[LeetCode] 55. Jump Game 跳躍游戲

這道題說的是有一個非負(fù)整數(shù)的數(shù)組，每個數(shù)字表示在當(dāng)前位置的最大跳力（這里的跳力指的是在當(dāng)前位置為基礎(chǔ)上能到達(dá)的最遠(yuǎn)位置），求判斷能不能到達(dá)最后一個位置，開始博主以為是必須剛好到達(dá)最后一個位置，超過了不算，其實是理解題意有誤，因為每個位置上的數(shù)字表示的是最大的跳力而不是像玩大富翁一樣搖骰子搖出幾一定要走幾。這里可以用動態(tài)規(guī)劃 Dynamic Programming 來解，維護(hù)一個一維數(shù)組 dp，其中 dp[i] 表示達(dá)到i位置時剩余的跳力，若到達(dá)某個位置時跳力為負(fù)了，說明無法到達(dá)該位置。接下來難點就是推導(dǎo)狀態(tài)轉(zhuǎn)移方程啦，想想啊，到達(dá)當(dāng)前位置的剩余跳力跟什么有關(guān)呢，其實是跟上一個位置的剩余跳力（dp 值）和上一個位置新的跳力（nums 數(shù)組中的值）有關(guān)，這里新的跳力就是原數(shù)組中每個位置的數(shù)字，因為其代表了以當(dāng)前位置為起點能到達(dá)的最遠(yuǎn)位置。所以當(dāng)前位置的剩余跳力（dp 值）和當(dāng)前位置新的跳力中的較大那個數(shù)決定了當(dāng)前能到的最遠(yuǎn)距離，而下一個位置的剩余跳力（dp 值）就等于當(dāng)前的這個較大值減去1，因為需要花一個跳力到達(dá)下一個位置，所以就有狀態(tài)轉(zhuǎn)移方程了：dp[i] = max(dp[i - 1], nums[i - 1]) - 1，如果當(dāng)某一個時刻 dp 數(shù)組的值為負(fù)了，說明無法抵達(dá)當(dāng)前位置，則直接返回 false，最后循環(huán)結(jié)束后直接返回 true  即可，參見代碼如下：

解法一：

class Solution {
public:
    bool canJump(vector<int>& nums) {
        vector<int> dp(nums.size(), 0);
        for (int i = 1; i < nums.size(); ++i) {
            dp[i] = max(dp[i - 1], nums[i - 1]) - 1;
            if (dp[i] < 0) return false;
        }
        return true;
    }
};

其實這題最好的解法不是 DP，而是貪婪算法 Greedy Algorithm，因為這里并不是很關(guān)心每一個位置上的剩余步數(shù)，而只希望知道能否到達(dá)末尾，也就是說我們只對最遠(yuǎn)能到達(dá)的位置感興趣，所以維護(hù)一個變量 reach，表示最遠(yuǎn)能到達(dá)的位置，初始化為0。遍歷數(shù)組中每一個數(shù)字，如果當(dāng)前坐標(biāo)大于 reach 或者 reach 已經(jīng)抵達(dá)最后一個位置則跳出循環(huán)，否則就更新 reach 的值為其和 i + nums[i] 中的較大值，其中 i + nums[i] 表示當(dāng)前位置能到達(dá)的最大位置，參見代碼如下：

解法二：

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size(), reach = 0;
        for (int i = 0; i < n; ++i) {
            if (i > reach || reach >= n - 1) break;
            reach = max(reach, i + nums[i]);
        }
        return reach >= n - 1;
    }
};

到此這篇關(guān)于C++實現(xiàn)LeetCode(55.跳躍游戲)的文章就介紹到這了,更多相關(guān)C++實現(xiàn)跳躍游戲內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！