45. 跳跃游戏 II

Difficulty
Medium
Tags
动态规划
URL
https://leetcode.cn/problems/jump-game-ii/
Star
给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。
示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是2。
     从下标为 0 跳到下标为 1 的位置，跳1 步，然后跳3 步到达数组的最后一个位置。
示例 2:
输入: nums = [2,3,0,1,4]
输出: 2
提示:
  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 1000
通过次数329,225提交次数738,679

法1 动态规划-第二类基本型

思路
dp[i] 表示到达当前位置需要的最少跳跃次数。
站在 位置 i 处， 当前位置的最少跳跃次数是由之前的 某个位置的 可以跳跃的最大长度 决定的。即需要寻找一个最佳的前驱位置。
题解
class Solution:
    def jump(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return 0
        dp = [len(nums) for _ in nums]
        dp[0] = 0

        for i in range(1, len(nums)):
            for j in range(i-1, -1, -1):
                if nums[j] + j >= i:
                    dp[i] = min(dp[i], dp[j]+1)
                # 可以提前停止
                if nums[j] + j >= len(nums)-1:
                    return dp[j] + 1

                # 不可能再有更少的步数了
                if dp[i] == dp[i-1]:
                    break

        return dp[-1]
当然，也可以换个角度，在每个位置时，就把可到达的后面的位置的最少步数更新一下
class Solution:
    def jump(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return 0
        dp = [len(nums) for _ in nums]
        dp[0] = 0

        for i in range(0, len(nums)):
            for j in range(i+1, i+1+nums[i]):
                if j >= len(nums)-1:
                    return dp[i]+1
                dp[j] = min(dp[j], dp[i] + 1)

        return dp[-1]

法 2 贪心 + 动态规划

思路
在寻找 i 的最佳前驱 j 的时候，我们希望找的 j 是最靠前的，因为 j 越靠前 意味着 到达 j 的步数最少，所以找到一个前驱其实就可以停止了。 
class Solution:
    def jump(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return 0
        dp = [len(nums) for _ in nums]
        dp[0] = 0

        for i in range(1, len(nums)):
            for j in range(0, i, 1):
                # 只要找到一个 就可以提前停止
                if nums[j] + j >= len(nums)-1:
                    return dp[j] + 1

                if nums[j] + j >= i:
                    dp[i] = min(dp[i], dp[j]+1)
                    break
            
        return dp[-1]
再 进一步优化， 可以想象 i+1 的最佳前驱 j_{i+1} 一定是大于等于 i 的最佳前驱的 j_{i} 的。所以找前驱j的时候，没必要从 0 开始找，只需要记住上一个前驱即可，每次都从上一个前驱开始寻找。
题解
class Solution:
    def jump(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return 0
        dp = [len(nums) for _ in nums]
        dp[0] = 0
        
        best_j = 0
        for i in range(1, len(nums)):
            for j in range(best_j, i, 1):
                if nums[j] + j >= i:
                    dp[i] = min(dp[i], dp[j]+1)
                    best_j = j
                    break

        return dp[-1]