45。跳跃游戏二题目来源：https://leetcode-cn.com/problems/jump-game-ii题目给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表您可以在该位置跳跃的最大长度。您的目标是使用最少的跳跃次数到达数组中的最后一个位置。示例：输入：[2,3,1,1,4]输出：2解释：到达最后一个位置的最小跳数为2。从索引0跳到索引1，跳1步，然后跳3步到达数组的最后一个位置。解释：假设你总能到达数组的最后一个位置。解题思路：贪心算法首先注意题意的解释部分【假设你总能到达数组的最后一个位置】。这里我们只需要考虑题目中给出的数组必须能够到达数组的最后一个位置即可。这道题的要求和之前的55.跳跃游戏不同。第55题要求的return是否能到达最后位置。如果用第55题的反例来论证这道题意义不大，如果觉得有必要，也可以在达不到的时候返回一个具体的值做标记，比如0。现在考虑如何找到到达最终位置的最少跳跃次数？在这里，我们考虑使用前向寻找最远可达的位置。这里以例1为例，[2,3,1,1,4]，索引为0，这里的元素值为2，表示跳转到这个位置可以到达的位置是接下来两个位置，如下图红色部分：这里，在索引为1的位置，元素值为3，表示可以跟随三个位置，最远可以到达的位置为索引4，以及此处已到达终点位置。而在index2的位置，值为1，这里只能跳到index3的位置。这里很明显，从index1的位置跳可以到达更远的位置。假设数组还没有走到尽头，现在选择跳转到index1的位置，据说在这个位置可以跳转到后面三个位置。这里如何选择落脚点？如上所述，在每个可到达的位置，确定每个可以跳跃的最远位置。现在位置在index1的位置上方，如下图，红色的3个部分是在index1的位置跳转的选项，跳到index4的位置可以跳到更远的位置，所以这是目前最好的落脚点。现在考虑如何实现呢？我们可以保持这个最远可达的位置，作为边界。当我们向前遍历，到达边界时，更新边界，相应的跳转次数加1。这里需要注意一点，当我们从正向遍历的时候，不需要遍历最后一个位置。根据上面的描述，我们知道我们一定会到达这里的最后一个位置。那么前面提到的需要维护的边界必须大于等于最后一个位置。如果边界刚好在最后一个位置，按照上面提到的更新边界和到达边界时跳转次数加1的逻辑，这里会增加不必要的跳转。所以不要考虑访问最后一个位置。具体代码实现如下。代码实现类解决方案：defjump(self,nums:List[int])->int:#定义最远位置、边界和步数max_pos=0end=0steps=0foriinrange(len(nums)-1):#获取最远可到达的位置max_pos=max(max_pos,i+nums[i])#到达边界时，更新边界#ifi==end同时跳转次数加1:end=max_possteps+=1returnSteps实现结果上面是用贪心算法从数组开始向前遍历，保持能跳最远的位置，确定边界，到达边界时更新边界，增加跳跃次数，然后解决《45. 跳跃游戏 II》问题的主要内容。欢迎关注微信公众号《书所集录》
