0055. 跳跃游戏.md

0055. 跳跃游戏

• 标签：贪心算法、数组、动态规划
• 难度：中等

题目大意

给定一个非负整数数组 nums，数组中每个元素代表在该位置可以跳跃的最大长度。

开始位置为数组的第一个下标处。要求判断是否能够到达最后一个下标。

解题思路

定义动态规划状态 dp[i] 为：从 0 出发，经过 j ≤ i，可以跳出的最远距离。可以得出。

• dp[0] = nums[0]。表示从 0 出发，经过 0，可以跳出的最远距离为 nums[0]。
• 如果能通过 0 ~ i-1 个位置到达 i，即 dp[i-1] ≥ i，则 dp[i] = max(dp[i-1], i + nums[i])。
• 如果不能通过 0 ~ i-1 个位置到达 i，即 dp[i-1] < i，则 dp[i] = dp[i-1]。

代码

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        size = len(nums)
        dp = [0 for _ in range(size)]
        dp[0] = nums[0]
        for i in range(1, size):
            if i <= dp[i-1]:
                dp[i] = max(dp[i-1], i + nums[i])
            else:
                dp[i] = dp[i-1]
        return dp[-1] >= size - 1