0055. 跳跃游戏

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]。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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
本站总访问量  次  |  您是本站第  位访问者