[45] 跳跃游戏 II

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

输入: [2,3,1,1,4]

输出: 2

解释: 跳到最后一个位置的最小跳跃数是 2。

从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

说明:

假设你总是可以到达数组的最后一个位置。

假设我们没有 [55] 跳跃游戏 这道题的经验，可以先来直接尝试梳理这道题的思路。

从题目可以看出，这里又是一道求最值的问题，因此理所当然的使用动态规划。

可以看出，如果要求出当前位置i的最小跳跃步数，需要选出在所有 0 到 i-1 位置中，可达当前位置且所需步数最小的那个，再 +1 即可得到到达当前位置的最小步数。

于是就有了以下解法：

function jump(nums: number[]): number {
  const len = nums.length;
  if (len === 1) return 0;
  const dp = Array(len).fill(Number.MAX_SAFE_INTEGER);
  dp[0] = 0;
  for (let i = 1; i < len; i++) {
    for (let j = 0; j < i; j++) {
      // 如果从j点能跳跃到i点，则比较，取较小步数结果
      if (j + nums[j] >= i) {
        dp[i] = Math.min(dp[i], dp[j] + 1);
      }
    }
  }
  return dp[len - 1];
}

注意到，这样的时间复杂度会比较高，达到了O(n^2)。有没有更好的解法呢？

根据 [55] 跳跃游戏 的解题经验，我们知道，这里具有贪心选择性质，因此只需要管局部最优即可。

即从i点开始，获取它所能到达的最远位置end，并通过遍历获取i到end位置之间是否有下一跳能达到更远位置的点，将最远位置使用一个变量greedy暂存起来。

当i到达end时，此时的greedy表示，在i到end位置中，一跳之内所能达到的最远位置为greedy。此时更新end为greedy，并将最小跳数 +1。

最终遍历结束时，返回当前所在位置的最小跳数即可。

function jump(nums: number[]): number {
  const len = nums.length;
  let end = 0;
  let greedy = 0;
  let jumps = 0;
  for (let i = 0; i < len - 1; i++) {
    greedy = Math.max(greedy, i + nums[i]);
    if (i === end) {
      jumps += 1;
      end = greedy;
    }
  }
  return jumps;
}