• 🙋?♂? 作者：海碼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;}
};