C++怎么解決地牢游戲問題

這篇文章主要講解了“C++怎么解決地牢游戲問題”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“C++怎么解決地牢游戲問題”吧！

地牢游戲

這道王子救公主的題還是蠻新穎的，我最開始的想法是比較右邊和下邊的數字的大小，去大的那個，但是這個算法對某些情況不成立，比如下面的情況：

如果按我的那種算法走的路徑為 1 -> 0 -> -2 -> 0 -> -3, 這樣的話騎士的起始血量要為5，而正確的路徑應為 1 -> -3 -> 3 -> 0 -> -3, 這樣騎士的騎士血量只需為3。無奈只好上網看大神的解法，發現統一都是用動態規劃 Dynamic Programming 來做，建立一個二維數組 dp，其中 dp[i][j] 用來表示當前位置 (i, j) 出發的起始血量，最先處理的是公主所在的房間的起始生命值，然后慢慢向第一個房間擴散，不斷的得到各個位置的最優的生命值。逆向推正是本題的精髓所在啊，仔細想想也是，如果從起始位置開始遍歷，我們并不知道初始時應該初始化的血量，但是到達公主房間后，我們知道血量至少不能小于1，如果公主房間還需要掉血的話，那么掉血后剩1才能保證起始位置的血量最小。那么下面來推導狀態轉移方程，首先考慮每個位置的血量是由什么決定的，騎士會掛主要是因為去了下一個房間時，掉血量大于本身的血值，而能去的房間只有右邊和下邊，所以當前位置的血量是由右邊和下邊房間的可生存血量決定的，進一步來說，應該是由較小的可生存血量決定的，因為較我們需要起始血量盡可能的少，因為我們是逆著往回推，騎士逆向進入房間后 PK 后所剩的血量就是騎士正向進入房間時 pk 前的起始血量。所以用當前房間的右邊和下邊房間中騎士的較小血量減去當前房間的數字，如果是負數或著0，說明當前房間是正數，這樣騎士進入當前房間后的生命值是1就行了，因為不會減血。而如果差是正數的話，當前房間的血量可能是正數也可能是負數，但是騎士進入當前房間后的生命值就一定要是這個差值。所以我們的狀態轉移方程是 dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])。為了更好的處理邊界情況，我們的二維 dp 數組比原數組的行數列數均多1個，先都初始化為整型數最大值 INT_MAX，由于我們知道到達公主房間后，騎士火拼完的血量至少為1，那么此時公主房間的右邊和下邊房間里的數字我們就都設置為1，這樣到達公主房間的生存血量就是1減去公主房間的數字和1相比較，取較大值，就沒有問題了，代碼如下：

解法一：

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size(), n = dungeon[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
        dp[m][n - 1] = 1; dp[m - 1][n] = 1;
        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);
            }
        }
        return dp[0][0];
    }
};

我們可以對空間進行優化，使用一個一維的 dp 數組，并且不停的覆蓋原有的值，參見代碼如下：

解法二：

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size(), n = dungeon[0].size();
        vector<int> dp(n + 1, INT_MAX);
        dp[n - 1] = 1;
        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                dp[j] = max(1, min(dp[j], dp[j + 1]) - dungeon[i][j]);
            }
        }
        return dp[0];
    }
};

感謝各位的閱讀，以上就是“C++怎么解決地牢游戲問題”的內容了，經過本文的學習后，相信大家對C++怎么解決地牢游戲問題這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！