45. Jump Game II

45. Jump Game IIopen 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].

题目大意

给定一个长度为 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]。

解题思路

思路一：贪心算法

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

初始化：
- 初始化两个变量 maxPosition 和 end，分别表示当前能够到达的最远位置和当前一步跳跃的结束位置，初始都为 0。
- 初始化变量 steps 用来记录跳跃次数，初始为 0。
贪心策略：
- 在遍历数组的过程中，对于每个位置，更新 maxPosition 为当前位置能够到达的最远位置。
- 当遍历到达 end 位置时，表示当前一步跳跃已经结束，将步数 steps 加一，并且更新 end 为 maxPosition。
- 如果遍历完数组时已经到达或超过了最后一个位置，返回当前步数 steps 即可。

思路二：动态规划

定义状态：dp[i] 表示从位置 nums[i] 跳到目标位置 nums[n - 1] 的最小跳跃次数。
状态转移方程：
- 对于每个位置 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] 的最小跳跃次数。
初始化：初始化数组 dp，长度为 n，初始值为 n，表示从任意位置跳到目标位置的最大跳跃次数为 n。最后一个位置到目标位置的距离为 0，所以 dp[n - 1] = 0。
遍历求解：从数组倒数第二个位置开始向前遍历，更新 dp[i] 的值。
返回结果：返回 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];
};

45. Jump Game II

# 45. Jump Game IIopen in new window

# 题目

# 题目大意

# 解题思路

# 思路一：贪心算法

# 思路二：动态规划

# 代码

# 相关题目

45. Jump Game IIopen in new window

题目

题目大意

解题思路

思路一：贪心算法

思路二：动态规划

代码

相关题目