[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ù)字的大小，去大的那個(gè)，但是這個(gè)算法對(duì)某些情況不成立，比如下面的情況：

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

解法一：

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

我們可以對(duì)空間進(jìn)行優(yōu)化，使用一個(gè)一維的 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++實(shí)現(xiàn)LeetCode(174.地牢游戲)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)地牢游戲內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論