题目

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。

示例：

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

输入: nums = [2,3,0,1,4]
输出: 2

解答 & 代码

解法一：动态规划 O(n^2)

动态规划数组 **dp**：dp[i] 代表到下标 i 的最少跳跃次数
状态转移方程： dp[i] = min(dp[j] + 1)，其中 j in [0, i - 1] 且能够从 j 跳一步到 i（即j + nums[j] >= i）

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

class Solution {
public:
  int jump(vector<int>& nums) {
      int len = nums.size();
      vector<int> dp(len, INT_MAX);
      dp[0] = 0;
      for(int i = 1; i < len; ++i)
      {
          for(int j = 0; j < i; ++j)
          {
              if(j + nums[j] >= i)
                  dp[i] = min(dp[i], dp[j] + 1);
          }
      }
      return dp[len - 1];
  }
};

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

时间复杂度：双重循环
空间复杂度 O(n)：dp 数组的空间复杂度为 O(n)

执行结果：

执行结果：通过

执行用时：1360 ms, 在所有 C++ 提交中击败了 5.00% 的用户
内存消耗：16.6 MB, 在所有 C++ 提交中击败了 17.03% 的用户

解法二：贪心

思想：每次在上次能跳到的范围 **(preEnd, end]** 内选择一个能跳的最远位置 **farthest** 作为新的能跳到的范围

[中等] 45. 跳跃游戏 II - 图2
初始时最远可到的位置 farthest = 0，上次跳跃可到达的范围右边界 end = 0，跳跃的次数 step = 0，初始时在位置 0

在位置 0 的位置，可以向前跳 1，2 或 3 步，最远可以到达的位置 3，因此 farthest = max(0, 3) = 3
1. 当前位置 0 == 上次跳跃可到达的范围右边界 end，则更新跳跃可达的范围右边界 end = farthest，跳跃数 +1，开始下一次跳跃
上次跳跃可到达的范围 1、2、3
1. 位置 1，最远可以到达的位置 1 + 1 = 2，因此 farthest = max(3, 2) = 3
2. 位置 2，最远可以到达的位置 2 + 4 = 6，因此 farthest = max(3, 6) = 6
3. 位置 3，最远可以到达的位置 3 + 2 = 5，因此 farthest = max(6, 5) = 6
  1. 位置 3 == 上次跳跃可到达的范围右边界 end，因此更新跳跃可达的范围右边界 end = farthest，跳跃数 +1，本次跳跃从位置 2 开始，开始下一次跳跃
… …

class Solution {
public:
    int jump(vector<int>& nums) {
        int len = nums.size();
        int farthest = 0;    // 当前能跳到的最远位置
        int end = 0;        // 上次跳跃可达的范围右边界
        int step = 0;        // 跳跃次数
        for(int i = 0; i < len - 1; ++i)
        {
            farthest = max(farthest, i + nums[i]);
            // 如果到达了上次跳跃可达的范围右边界
            if(i == end)
            {
                // 更新跳跃可达的范围右边界
                end = farthest;
                ++step;        // 跳跃次数 +1，开始下一次跳跃
            }
        }
        return step;
    }
};

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

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

执行结果：

执行结果：通过

执行用时：12 ms, 在所有 C++ 提交中击败了 77.06% 的用户
内存消耗：16.1 MB, 在所有 C++ 提交中击败了 57.84% 的用户