python 跳跃游戏

leetcode 55 跳跃游戏

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。
示例1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标

示例2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后
一个下标。

提示：

• 1 <= nums.length <= 3 * 104
• 0 <= nums[i] <= 105

一、贪心算法求解

1.1 求解思路

我们可以用贪心的方法解决这个问题。

对于每一个可以到达位置的索引为$idx$，它使得 $idx+1,idx+2,\cdots ,idx+\text{nums}[idx]$ 这些最大覆盖范围内的位置都可以到达。

依次遍历数组中的每一个位置，并实时更新该位置的最大覆盖范围。对于当前遍历到的位置 $x$，如果它在最大覆盖范围内，那么我们就可以从起点通过若干次跳跃到达该位置，因此我们可以用 $idx+\text{nums}[idx]$更新最远可以到达的位置。

在遍历的过程中，如果最大覆盖范围大于等于数组中的最后一个位置，那就说明最后一个位置可达，我们就可以直接返回 True 作为答案。反之，如果在遍历结束后，最后一个位置仍然不可达，我们就返回 False 作为答案。

1.2 代码实现

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        right_most = 0  # 记录最大覆盖范围
        for idx, val in enumerate(nums[:-1]): # 忽略最后一个位置
            right_most = max(right_most, idx+val)  # 当前位置上，最远能跳到哪
            # 如果最远都无法超过当前位置，那肯定无法到达最后一个位置，提前结束
            if right_most <= idx:
                return False 
        return True

1.3 复杂度

时间复杂度：$O(n)$，其中 $n$ 为数组的大小。只需要访问 nums 数组一遍，共 $n$ 个位置。

空间复杂度：$O(1)$，不需要额外的空间开销。

二、动态规划求解

2.1 求解思路——五部曲

1. 确定dp数组（dp table）以及下标的含义:
   dp[i]表示在下标i处跳跃的覆盖范围。

2. 确定递推公式
   对于dp[i]，它等于dp[i-1]跳一格到达i处后剩余的步数，和nums[i]的最大值。因此得出状态转移方程为：$$dp[i]=max(dp[i-1]-1,nums[i])$$

3. dp数组如何初始化
   边界条件：$dp[0]=nums[0]$

4. 确定遍历顺序
   在每次循环开始，我们判断dp[i-1]是否等于0，若是，则不可能到达下标i处，因此直接返回false。循环结束后 返回true

5. 举例推导dp数组

2.2 代码实现

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        dp = [0] * n
        dp[0] = nums[0]
        for i in range(1,n):
            if dp[i-1] == 0: 
                return False
            dp[i] = max(dp[i-1]-1,nums[i])
        return True

2.3 复杂度

时间复杂度：$O(n)$，其中 $n$ 为数组的大小。只需要访问 nums 数组一遍，共 $n$ 个位置。

空间复杂度：$O(n)$