C++如何實現跳躍游戲

這篇文章主要介紹“C++如何實現跳躍游戲”的相關知識，小編通過實際案例向大家展示操作過程，操作方法簡單快捷，實用性強，希望這篇“C++如何實現跳躍游戲”文章能幫助大家解決問題。

Jump Game 跳躍游戲

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

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++如何實現跳躍游戲”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識，可以關注億速云行業資訊頻道，小編每天都會為大家更新不同的知識點。