算法练习12——跳跃游戏

LeetCode 55 跳跃游戏

给你一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false 。

贪心

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        pos = 0
        for idx, num in enumerate(nums):
            if idx > pos or pos >= len(nums) - 1:
                break
            pos = max(pos, idx + num)
        return pos >= len(nums) - 1

虽然enumerate更加pythonic,但是实际测试enrmerate相比range更加耗时,不过差的很少,大概10ms左右,不影响AC

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        l = len(nums)
        pos = 0
        for idx in range(l):
            if idx > pos or pos >= l - 1:
                break
            pos = max(pos, idx + nums[idx])
        return pos >= l - 1

动态规划

看了一眼评论区,有人指出贪心实质上是动态规划,动态规划的思路如下,dp[n]为0~n位置能跳到的最远距离,所以状态转移方程为dp[n] = max(dp[n-1], dp[n-1] + nums[n]),初始值可以设置dp[0] = nums[0],一维动态规划,同时根据状态转移方程可知只涉及n和n-1,可以进行滚动优化,使用一个变量即可替代整个dp数组,由此可得解法。实质上滚动优化后动态规划思路的代码和贪心思路的代码是一致的。
果然动态规划最难的是找状态。