跳跃游戏

https://leetcode.cn/problems/jump-game/description/

思路

刚看到本题一开始可能想：当前位置元素如果是 3，我究竟是跳一步呢，还是两步呢，还是三步呢，究竟跳几步才是最优呢？

其实跳几步无所谓，关键在于可跳的覆盖范围！

不一定非要明确一次究竟跳几步，每次取最大的跳跃步数，这个就是可以跳跃的覆盖范围。

这个范围内，别管是怎么跳的，反正一定可以跳过来。

那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点！

每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。

贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。

局部最优推出全局最优，找不出反例，试试贪心！

如图：

求解

var canJump = function(nums) {
  let max = 0;
  for(let i=0;i<=max;i++){
    if (i+nums[i]>max) max = i+nums[i]
    if(max>=nums.length-1) return true
  }
  return false
};

求解过程中，写过一个错误版本，就是给max赋值之前没有判断。有一部分例子没法通过。

当时没通过的案例是[3,0,8,0,0,2],在这个案例中，如果不做判断那么覆盖范围max会卡在 1+0

跳跃游戏II

https://leetcode.cn/problems/jump-game-ii/description/

思路

本题相对于55.跳跃游戏 (opens new window)还是难了不少。

但思路是相似的，还是要看最大覆盖范围。

本题要计算最少步数，那么就要想清楚什么时候步数才一定要加一呢？

贪心的思路，局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。整体最优：一步尽可能多走，从而达到最少步数。

思路虽然是这样，但在写代码的时候还不能真的能跳多远就跳多远，那样就不知道下一步最远能跳到哪里了。

所以真正解题的时候，要从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最少步数！

这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。

如果移动下标达到了当前这一步的最大覆盖最远距离了，还没有到终点的话，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点。

如图：

图中覆盖范围的意义在于，只要红色的区域，最多两步一定可以到！（不用管具体怎么跳，反正一定可以跳到）

求解

var jump = function(nums) {
  let cover = 0
  let step = 0
  let last = 0
  for(let i=0;i<nums.length-1;i++){
    cover = Math.max(cover,i+nums[i])
    // 走了step步还没到终点，说明步数需要+1，
    // last记录的是当前覆盖范围的最后一个位置
    if(i === last){
      last = cover
      step++
    }
  }
  return step
};