跳至主要內容

45. 跳跃游戏 II


45. 跳跃游戏 II

🟠   🔖  贪心 数组 动态规划  🔗 力扣open in new window LeetCodeopen in new window

题目

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

  • 0 <= j <= nums[i] and
  • i + j < n

Return the minimum number of jumps to reachnums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

Example 1:

Input: nums = [2,3,1,1,4]

Output: 2

Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [2,3,0,1,4]

Output: 2

Constraints:

  • 1 <= nums.length <= 10^4
  • 0 <= nums[i] <= 1000
  • It's guaranteed that you can reach nums[n - 1].

题目大意

给定一个长度为 n0 索引整数数组 nums。初始位置为 nums[0]

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处:

  • 0 <= j <= nums[i]
  • i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]

解题思路

思路一:贪心算法

贪心算法是一种通过在每一步选择中都采取当前状态下最优(即最有利)的选择,从而希望最终能够达到全局最优解的方法。

  1. 初始化

    • 初始化两个变量 maxPositionend,分别表示当前能够到达的最远位置和当前一步跳跃的结束位置,初始都为 0。
    • 初始化变量 steps 用来记录跳跃次数,初始为 0。
  2. 贪心策略

    • 在遍历数组的过程中,对于每个位置,更新 maxPosition 为当前位置能够到达的最远位置。
    • 当遍历到达 end 位置时,表示当前一步跳跃已经结束,将步数 steps 加一,并且更新 endmaxPosition
    • 如果遍历完数组时已经到达或超过了最后一个位置,返回当前步数 steps 即可。

复杂度分析

  • 时间复杂度O(n),其中 n 是数组的长度,只需要遍历数组一遍。

  • 空间复杂度O(1),使用了常数个变量才存储中间状态。


思路二:动态规划

  1. 定义状态dp[i] 表示从位置 nums[i] 跳到目标位置 nums[n - 1] 的最小跳跃次数。

  2. 状态转移方程

    • 对于每个位置 nums[i],我们需要考虑从当前位置跳跃到下一个位置 nums[i + j] 的所有可能性,其中 1 <= j <= nums[i]
    • 对于每个可能的跳跃步数 j,我们更新 dp[i]1 + dp[i + j],表示从当前位置跳跃一次,加上从下一位置 nums[i + j] 跳到目标位置 nums[n - 1] 的最小跳跃次数。
    • 最终,dp[0] 即为从起始位置 nums[0] 跳到目标位置 nums[n - 1] 的最小跳跃次数。
  3. 初始化:初始化数组 dp,长度为 n,初始值为 n,表示从任意位置跳到目标位置的最大跳跃次数为 n。最后一个位置到目标位置的距离为 0,所以 dp[n - 1] = 0

  4. 遍历求解:从数组倒数第二个位置开始向前遍历,更新 dp[i] 的值。

  5. 返回结果:返回 dp[0],即起始位置到目标位置的最小跳跃次数。

复杂度分析

  • 时间复杂度O(n^2),其中 n 是数组的长度。这是因为在每个位置 i,我们需要考虑从当前位置跳跃到下一个位置的所有可能性,这可能需要遍历该位置能够跳跃的所有可能步数,这一过程的时间复杂度为 O(nums[i]),而数组共有 n 个位置,因此总的时间复杂度为 O(n^2)

  • 空间复杂度O(n),因为我们使用了一个长度为 n 的数组 dp 来存储每个位置的最小跳跃次数。

动态规划解法在时间复杂度上可能较高,因为对于每个位置都需要遍历其能够跳跃的所有可能步数,但它能够有效地求解问题并给出正确答案。

代码

贪心算法
/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function (nums) {
	if (nums.length === 1) {
		return 0;
	}

	let steps = 0;
	let maxPosition = 0;
	let end = 0;

	for (let i = 0; i < nums.length - 1; i++) {
		maxPosition = Math.max(maxPosition, i + nums[i]);
		if (i === end) {
			steps++;
			end = maxPosition;
			if (end >= nums.length - 1) {
				break;
			}
		}
	}

	return steps;
};

相关题目

题号标题题解标签难度力扣
55跳跃游戏[✓]贪心 数组 动态规划🟠🀄️open in new window 🔗open in new window
1306跳跃游戏 III深度优先搜索 广度优先搜索 数组🟠🀄️open in new window 🔗open in new window
1871跳跃游戏 VII字符串 动态规划 前缀和 1+🟠🀄️open in new window 🔗open in new window
2297跳跃游戏 VIII 🔒 数组 3+🟠🀄️open in new window 🔗open in new window
2617网格图中最少访问的格子数 广度优先搜索 并查集 5+🔴🀄️open in new window 🔗open in new window
2770达到末尾下标所需的最大跳跃次数数组 动态规划🟠🀄️open in new window 🔗open in new window
2786访问数组中的位置使分数最大数组 动态规划🟠🀄️open in new window 🔗open in new window