这是跟着代码随想录的顺序学习算法的第？天。

以下是学习时自己的一些理解与笔记，如有错误欢迎指正与讨论。

55. 跳跃游戏、45. 跳跃游戏 II

参考相关链接：

55. 跳跃游戏

45. 跳跃游戏 II

代码随想录

笔记

55.跳跃游戏

本题重点在于，题目只是要求判断能否到达最后一个下标，而没有要求说明是如何到达最后一个下标的，所以思考重心应该放在 如何判断能否到达 ，而不是 如何才能到达 ，也就是只考虑判断。

想要判断从这个数组这条路往下走，能否到达最后一个下标，那自然而然就要知道从这个数组这条路往下走能够走多远，一步步地走，一步步地记录此时能够走的最远距离。

如果能走的最远距离达到了或者超过了最后一个下标，就说明可以到达，具体怎么到达的，不关心。

var canJump = function(nums) {// 范围覆盖const len = nums.length;if(len === 1) return true;let distance = nums[0];for(let i = 0; i <= distance; i++){distance = Math.max(distance, nums[i] + i);if(distance >= len - 1) return true;}return false;
};

45. 跳跃游戏 II

本题在上一题的情境下，变化了一下要求，要求使用最少的跳跃次数来到达数组的最后一个位置，同时，题目保证了给的数组是一定可以到达最后一个位置的。

同样，本题是要求使用最少的跳跃次数，而不关心具体是如何到达的，因此，思考重心就需要放到 在跳的步数最少的情况下，何时能够到达终点 ，而不是 跳最少步数的路径 。

为了让跳跃次数最少，就需要让跳的每一步利益最大化，这里的利益最大化指的是，需要找到本次可跳跃范围内，下一步可跳的最远位置，注意，是关注下一步最远能够跳到哪里，而不关心是从本次可跳跃范围内的哪一步开始跳跃的。

因此，我们就需要去找，本次跳跃可达到的最大利益是多少，具体的思路就是，先迈出一步，在迈得过程中，不断更新最大的利益，也就是下一步最远能够到达哪里。

当迈到本次最远的可跳跃范围的时候，迈出下一步，此时的可跳跃范围已经在上一次迈步的时候求出了结果，注意，此时我们并不关心是在哪里迈出下一步的，我们只关心下一步能够走多远。

每次迈出新的一步的时候记录步数，当发现下一步最远能够到达终点，返回结果。

写出代码。

// 报错
var jump = function(nums) {if(nums.length === 1) return 0;let distance = nums[0];let cur = nums[0];let res = 1;for(let i = 0; i <= distance; i++) {distance = Math.max(distance, nums[i] + i);if(i === cur) { // 在走到这一步能走的最远地方时候 迈出下一步res++;cur = distance;if(distance >= nums.length - 1) return res; // 判断此时迈了这一步后能否直接到达终点}}return res;
};

报错案例是

输入 [1,2]
输出 2
预期结果 1

前面的思路应该是没有找到什么逻辑上的问题的，那么为什么会报这个错呢？

按理说，从 1 迈一步就可以直接到达 2 了，为什么输出结果是需要两步呢？

检查了一下，发现

// ...
let res = 1;
// ...

是在这里出了问题， 这里默认起始状态下迈了新的一步出去，但是，没有进行判断，也就是说，并没有按照前面的思路来做。于是这里只需要补上这一步就可以了。

// ...
let res = 1;
if(distance >= nums.length - 1) return res;
// ...

在这里，我们其实也可以不在初始化的时候做额外判断。

上面需要在初始化的时候做额外判断的原因是，我们是在每次迈出新的一步的时候，去进行判断。

而迈出第一步的时候可能就可以直接到达终点，所以第一步也需要判断。

也就是说，问题出在了每次迈出新的一步的时候都需要进行判断，那就不进行这个判断不就好了，题目已经保证了一定可以到达终点，那么我们只需要在走到终点的时候记录此时已经走的步数就可以了，不需要知道什么路径到达终点是少跳跃次数的。

写出代码。

// 报错
for(let i = 0; i < nums.length; i++) {distance = Math.max(distance, nums[i] + i);if(i === cur) {res++;cur = distance;}
}
return res;

报错案例是

输入 [1,2]
输出 2
预期结果 1

这是为什么呢？一定要每次迈步都判断吗？

测试一下

输入 [1,2,3]
输出 2
预期结果 2输入 [2,2,3]
输出 2 // 错误
预期结果 1输入 [3,2,3]
输出 1
预期结果 1

测试发现只有第二个案例是错误的，第一个案例不能一步到达最后一个元素，而第三个案例同样是可以一步到达最后一个元素的情况，却得到了正确答案。

对比一下第二种和第三种情况，可以发现第二种情况是刚刚好能够到达最后一个元素，而第三个案例是可到达的最远位置是在最后一个元素之后的。

第二种情况下，到达最后一个元素的时候，同时也到达了本次可移动的最远距离，于是多迈了一步。

第三种情况下，到达最后一个元素的时候，没有到达本次可移动的最远距离，所以没有多迈一步。

那么，该怎么处理这种情况，怎样让其不多走这一步？

在这里，我们知道是一定可以走到最后一个元素的，所以我们在确切的走到最后一个元素的时候，再下来看跳了多少次。

事实上，我们并不需要走到最后一步才能够知道答案，在走到 nums.length - 1 的时候，其实就已经可以得到结果了。

• 如果在走到 nums.length - 1 的时候，没有到达了本次跳跃的最远距离，也就意味着我们这一次跳跃一定可以至少多跳一格，也就是可以到达最后一个元素，所以此时可以得到正确的跳跃次数。

• 如果在走到 nums.length - 1 的时候，到达了本次跳跃的最远距离，就需要再迈一步，下一次的跳跃一定能够到达最后一个元素，那如果倒数第二个元素是 0 呢？这并不影响结果，因为我们只是在这个地方发现需要再迈一步，也就是再跳一次，但我们并不一定就是在这个地方起跳，因此，没有影响，还是能够得到正确的跳跃次数。

for(let i = 0; i < nums.length - 1; i++) {distance = Math.max(distance, nums[i] + i);if(i === cur) {res++;cur = distance;}
}
return res;