運用貪心思想解決跳躍游戲

文章目錄

• • 運用貪心思想解決跳躍游戲
  • Jump Game I
  • • 1.題目描述
    • 2.分析
    • 3.代碼
  • Jump Game II
  • • 1.問題描述
    • 2.分析
    • 3.動規代碼【超時】
    • 4.貪心代碼

Jump Game I

1.題目描述

2.分析

• 不知道讀者有沒有發現，有關動態規劃的問題，大多是讓你求最值的，比如最長子序列，最小編輯距離，最長公共子串等等等。這就是規律，因為動態規劃本身就是運籌學里的一種求最值的算法。
• 那么貪心算法作為特殊的動態規劃也是一樣，也一定是讓你求個最值。這道題表面上不是求最值，但是可以改一改：
• 請問通過題目中的跳躍規則，最多能跳多遠？如果能夠越過最后一格，返回 true，否則返回 false。
• 所以說，這道題肯定可以用動態規劃求解的。但是由于它比較簡單，下一道題再用動態規劃和貪心思路進行對比，現在直接上貪心的思路：

3.代碼

bool canJump(vector<int>& nums) {int n = nums.size();int farthest = 0;for (int i = 0; i < n - 1; i++) {// 不斷計算能跳到的最遠距離farthest = max(farthest, i + nums[i]);// 可能碰到了 0，卡住跳不動了if (farthest <= i) return false;}return farthest >= n - 1; }

• 你別說，如果之前沒有做過類似的題目，還真不一定能夠想出來這個解法。每一步都計算一下從當前位置最遠能夠跳到哪里，然后和一個全局最優的最遠位置 farthest 做對比，通過每一步的最優解，更新全局最優解，這就是貪心。

很簡單是吧？記住這一題的思路，看第二題，你就發現事情沒有這么簡單。。。

Jump Game II

1.問題描述

2.分析

現在的問題是，保證你一定可以跳到最后一格，請問你最少要跳多少次，才能跳過去。

• 我們先來說說動態規劃的思路，采用自頂向下的遞歸動態規劃，可以這樣定義一個 dp 函數：

// 定義：從索引 p 跳到最后一格，至少需要 dp(nums, p) 步 int dp(vector<int>& nums, int p);

• 我們想求的結果就是 dp(nums, 0)，base case 就是當 p 超過最后一格時，不需要跳躍：

if (p >= nums.size() - 1) {return 0; }

• 我們可以暴力窮舉所有可能的跳法，通過備忘錄 memo 消除重疊子問題，取其中的最小值最為最終答案：

3.動規代碼【超時】

vector<int> memo; // 主函數 int jump(vector<int>& nums) {int n = nums.size();// 備忘錄都初始化為 n，相當于 INT_MAX// 因為從 0 調到 n - 1 最多 n - 1 步memo = vector<int>(n, n);return dp(nums, 0); }int dp(vector<int>& nums, int p) {int n = nums.size();// base caseif (p >= n - 1) {return 0;}// 子問題已經計算過if (memo[p] != n) {return memo[p];}int steps = nums[p];// 你可以選擇跳 1 步，2 步...for (int i = 1; i <= steps; i++) {// 窮舉每一個選擇// 計算每一個子問題的結果int subProblem = dp(nums, p + i);// 取其中最小的作為最終結果memo[p] = min(memo[p], subProblem + 1);}return memo[p]; }

• 該算法的時間復雜度是 遞歸深度 × 每次遞歸需要的時間復雜度，即 O(N^2)，在 LeetCode上是無法通過所有用例的，會超時。

4.貪心代碼

• 貪心算法比動態規劃多了一個性質：貪心選擇性質。我知道大家都不喜歡看嚴謹但枯燥的數學形式定義，那么我們就來直觀地看一看什么樣的問題滿足貪心選擇性質。
• 剛才的動態規劃思路，不是要窮舉所有子問題，然后取其中最小的作為結果嗎？核心的代碼框架是這樣：

int steps = nums[p];// 你可以選擇跳 1 步，2 步...for (int i = 1; i <= steps; i++) {// 計算每一個子問題的結果int subProblem = dp(nums, p + i);res = min(subProblem + 1, res);}

• for 循環中會陷入遞歸計算子問題，這是動態規劃時間復雜度高的根本原因。
• 但是，真的需要【遞歸地】計算出每一個子問題的結果，然后求最值嗎？直觀地想一想，似乎不需要遞歸，只需要判斷哪一個選擇最具有【潛力】即可：

• 比如上圖這種情況，我們站在索引 0 的位置，可以向前跳 1，2 或 3 步，你說應該選擇跳多少呢？
• 顯然應該跳 2 步調到索引 2，因為 nums[2] 的可跳躍區域涵蓋了索引區間 [3..6]，比其他的都大。如果想求最少的跳躍次數，那么往索引 2 跳必然是最優的選擇。
• 你看，這就是貪心選擇性質，我們不需要【遞歸地】計算出所有選擇的具體結果然后比較求最值，而只需要做出那個最有【潛力】，看起來最優的選擇即可。
• 繞過這個彎兒來，就可以寫代碼了

int jump(vector<int>& nums) {int n = nums.size();int end = 0, farthest = 0;int jumps = 0;for (int i = 0; i < n - 1; i++) {farthest = max(nums[i] + i, farthest);if (end == i) {jumps++;end = farthest;}}return jumps; }

結合剛才那個圖，就知道這段短小精悍的代碼在干什么了：

• i 和 end 標記了可以選擇的跳躍步數，farthest 標記了所有選擇 [i..end] 中能夠跳到的最遠距離，jumps記錄了跳躍次數。
• 本算法的 時間復雜度 O(N)，空間復雜度 O(1)， 可以說是非常高效，動態規劃都被吊起來打了。
• 至此，兩道跳躍問題都使用貪心算法解決了。

總結

以上是生活随笔為你收集整理的运用贪心思想解决跳跃游戏的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。