跳跃游戏

1、题目

图1

2、题解

贪心

对于每一个位置x，该位置可以到达的最远距离是\(x+nums[x]\)。通过遍历数组中每一个位置，同时维持该位置可以到达的最远距离。在遍历的过程中，如果最远可以到达的位置大于等于数组中的最后一个位置，那就说明最后一个位置可达，直接返回\(True\)。如果遍历结束不可到达，则返回\(False\)。

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        max_step = 0
        for i,jump in enumerate(nums):
            if max_step>=i and i+jump>max_step:
                max_step = i+jump
            
            if max_step<i:
                return False
        
        return True