0045. 跳跃游戏 II

0045. 跳跃游戏 II #

  • 标签:贪心、数组、动态规划
  • 难度:中等

题目大意 #

描述:给定一个非负整数数组 nums,数组中每个元素代表在该位置可以跳跃的最大长度。开始位置为数组的第一个下标处。

要求:计算出到达最后一个下标处的最少的跳跃次数。假设你总能到达数组的最后一个下标处。

说明

  • $1 \le nums.length \le 10^4$。
  • $0 \le nums[i] \le 1000$。

示例

1
2
3
输入nums = [2,3,1,1,4]
输出2
解释跳到最后一个位置的最小跳跃数是 2从下标为 0 跳到下标为 1 的位置 1 然后跳 3 步到达数组的最后一个位置

解题思路 #

思路 1:动态规划(超时) #

1. 划分阶段 #

按照位置进行阶段划分。

2. 定义状态 #

定义状态 dp[i] 表示为:跳到下标 i 所需要的最小跳跃次数。

3. 状态转移方程 #

对于当前位置 i,如果之前的位置 j($o \le j < i$) 能够跳到位置 i 需要满足:位置 j($o \le j < i$)加上位置 j 所能跳到的最远长度要大于等于 i,即 j + nums[j] >= i

而跳到下标 i 所需要的最小跳跃次数则等于满足上述要求的位置 j 中最小跳跃次数加 1,即 dp[i] = min(dp[i], dp[j] + 1)

4. 初始条件 #

初始状态下,跳到下标 0 需要的最小跳跃次数为 0,即 dp[0] = 0

5. 最终结果 #

根据我们之前定义的状态,dp[i] 表示为:跳到下标 i 所需要的最小跳跃次数。则最终结果为 dp[size - 1]

思路 1:动态规划(超时)代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def jump(self, nums: List[int]) -> int:
        size = len(nums)
        dp = [float("inf") for _ in range(size)]
        dp[0] = 0

        for i in range(1, size):
            for j in range(i):
                if j + nums[j] >= i:
                    dp[i] = min(dp[i], dp[j] + 1)

        return dp[size - 1]

思路 1:复杂度分析 #

  • 时间复杂度:$O(n^2)$。两重循环遍历的时间复杂度是 $O(n^2)$,所以总体时间复杂度为 $O(n^2)$。
  • 空间复杂度:$O(n)$。用到了一维数组保存状态,所以总体空间复杂度为 $O(n)$。

思路 2:动态规划 + 贪心 #

因为本题的数据规模为 $10^4$,而思路 1 的时间复杂度是 $O(n^2)$,所以就超时了。那么我们有什么方法可以优化一下,减少一下时间复杂度吗?

上文提到,在满足 j + nums[j] >= i 的情况下,dp[i] = min(dp[i], dp[j] + 1)

通过观察可以发现,dp[i] 是单调递增的,也就是说 dp[i - 1] <= dp[i] <= dp[i + 1]

举个例子,比如跳到下标 i 最少需要 5 步,即 dp[i] = 5,那么必然不可能出现少于 5 步就能跳到下标 i + 1 的情况,跳到下标 i + 1 至少需要 5 步或者更多步。

既然 dp[i] 是单调递增的,那么在更新 dp[i] 时,我们找到最早可以跳到 i 的点 j,从该点更新 dp[i]。即找到满足 j + nums[j] >= i 的第一个 j,使得 dp[i] = dp[j] + 1

而查找第一个 j 的过程可以通过使用一个指针变量 j 从前向后迭代查找。

最后,将最终结果 dp[size - 1] 返回即可。

思路 2:动态规划 + 贪心代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def jump(self, nums: List[int]) -> int:
        size = len(nums)
        dp = [float("inf") for _ in range(size)]
        dp[0] = 0

        j = 0
        for i in range(1, size):
            while j + nums[j] < i:
                j += 1
            dp[i] = dp[j] + 1

        return dp[size - 1]

思路 2:复杂度分析 #

  • 时间复杂度:$O(n)$。最外层循环遍历的时间复杂度是 $O(n)$,看似和内层循环结合遍历的时间复杂度是 $O(n^2)$,实际上内层循环只遍历了一遍,与外层循环遍历次数是相加关系,两者的时间复杂度和是 $O(2n)$,$O(2n) = O(n)$,所以总体时间复杂度为 $O(n)$。
  • 空间复杂度:$O(n)$。用到了一维数组保存状态,所以总体空间复杂度为 $O(n)$。

思路 2:贪心算法 #

如果第 i 个位置所能跳到的位置为 [i + 1, i + nums[i]],则:

  • 0 个位置所能跳到的位置就是 [0 + 1, 0 + nums[0]],即 [1, nums[0]]
  • 1 个位置所能跳到的位置就是 [1 + 1, 1 + nums[1]],即 [2, 1 + nums[1]]
  • ……

对于每一个位置 i 来说,所能跳到的所有位置都可以作为下一个起跳点,为了尽可能使用最少的跳跃次数,所以我们应该使得下一次起跳所能达到的位置尽可能的远。简单来说,就是每次在「可跳范围」内选择可以使下一次跳的更远的位置。这样才能获得最少跳跃次数。具体做法如下:

  1. 维护几个变量:当前所能达到的最远位置 end,下一步所能跳到的最远位置 max_pos,最少跳跃次数 setps
  2. 遍历数组 nums 的前 len(nums) - 1 个元素:
  3. 每次更新第 i 位置下一步所能跳到的最远位置 max_pos
  4. 如果索引 i 到达了 end 边界,则:更新 end 为新的当前位置 max_pos,并令步数 setps1
  5. 最终返回跳跃次数 steps

思路 2:贪心算法代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def jump(self, nums: List[int]) -> int:
        end, max_pos = 0, 0
        steps = 0
        for i in range(len(nums) - 1):
            max_pos = max(max_pos, nums[i] + i)
            if i == end:
                end = max_pos
                steps += 1
        return steps

思路 2:复杂度分析 #

  • 时间复杂度:$O(n)$。一重循环遍历的时间复杂度是 $O(n)$,所以总体时间复杂度为 $O(n)$。
  • 空间复杂度:$O(1)$。只用到了常数项的变量,所以总体空间复杂度为 $O(1)$。

参考资料 #

本站总访问量  次  |  您是本站第  位访问者