class Solution:
    def canJump(self, nums: List[int]) -> bool:
        offset=0
        def dfs(index):
            nonlocal offset
            if index>=len(nums) or index+nums[index]>=len(nums)-1:
                return True
            if nums[index]==0:
                return False
            for i in range(index+nums[index],index,-1):
                if i>offset:
                    offset=i
                    if dfs(i):
                        return True                 
            return False
        return dfs(0)

'''
超时
'''

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        canreach=0
        for index,n in enumerate(nums):
            if index<=canreach:
                canreach=max(canreach,index+n)
        return canreach>=len(nums)-1

'''
执行用时：
44 ms
, 在所有 Python3 提交中击败了
87.18%
的用户
内存消耗：
16.1 MB
, 在所有 Python3 提交中击败了
7.13%
的用户
'''