45. 跳跃游戏 II
45. 跳跃游戏 II
题目
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]
andi + 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
即可。
- 在遍历数组的过程中,对于每个位置,更新
复杂度分析
时间复杂度:
O(n)
,其中n
是数组的长度,只需要遍历数组一遍。空间复杂度:
O(1)
,使用了常数个变量才存储中间状态。
思路二:动态规划
定义状态:
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];
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
55 | 跳跃游戏 | [✓] | 贪心 数组 动态规划 | 🟠 | 🀄️ 🔗 |
1306 | 跳跃游戏 III | 深度优先搜索 广度优先搜索 数组 | 🟠 | 🀄️ 🔗 | |
1871 | 跳跃游戏 VII | 字符串 动态规划 前缀和 1+ | 🟠 | 🀄️ 🔗 | |
2297 | 跳跃游戏 VIII 🔒 | 栈 图 数组 3+ | 🟠 | 🀄️ 🔗 | |
2617 | 网格图中最少访问的格子数 | 栈 广度优先搜索 并查集 5+ | 🔴 | 🀄️ 🔗 | |
2770 | 达到末尾下标所需的最大跳跃次数 | 数组 动态规划 | 🟠 | 🀄️ 🔗 | |
2786 | 访问数组中的位置使分数最大 | 数组 动态规划 | 🟠 | 🀄️ 🔗 |