在這個算法題中，我們將看到貪心算法的應用，今天要講的是LeetCode的第55號題目，Jump Game，這個題目是什麼意思呢？
給定一個非負數的數組，最初我們在第一個數字的位置上，數組中的每一個數字表示在當前的位置上你最多可以跳多遠，題目要求我們確定能否跳到數組中的最後一個數。
比如給定數組[2,3,1,1,4]，你的代碼應該返回true，這其中一個可能的跳躍方式是從2跳到3，然後從3跳到4；當然從2開始以一次一步的方式也可以跳到最後。
而給定數組[3,2,1,0,4]，那麼你的函數應該返回false，在這種情況下無論你用什麼方式都不可能從3跳到最後的4。
那麼我們該怎樣解決這個問題呢？
有的同學會覺得的這個問題不好解決，原因就在於給定一個位置，假設這個位置上的數字是6，也就是說從這個位置開始，你可以選擇跳一步、也可以是兩部、三步、四步、五步或者六步，有這麼多可能性你該跳多少步呢？
順著這個思路走下去的話，那麼你只能把每一種可能性都試一遍了，還是以上圖為例，從該位置開始有6種可能性，那麼我們依次遍歷每一個種可能的選擇，各種遍歷方式的組合數是非常巨大的，因此這種思路不可行。
正著走不通，那麼讓我們反向思考一下。
這個問題的反向思考是基於這樣的一種觀察，也就是，如果數組中有某個位置無法到達，那麼我們就無法跳到最後一個節點，這是顯而易見的，因為如果能跳到最後一個節點的話，那麼我們必然要經過數組中的所有節點。換句話說就是如果我們能跳到最後一個節點的話，那麼我們必然能跳到數組中任意一個節點。
有了這樣的分析實際上就非常簡單了，我們之前在很多個算法題目中都說過，有時解決一個通用的問題比解決一個具體的問題思考起來要簡單，在這裡具體的那個問題就是判斷是否能跳到最後一個節點，而通用的那個問題就是能否跳到數組中任意一個節點，在這裡我們就來思考在給定條件下能否跳到數組中任意一個節點，如果可以的話那麼我們的函數應該返回true，否則返回false。
我們還是從最簡單的情況一步一步來分析。
對於數組[2,3,1,1,4]，首先我們會被放到2這個位置，接下來我們判斷能否跳到3？
那麼從2能否跳到3呢？答案很簡單，當然是可以的，為什麼呢？因為從2跳到3隻需要一步，而第一個位置我們最遠可以跳兩步，因此我們可以跳到3：
這樣我們來到了數組中的第二個數，也就是3，接下來就比較有意思了。
此時我們的任務就是判斷從節點3能否跳到節點1，那麼可以跳到嗎？
答案是顯而易見的，當然可以跳到，為什麼呢？因為在當前位置上我們可以最多跳3步，而從3跳到1隻需要一步，那麼如果當前位置上的數不是3而是0呢？
那麼我們還能跳到1嗎？答案是可以的，因為雖然我們不能從0跳到1，但是可以從2直接跳到1，從這兩種情況下你能得到什麼啟示？
以上兩種情況給我的啟示就是，能否跳到當前位置取決於當前位置之前的所有位置上的步數，有的同學會說這不是廢話嗎，是的，這是一句廢話，這句廢話會引導我們進一步思考，那就是這到底是怎麼的取決呢?
讓我們再次回到數組[2,3,1,1,4]的例子，從2可以跳到1，從3也可以跳到1，但是2最多可以跳到1，超出0步，而3最多可以跳到4，超過了1這個位置兩步，如圖所示：
那麼這張圖告訴我們什麼呢？是什麼樣的條件決定了能不能跳到當前位置呢？
如果我們能夠保證從在此位置之前任意一個位置(前提是我們可以從數組開頭跳到這些位置)起跳能跳到或跳過當前位置，那麼我們就可以確定可以從數組開頭跳到當前位置。
因此我們需要記下在該位置之前的所有位置起跳能超過當前位置的最大步數，只要這個最大步數經過每一個位置時都大於0，那麼我們就能確定一定可以從開頭跳到最後。而這本質上就是貪心算法，貪心算法的思想是我們總是在當前就做出最好的選擇，而不是從整體上加以考慮。
上述結論比較拗口，舉個例子你就明白啦，我們還是以[2,3,1,1,4]為例來說明。
最開始我們在位置2上，此時我們可以認為從位置2起跳可以超過當前位置2步，因此最大步數是2，我們將這個最大步數記為max_step，也就是能超過當前位置的最大步數，我們的任務就是要保證在每個位置max_step都要大於0，這樣我們就一定能到達最後，如圖所示：
接下來是位置3，此時我們需要將max_step減1，此時max_step為1是大於0的，因為我們向前走了一步。我們可以選出從3開始起跳，從而能超過3這個位置3步，也可以選擇使用max_step的起跳位置，也就是2，因此這個最大步數就是max_step = max(3, max_step-1)，這時max_step就是3。
接下來是位置1，同樣將max_step減1，此時max_step為2是大於0的，在這裡我們可以選擇從1這個位置起跳，也可以選擇使用max_step的起跳位置，也就是位置3，這樣我們又得到了能新的max_step，即max_step = max(1, max_step-1)。
重複上述過程直到數組最後，如果中途發現max_step已經等於0了，那麼說明我們無法從數組開頭跳到最後。
基於上述分析，代碼就很簡單了。
bool canJump(vector<int>& nums) { int len = nums.size(); if(len == 0 || len == 1) return true; int step=nums[0]; for(int i=0;i<len-1;i++){ step = max(step-1,nums[i]); if(step<=0) return false; } return true; }怎麼樣，有了仔細的分析，代碼是不是不要太簡單？
在本文中我們首次見到了貪心算法，貪心算法在每次做決策時總是選擇在當前看來最好的那個，值得注意的是，不是所有問題都適用於貪心算法，那麼什麼樣的問題才適用此算法呢，現在就去講解該理論的話可能理解不會那麼深刻，在後續文章中我們還會遇到該算法，見得多了你自然就會明白什麼樣的問題可以用貪心算法，到那時我們再來詳解講解該理論。