【Hot 100】45. 跳跃游戏 II

• 🙋‍♂️ 作者：海码007
• 📜 专栏：算法专栏
• 💥 标题：【Hot 100】45. 跳跃游戏 II
• ❣️ 寄语：书到用时方恨少，事非经过不知难！

引言

跳跃游戏 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;}
};