C++跳躍游戲問題怎么解決

這篇文章主要介紹“C++跳躍游戲問題怎么解決”，在日常操作中，相信很多人在C++跳躍游戲問題怎么解決問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”C++跳躍游戲問題怎么解決”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
jump length is 0, which makes it impossible to reach the last index.

這道題說的是有一個非負整數的數組，每個數字表示在當前位置的最大跳力（這里的跳力指的是在當前位置為基礎上能到達的最遠位置），求判斷能不能到達最后一個位置，開始博主以為是必須剛好到達最后一個位置，超過了不算，其實是理解題意有誤，因為每個位置上的數字表示的是最大的跳力而不是像玩大富翁一樣搖骰子搖出幾一定要走幾。這里可以用動態規劃 Dynamic Programming 來解，維護一個一維數組 dp，其中 dp[i] 表示達到i位置時剩余的跳力，若到達某個位置時跳力為負了，說明無法到達該位置。接下來難點就是推導狀態轉移方程啦，想想啊，到達當前位置的剩余跳力跟什么有關呢，其實是跟上一個位置的剩余跳力（dp 值）和上一個位置新的跳力（nums 數組中的值）有關，這里新的跳力就是原數組中每個位置的數字，因為其代表了以當前位置為起點能到達的最遠位置。所以當前位置的剩余跳力（dp 值）和當前位置新的跳力中的較大那個數決定了當前能到的最遠距離，而下一個位置的剩余跳力（dp 值）就等于當前的這個較大值減去1，因為需要花一個跳力到達下一個位置，所以就有狀態轉移方程了：dp[i] = max(dp[i - 1], nums[i - 1]) - 1，如果當某一個時刻 dp 數組的值為負了，說明無法抵達當前位置，則直接返回 false，最后循環結束后直接返回 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，因為這里并不是很關心每一個位置上的剩余步數，而只希望知道能否到達末尾，也就是說我們只對最遠能到達的位置感興趣，所以維護一個變量 reach，表示最遠能到達的位置，初始化為0。遍歷數組中每一個數字，如果當前坐標大于 reach 或者 reach 已經抵達最后一個位置則跳出循環，否則就更新 reach 的值為其和 i + nums[i] 中的較大值，其中 i + nums[i] 表示當前位置能到達的最大位置，參見代碼如下：

解法二：

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;
    }
};

到此，關于“C++跳躍游戲問題怎么解決”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！