Leetcode 55 跳跃游戏

给你一个非负整数数组 nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该下标可以跳跃的最大长度。
判断你是否能够到达最后一个下标。

一开始想了一个比较笨的方法，就是从后往前推，递归的判断每一个元素能否到达最后一个元素。

后来发现从前往后推更简单，直接用一个变量right来记录当前能到达的最远位置。每次遍历到一个元素时，如果当前元素的下标小于等于right，就更新right为max(right, i+nums[i])。如果在遍历过程中发现right已经大于等于最后一个元素的下标，就可以返回True。

class Solution:
    # 递归模拟过程
    # def canJump(self, nums: List[int]) -> bool:
    #     n = len(nums)
    #     if n == 1:
    #         return True
    #     last_num, dis = nums[-1], 1
    #     for i in range(n-1, 0, -1):
    #         cur_jump = nums[i-1]
    #         if cur_jump >= dis:
    #             return self.canJump(nums[:n-1])
    #         else:
    #             dis += 1
    #             continue
    #     return False

    def canJump(self, nums: List[int]) -> bool:
        right = 0
        for i in range(len(nums)):
            if i <= right:
                right = max(right, i+nums[i])
                if right >= len(nums) - 1:
                    return True
        return False