45. 跳跃游戏 II

🟠   🔖  贪心 数组 动态规划  🔗 力扣 LeetCode

题目

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].

题目大意

给定一个长度为 n 的 0 索引整数数组 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. 初始化：

   • 初始化两个变量 maxPosition 和 end，分别表示当前能够到达的最远位置和当前一步跳跃的结束位置，初始都为 0。
   • 初始化变量 steps 用来记录跳跃次数，初始为 0。

2. 贪心策略：

   • 在遍历数组的过程中，对于每个位置，更新 maxPosition 为当前位置能够到达的最远位置。
   • 当遍历到达 end 位置时，表示当前一步跳跃已经结束，将步数 steps 加一，并且更新 end 为 maxPosition。
   • 如果遍历完数组时已经到达或超过了最后一个位置，返回当前步数 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;
};

动态规划

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function (nums) {
	const n = nums.length;
	// dp[i] 代表从 nums[i] 跳到 nums[n - 1] 的最小跳跃次数
	let dp = new Array(n).fill(n);
	dp[n - 1] = 0;
	for (let i = n - 2; i >= 0; i--) {
		let num = nums[i];
		for (let j = 1; j <= num; j++) {
			if (i + j <= n - 1) {
				dp[i] = Math.min(1 + dp[i + j], dp[i]);
			}
		}
	}
	return dp[0];
};

相关题目

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