[[435245]]

跳躍游戲

力扣題目鏈接：https://leetcode-cn.com/problems/jump-game

給定一個非負整數數組，你最初位于數組的第一個位置。

數組中的每個元素代表你在該位置可以跳躍的最大長度。

判斷你是否能夠到達最后一個位置。

示例 1:

• 輸入: [2,3,1,1,4]
• 輸出: true
• 解釋: 我們可以先跳 1 步，從位置 0 到達 位置 1, 然后再從位置 1 跳 3 步到達最后一個位置。

示例 2:

• 輸入: [3,2,1,0,4]
• 輸出: false
• 解釋: 無論怎樣，你總會到達索引為 3 的位置。但該位置的最大跳躍長度是 0 ， 所以你永遠不可能到達最后一個位置。

思路

剛看到本題一開始可能想：當前位置元素如果是3，我究竟是跳一步呢，還是兩步呢，還是三步呢，究竟跳幾步才是最優呢?

其實跳幾步無所謂，關鍵在于可跳的覆蓋范圍!

不一定非要明確一次究竟跳幾步，每次取最大的跳躍步數，這個就是可以跳躍的覆蓋范圍。

這個范圍內，別管是怎么跳的，反正一定可以跳過來。

那么這個問題就轉化為跳躍覆蓋范圍究竟可不可以覆蓋到終點!

每次移動取最大跳躍步數(得到最大的覆蓋范圍)，每移動一個單位，就更新最大覆蓋范圍。

貪心算法局部最優解：每次取最大跳躍步數(取最大覆蓋范圍)，整體最優解：最后得到整體最大覆蓋范圍，看是否能到終點。

局部最優推出全局最優，找不出反例，試試貪心!

如圖：

跳躍游戲

i每次移動只能在cover的范圍內移動，每移動一個元素，cover得到該元素數值(新的覆蓋范圍)的補充，讓i繼續移動下去。

而cover每次只取 max(該元素數值補充后的范圍, cover本身范圍)。

如果cover大于等于了終點下標，直接return true就可以了。

C++代碼如下：

class Solution { 
public: 
    bool canJump(vector<int>& nums) { 
        int cover = 0; 
        if (nums.size() == 1) return true; // 只有一個元素，就是能達到 
        for (int i = 0; i <= cover; i++) { // 注意這里是小于等于cover 
            cover = max(i + nums[i], cover); 
            if (cover >= nums.size() - 1) return true; // 說明可以覆蓋到終點了 
        } 
        return false; 
    } 
}; 

總結

這道題目關鍵點在于：不用拘泥于每次究竟跳跳幾步，而是看覆蓋范圍，覆蓋范圍內一定是可以跳過來的，不用管是怎么跳的。

大家可以看出思路想出來了，代碼還是非常簡單的。

一些同學可能感覺，我在講貪心系列的時候，題目和題目之間貌似沒有什么聯系?

**是真的就是沒什么聯系，因為貪心無套路!**沒有個整體的貪心框架解決一些列問題，只能是接觸各種類型的題目鍛煉自己的貪心思維!