引言
跳跃游戏 II
- 🎈 题目链接：
- 🎈 做题状态：
dp解题
思路：
遍历nums数组，并且记录当前位置可以跳跃到的地方的最小步数，通过遍历 nums[i] 的值来更新每个位置的步数，并且需要记录最小步数。其实可以有一个优化技巧，就是记录minSteps数组此时更新到的最右侧边界索引。如果当前位置能超越这个索引就更新后面的步数值，如果超不过就不需要更新。
class Solution {
public:
int jump(vector<int>& nums) {
vector<int> minSteps(nums.size(), INT_MAX);
minSteps[0] = 0;
// 遍历nums，并更新每个位置跳跃所需要的最短距离。
for(int i = 0; i < nums.size()-1; ++i)
{
int step = nums[i]; // 记录当前可以跳跃的步数
for (int j = i + 1; j <= i + step && j < nums.size(); ++j)
{
minSteps[j] = min(minSteps[j], minSteps[i] + 1);
}
}
return minSteps[nums.size()-1];
}
};
贪心解题
贪心的思路理解起来还是有点费力的。
在每一次跳跃时，总是选择当前跳跃范围内能跳最远的位置，作为下一次跳跃的边界，以此保证跳跃次数最少。
虽然跳跃是“在到达边界 end 的时候触发”，但能跳多远，取决于之前所有点探索的最远跳跃距离 farthest；
换句话说：你起跳的位置未必是边界点本身，而是边界范围内跳得最远的那个位置。
👉 这正体现了贪心策略的精髓：不回头、只选择当前最优。
class Solution {
public:
int jump(vector<int>& nums) {
int steps = 0; // 最终要返回的跳跃次数
int end = 0; // 当前这一跳的边界（跳到这就得起跳）
int farthest = 0; // 从当前范围中能跳到的最远位置
// 注意：我们只遍历到 nums.size() - 2，因为最后一跳跳到终点时无需再跳
for (int i = 0; i < nums.size() - 1; ++i)
{
// 更新当前能跳到的最远位置
farthest = max(farthest, i + nums[i]);
// 如果到达当前跳跃的边界，就必须跳一次
if (i == end)
{
++steps; // 起跳！
end = farthest; // 重新设置下一跳的边界
}
}
return steps;
}
};