55. 跳跃游戏

解1

动态规划
f(i) 表示当前所能跳跃到的最大索引

• f(0) = 0
• 当f(i - 1) >= i时， f(i) = max(f(i - 1), i + nums[i])
• 当f(i - 1) < i时， f(i) = f(i - 1) 即跳跃到的最大索引不会更新了

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        
        if len(nums) <= 1:
            return True
        
        # 当前所能跳跃到的最远索引
        maxIndex = 0
        
        for i in range(len(nums) - 1):
            
            # 若跳不到i 自然也跳不到i后面的所有索引
            if maxIndex < i:
                return False
            
            maxIndex = max(maxIndex, i + nums[i])
            
        if maxIndex >= len(nums) - 1:
            return True
        else:
            return False

解2

动态规划
逆序思维
i 表示当前能到达最后一个位置的最小索引

• 初始 i = n - 1
• 当 i - j <= nums[j] 时，i = j
• 当i - j > nums[j] 时，i不变 （表示不能从 j 跳跃到 i）

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        
        if len(nums) <= 1:
            return True
        
        i = len(nums) - 1
        
        for j in range(len(nums) - 2, -1, -1):
            
            if i - j <= nums[j]:
                i = j
                
        return i == 0