leetcode：55. 跳跃游戏

题目

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。

示例：

  1. 输入：nums = [2,3,1,1,4]
  2. 输出：true
  3. 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
  1. 输入：nums = [3,2,1,0,4]
  2. 输出：false
  3. 解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

解答 & 代码

解法一：普通动态规划

  • 动态规划数组 **dp**：dp[i] 代表下标为 i 的位置能否到达（true 能到达，false 不能到达）
  • 状态转移方程：在下标 i 之前的位置（即下标区间为 [0, i - 1]），如果存在一个下标 j 能够到达，且 j + nums[j] >= i，则下标 i 也能到达，即 dp[i] = true；否则 dp[i] = false

  • 初始化：第一个下标能到达，即 dp[0] = true 

    1. class Solution {
    2. public:
    3.   bool canJump(vector<int>& nums) {
    4.       int len = nums.size();
    5.       vector<bool> dp(len, false);    // 动态规划数组，dp[i] 代表下标为 i 的位置能否到达
    6.       dp[0] = true;                                    // 初始化
    7.         // 状态转移
    8.       for(int i = 1; i < len; ++i)
    9.       {
    10.           for(int j = i - 1; j >= 0; --j)
    11.           {
    12.                 // 如果找到一个 j ∈ [0, i - 1]，j 本身可到达，且 i 在 j 的跳跃范围之内
    13.                 // 则 dp[i] = true，即下标 i 可到达
    14.               if(dp[j] == true && j + nums[j] >= i)
    15.               {
    16.                   dp[i] = true;
    17.                   break;
    18.               }
    19.           }
    20.       }
    21.       return dp[len - 1];
    22.   }
    23. };

    复杂度分析：设 nums 数组长度为 n

  • 时间复杂度 [中等] 55. 跳跃游戏 - 图1：双重循环

  • 空间复杂度 O(n)：dp 数组的空间复杂度为 O(n)

执行结果：

  1. 执行结果：通过
  3. 执行用时：132 ms, 在所有 C++ 提交中击败了 9.80% 的用户
  4. 内存消耗：47.5 MB, 在所有 C++ 提交中击败了 10.10% 的用户

解法二：贪心算法 动态规划

有关动态规划的问题，大多是让你求最值的，比如最长子序列，最小编辑距离，最长公共子串等等等。这就是规律，因为动态规划本身就是运筹学里的一种求最值的算法。 贪心算法作为特殊的动态规划也是一样，也一定是让你求个最值。 这道题表面上不是求最值，但是可以改一改：请问通过题目中的跳跃规则，最多能跳多远？如果能够越过最后一格，返回 true，否则返回 false。

贪心算法：每一步都计算一下从当前位置最远能够跳到哪里，然后和一个全局最优的最远位置 farthest 做对比，通过每一步的最优解，更新全局最优解，这就是贪心。

具体的，
设想一下，对于数组中的任意一个位置 y，我们如何判断它是否可以到达？根据题目的描述，只要存在一个位置 x，它本身可以到达，并且它跳跃的最大长度为 x + nums[x]，这个值大于等于 y，即 x + nums[x] ≥ y，那么位置 y 也可以到达。

依次遍历数组 nums 中的每一个位置，设当前遍历到下标 i：

  • 如果当前位置在最远能跳到的位置 farthest 范围内，那么说明当前位置是可以到达的
    • 用当前位置能跳到的最远距离 i + nums[i] 更新全局可达最远位置 farthest
    • 如果最远可达位置 farthest 大于等于数组最有一个位置，那么说明数组最后一个位置可达，直接返回 true

  • 否则，当前位置不可到达，直接返回 false（后面的位置更不可能到达）

    1. class Solution {
    2. public:
    3.   bool canJump(vector<int>& nums) {
    4.       int len = nums.size();
    5.       int farthest = 0;        // 目前最远能跳到的位置（全局最优解）
    6.       // 遍历数组的每一个位置，并实时维护最远能跳到的位置 farthest
    7.       for(int i = 0; i < len; ++i)
    8.       {
    9.           // 如果当前位置在最远能跳到的位置 farthest 范围内，那么当前位置是可以到达的
    10.           if(i <= farthest)
    11.           {
    12.               // 用当前位置可达的最远位置 i + nums[i] 更新全局可达最远位置 farthest
    13.               farthest = max(farthest, i + nums[i]);
    14.               // 如果最远可达位置 farthest 大于等于数组最有一个位置，
    15.               // 那么说明数组最后一个位置可达，直接返回 true
    16.               if(farthest >= len - 1)
    17.                   return true;
    18.           }
    19.           // 否则，当前位置不可到达，直接返回 false（后面的位置更不可能到达）
    20.           else
    21.               return false;
    22.       }
    23.       return false;
    24.   }
    25. };

    复杂度分析：设 nums 数组长度为 n

  • 时间复杂度 O(n)：只遍历了一次数组

  • 空间复杂度 O(1)：

执行结果：

  1. 执行结果：通过
  3. 执行用时：56 ms, 在所有 C++ 提交中击败了 42.61% 的用户
  4. 内存消耗：47.2 MB, 在所有 C++ 提交中击败了 46.86% 的用户

换种写法：逻辑相同

  1. class Solution {
  2. public:
  3.     bool canJump(vector<int>& nums) {
  4.         int len = nums.size();
  5.         int farthest = 0;
  6.         for(int i = 0; i < len; ++i)
  7.         {
  8.             if(i > farthest)
  9.                 return false;
  10.             farthest = max(farthest, i + nums[i]);
  11.             if(farthest >= len - 1)
  12.                 return true;
  13.         }
  14.         return farthest >= len - 1;
  15.     }
  16. };

执行结果：

  1. 执行结果：通过
  3. 执行用时：36 ms, 在所有 C++ 提交中击败了 98.31% 的用户
  4. 内存消耗：47.2 MB, 在所有 C++ 提交中击败了 68.24% 的用户