[LeetCode] 174. Dungeon Game 地牢游戲

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0's) or contain magic orbs that increase the knight's health (positive integers).

In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Write a function to determine the knight's minimum initial health so that he is able to rescue the princess.

For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.

Note:

• The knight's health has no upper bound.
• Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

這道王子救公主的題還是蠻新穎的，我最開始的想法是比較右邊和下邊的數(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] 用來表示當前位置 (i, j) 出發(fā)的起始血量，最先處理的是公主所在的房間的起始生命值，然后慢慢向第一個房間擴散，不斷的得到各個位置的最優(yōu)的生命值。逆向推正是本題的精髓所在啊，仔細想想也是，如果從起始位置開始遍歷，我們并不知道初始時應(yīng)該初始化的血量，但是到達公主房間后，我們知道血量至少不能小于1，如果公主房間還需要掉血的話，那么掉血后剩1才能保證起始位置的血量最小。那么下面來推導(dǎo)狀態(tài)轉(zhuǎn)移方程，首先考慮每個位置的血量是由什么決定的，騎士會掛主要是因為去了下一個房間時，掉血量大于本身的血值，而能去的房間只有右邊和下邊，所以當前位置的血量是由右邊和下邊房間的可生存血量決定的，進一步來說，應(yīng)該是由較小的可生存血量決定的，因為較我們需要起始血量盡可能的少，因為我們是逆著往回推，騎士逆向進入房間后 PK 后所剩的血量就是騎士正向進入房間時 pk 前的起始血量。所以用當前房間的右邊和下邊房間中騎士的較小血量減去當前房間的數(shù)字，如果是負數(shù)或著0，說明當前房間是正數(shù)，這樣騎士進入當前房間后的生命值是1就行了，因為不會減血。而如果差是正數(shù)的話，當前房間的血量可能是正數(shù)也可能是負數(shù)，但是騎士進入當前房間后的生命值就一定要是這個差值。所以我們的狀態(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];
    }
};

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

最新評論