【Leetcode】55- 跳跃游戏

问题简述

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

示例 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 <= 10⁴
0 <= nums[i] <= 10⁵

思路分析

解法一：

该问题也是分阶段求解的，每个阶段的最优解是基于之前阶段的最优解（“最优子结构”），且当前阶段的解与之后阶段的解无关（“无后效性”），可以考虑采用动态规划求解。

原数组中每个下标对应的值表示的是 在该位置可以跳跃的最大长度 ，初始为nums[i]，但我们的问题是：从第一个下标是否可以经过多次跳跃到达最后一个下标。因此对于每一个下标 $i$，不仅要考虑 原始的该位置可以跳跃的最大长度，还需要考虑从该下标之前的其他下标 $j（j<i）$开始跳跃，跳到当前位置 $i$ 后还剩下的可以跳跃的最大长度。如果这个剩余的可以跳跃的最大长度大于当前下标原始的该位置可以跳跃的最大长度，则当前下标的从当前位置往后可以跳跃的最大长度 需要更新，反之不需要更新。

因此我们将每个阶段的状态定义为 从当前位置往后可以跳跃的最大长度，等于原始的该位置可以跳跃的最大长度、从上一个位置跳跃至当前位置之后剩下可以跳跃的最大长度 这两者之间的最大值。如果当前状态值大于0，说明可以从当前位置继续往后跳跃。我们从第一个下标开始往后逐个下标进行判断，直到倒数第二个下标，如果其状态值大于0，说明可以到达最后一个下标，则最终的问题结果为true。
我们用状态数组dp来记录每个位置的可以跳跃的最大长度，则状态转移方程为：dp[i] = max(dp[i-1]-1,nums[i])。由于当前状态仅与上一阶段状态有关，使用滚动数组思想对dp数组降维，使用一个变量保存上一阶段状态即可。

具体代码实现见代码示例的 解法一。

解法二：

该问题具有“最优子结构”和“无后效性”，也具有“贪心选择性质”（即原问题的全局最优解可以通过每个子问题的局部最优解来逐步推断得到），因此也可以采用贪心算法求解。
问题：从第一个下标开始，是否可以经过多次跳跃到达最后一个下标。
其子问题为：从第一个下标开始，是否可以跳跃到当前下标之后的下标。可以通过求解经过每个下标时可到达的最远下标，比较是否大于当前下标来判断。每个子问题的解都基于前一个子问题的解。
因此我们遍历数组的每个下标，计算经过每个下标时可到达的最远下标，如果该值有小于等于当前下标的，说明不可到达比当前更远的下标了，对于原问题“是否可以到达最后一个下标”可以直接返回false。否则继续计算，当前下标的可到达的最远下标基于原本可跳跃最远下标和其前一个下标的可到达的最远下标进行比较取更大者进行更新，直到倒数第二个下标，若其可到达的最远下标仍然大于当前下标，说明其后一个下标（即最后一个下标）也是可以到达的，最终返回true。

动态规划算法与贪心算法的异同🌟

相同点：

都具有最优子结构，即原问题可以拆解为对多阶段的子问题求解，每个阶段的问题的最优解包含了子问题的最优解；

不同点：

• 虽然都具有最优子结构，但子问题结构不同：
  • 动态规划的子问题有重叠，每个当前子问题与之前多个子问题有关（也可能只与上一个问题有关，与具体问题相关）。动态规划问题的求解分阶段进行（每个阶段对应一个子问题），每个阶段是由前几个可能的阶段转移而来的，这几个阶段之间会有重叠（对应了子问题的重叠），我们需要逐步求得所有阶段的状态（对应就是求解出所有子问题的最优解），直到求得最后阶段的状态（对应原问题的最优解）。因此动态规划问题的最优解来自于前几个子问题的最优解；
  • 贪心算法的子问题没有重叠，每个当前子问题只与其上一个子问题有关。当前问题的最优解就是基于前一个子问题的最优解得到的，这样逐个基于上一个子问题求解当前子问题的最优解，直到最后求解原问题，最终可以得到全局最优解。因此贪心算法的最优解来自于其前一个子问题的最优解；
• 复杂度不同：
  • 动态规划算法的时间复杂度和空间复杂度都会更高，因为需要求解所有子问题并记录最优解；
  • 贪心算法的复杂度会更低；

联系：

可以使用贪心算法求解的问题，一定可以使用动态规划算法求解。只不过贪心算法会按一定贪心选择的策略总是直接选择其中的一种最优解，而不用像动态规划算法需要保存所有子问题的最优解。

代码示例

解法一：

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        pre = nums[0]  # 记录前一个下标的 可以继续跳跃的最大长度
        for i in range(len(nums)-1):
            pre = max(pre - 1, nums[i])
            if pre <= 0:
                return False
        return True

解法二：

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        longestind = 0 # 记录从下标0开始每经过一个下标时可跳跃到达的最远下标
        lens = len(nums)
        for i in range(lens-1):
            longestind = max(longestind, i + nums[i])
            if longestind <= i:
                return False
        return True 

测试用例1：
输入：nums = [2,2,0,1,1]
预期输出：true

测试用例2：
输入：nums = [2,0,1,0,1]
预期输出：false

复杂度分析

时间复杂度 $O(n)$ 需要遍历一遍数组
时间复杂度 $O(1)$ 仅用常数个变量存储