55.跳跃游戏题目来源：https://leetcode-cn.com/problems/jump-game题目给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表您可以在该位置跳跃的最大长度。确定您是否可以到达最后一个位置。示例1：输入：[2,3,1,1,4]输出：true解释：我们可以先跳1步，从位置0到位置1，然后从位置1跳3步到最后一个位置。示例2：输入：[3,2,1,0,4]输出：false解释：无论如何，你总是会到达索引为3的位置。但是那个位置的最大跳跃长度是0，所以你永远不能到达最后一个位置。解题思路：greedy下面位置的计算从0开始，需要先注意题目。其中，初始起始位置是数组的第一个位置（注意这个位置是索引位置）。另外，数组中的每一个元素，也就是索引对应的值，就是当前位置可以跳转的最大长度。（明确区分这两个变量）那么根据上面的理解，先例1：[2,3,1,1,4]初始起始位置为0，最大可跳转长度为2。所以意思这里就是下面两个位置可以作为下一次的起始位置（这里可能有点绕）。即可以从起始位置0跳到位置1或位置2，此时后两个位置可以根据选择作为新的起始点。然后在每个起点尝试跳跃，计算出最远可以到达的位置值，并不断维护和更新这个值。只要你能跳到最后，就意味着成功。这里注意，可以跳转到最远的位置，只要这个值大于等于上一个位置，就代表成功。当某个位置和该位置可以跳跃的最远距离之和大于最终位置时，按照上面的理解，就意味着可以将最终位置作为起点，也可以理解为着陆在最后的位置。再看例子1，起始位置为0，最长可跳长度为2，先尝试跳1步到位置1，此时该位置最远跳长度为3，所以最远跳距离canbejumpedis4.这个时间刚好等于最后一个位置4。然后返回True，说明可以跳到最后一个位置。看例子2，为什么返回False？[3,2,1,0,4]首先注意数组中位置3的元素，表示当前位置跳转的长度为0，也就是说跳转到这个位置时，不可能跳到最后。然后看初始起始位置0，最长可跳转长度为3。此时如果选择直接跳到位置3，那么就不能像上面说的那样跳到终点。然后先跳到位置1。此时最大长度为2，如果选择最大长度跳，也会落到3号位，只能选择跳到2号位，此时最大长度为1，会还是掉到3号位。假设你回到0号位，选择跳到2号位，也会出现和上面一样的情况，这个位置只能跳到3号位。所以无论你选择什么，你都会去到3号位，所以不可能跳到最后，最后返回False。具体实现可以看下面的代码。代码实现类解决方案：defcanJump(self,nums:List[int])->bool:#其中farthest为最远的长度，需要维护更新的长度，farthest=len(nums),0为iinrange(length):#记录当前位置和在该位置可以跳跃的最大长度i+nums[i]#与最远长度比较，取较大值，更新最远ifi<=farthest:farthest=max(i+nums[i],farthest)#如果最远位置大于最后一个位置#表示可以到达最后一个位置，returnTrueiffarthest>=length-1:returnTruereturnFalse实现result以上就是利用贪婪的思想解决《55. 跳跃游戏》问题的主要内容，在每个起点尝试跳最远的距离，保持这个值，只要能到达最后的位置，就表示成功。欢迎关注微信公众号《书所集录》
