[[435245]]

跳躍游戲

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

給定一個(gè)非負(fù)整數(shù)數(shù)組，你最初位于數(shù)組的第一個(gè)位置。

數(shù)組中的每個(gè)元素代表你在該位置可以跳躍的最大長(zhǎng)度。

判斷你是否能夠到達(dá)最后一個(gè)位置。

示例 1:

• 輸入: [2,3,1,1,4]
• 輸出: true
• 解釋: 我們可以先跳 1 步，從位置 0 到達(dá) 位置 1, 然后再?gòu)奈恢?1 跳 3 步到達(dá)最后一個(gè)位置。

示例 2:

• 輸入: [3,2,1,0,4]
• 輸出: false
• 解釋: 無(wú)論怎樣，你總會(huì)到達(dá)索引為 3 的位置。但該位置的最大跳躍長(zhǎng)度是 0 ， 所以你永遠(yuǎn)不可能到達(dá)最后一個(gè)位置。

思路

剛看到本題一開(kāi)始可能想：當(dāng)前位置元素如果是3，我究竟是跳一步呢，還是兩步呢，還是三步呢，究竟跳幾步才是最優(yōu)呢?

其實(shí)跳幾步無(wú)所謂，關(guān)鍵在于可跳的覆蓋范圍!

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

這個(gè)范圍內(nèi)，別管是怎么跳的，反正一定可以跳過(guò)來(lái)。

那么這個(gè)問(wèn)題就轉(zhuǎn)化為跳躍覆蓋范圍究竟可不可以覆蓋到終點(diǎn)!

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

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

局部最優(yōu)推出全局最優(yōu)，找不出反例，試試貪心!

如圖：

跳躍游戲

i每次移動(dòng)只能在cover的范圍內(nèi)移動(dòng)，每移動(dòng)一個(gè)元素，cover得到該元素?cái)?shù)值(新的覆蓋范圍)的補(bǔ)充，讓i繼續(xù)移動(dòng)下去。

而cover每次只取 max(該元素?cái)?shù)值補(bǔ)充后的范圍, cover本身范圍)。

如果cover大于等于了終點(diǎn)下標(biāo)，直接return true就可以了。

C++代碼如下：

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

總結(jié)

這道題目關(guān)鍵點(diǎn)在于：不用拘泥于每次究竟跳跳幾步，而是看覆蓋范圍，覆蓋范圍內(nèi)一定是可以跳過(guò)來(lái)的，不用管是怎么跳的。

大家可以看出思路想出來(lái)了，代碼還是非常簡(jiǎn)單的。

一些同學(xué)可能感覺(jué)，我在講貪心系列的時(shí)候，題目和題目之間貌似沒(méi)有什么聯(lián)系?

**是真的就是沒(méi)什么聯(lián)系，因?yàn)樨澬臒o(wú)套路!**沒(méi)有個(gè)整體的貪心框架解決一些列問(wèn)題，只能是接觸各種類型的題目鍛煉自己的貪心思維!