给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
来源：力扣（LeetCode）
刚看到这个题目的时候，我觉得应该用回溯或者动态规划算法：从元素的倒数第二个位置开始遍历，看看它能否到达最后一个位置——如果不能到达，继续向前遍历其他元素；如果能到达，将该元素作为新数组的最后位置，看看是否有元素能够到达该元素，以此类推，直到找到第0个元素。
后来整了半天还是没有写出来程序，看了看题解，发现还是大神的脑回路厉害。这道题用的是贪心算法，关键思想是：如果能到达某个位置，那一定能到达它前面的所有位置。
具体的解题思路如下： ①假设当前能到达的最远位置为变量 max_position，并初始化为 0； ②遍历数组 nums 中的元素，如果当前能到达的最远位置大于等于当前位置 i，并且当前位置 i 加上其对应元素 jump 能够达到的位置超过 max_position，那么更新 max_position； ③如果当前能到达的最远位置变量 max_position 到不了当前位置 i ，直接返回 False 提前结束循环；如果当前能到达的最远位置变量 max_position 大于等于数组最远位置，直接返回 True 提前结束循环。
代码如下：
def canJump(self, nums: List[int]) -> bool: max_position = 0 n = len(nums) for i, jump in enumerate(nums): if max_position < i: return False if i+jump>max_position: max_position = i+jump if max_position >= n-1: return True return max_position >= n-1