[55] 跳跃游戏

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

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

判断你是否能够到达最后一个位置。

示例 1:

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

输出：true

解释：我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例 2:

输入：[3,2,1,0,4]

输出：false

解释：无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

这道题也是一个求最值的题目，我们可以把问题改造成这样：若最远跳跃距离超过最后一个位置，则返回true，否则返回false。

所以习惯上，我们想到使用动态规划的方式，若想到达最后一个格子，那么需要前面有格子的最大跳跃距离超过当前格子。

那么仅需要记录下来每一个格子是否可达，并且从可达的格子作为起点，将它跳跃距离内的所有格子都标记为可达。

这样依次遍历下去，就能获取最后一个格子的可达性了。

function canJump(nums: number[]): boolean {
  const len = nums.length;
  if (len === 1) return true;

  const dp: boolean[] = Array(len).fill(false);
  dp[0] = true;

  for (let i = 0; i < len - 1; i++) {
    if (dp[i]) {
      let jump = nums[i];

      for (let j = i + 1; j <= i + jump && j < len; j++) {
        dp[j] = true;
      }
    }
  }

  return dp[len - 1];
}

但这种解法的复杂度可能较高，时间复杂度为 O(N*M)，空间复杂度为 O(N)，N 为 nums 长度，M 为所有位置的最大跳跃长度。

我们注意到，当一个格子成为可达后，我们其实完全不再需要关心到达此处的其他可达路径。也就是说，不再需要动态规划那样递归的处理子问题了。

于是，这里存在着一次贪心选择的可能。我只判断每一个格子的最远可达距离，看所有的格子的最远可达距离是否超过最后一个位置即可。

因此，最终我们利用了贪心法来解题。

如果某一个作为 起跳点 的格子可以跳跃的距离是 nums[i]，那么表示后面 nums[i] 个格子都可以作为 起跳点。跳到的最远位置为 i + nums[i]。

可以对每一个能作为 起跳点 的格子都尝试跳一次，把 能跳到最远的距离 不断更新。

如果可以一直跳到最后，就成功了。

当发现当前的格子不能作为起跳点，说明当前格子时不可达的。说明没有到达下一个格子的方法，此时返回失败。

function canJump(nums: number[]): boolean {
  let furtherest = 0;

  for (let i = 0; i < nums.length; i++) {
    if (i > furtherest) return false;
    furtherest = Math.max(furtherest, i + nums[i]);
  }
  return true;
}