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

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

地牢游戲

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

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

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

解法二：

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++怎么解決地牢游戲問題”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對C++怎么解決地牢游戲問題這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關(guān)知識點的文章，歡迎關(guān)注！