174. 地下城游戲https://leetcode.cn/problems/dungeon-game/description/

惡魔們抓住了公主并將她關在了地下城dungeon的右下角。地下城是由m x n個房間組成的二維網格。我們英勇的騎士最初被安置在左上角的房間里，他必須穿過地下城并通過對抗惡魔來拯救公主。騎士的初始健康點數為一個正整數。如果他的健康點數在某一時刻降至0或以下，他會立即死亡。有些房間由惡魔守衛，因此騎士在進入這些房間時會失去健康點數（若房間里的值為負整數，則表示騎士將損失健康點數）；其他房間要么是空的（房間里的值為0），要么包含增加騎士健康點數的魔法球（若房間里的值為正整數，則表示騎士將增加健康點數）。為了盡快解救公主，騎士決定每次只向右或向下移動一步。返回確保騎士能夠拯救到公主所需的最低初始健康點數。注意：任何房間都可能對騎士的健康點數造成威脅，也可能增加騎士的健康點數，包括騎士進入的左上角房間以及公主被監禁的右下角房間。

1. 輸入：dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]，輸出：7，解釋：如果騎士遵循最佳路徑：右 -> 右 -> 下 -> 下 ，則騎士的初始健康點數至少為7。
2. 輸入：dungeon = [[0]]，輸出：1。

提示：m == dungeon.length，n == dungeon[i].length；1 <= m, n <= 200；-1000 <= dungeon[i][j] <= 1000。

---

我們用動態規劃的思想來解決這個問題。

確定狀態表示：根據經驗和題目要求，我們有2個狀態表示的方案：

• 用dp[i][j]表示：從起點開始，到達[i, j]位置，所需的最低初始健康點數。
• 用dp[i][j]表示：從[i, j]位置開始，到達終點，所需的最低初始健康點數。

究竟選擇哪一種狀態表示呢？事實上，哪一種狀態表示能推導出狀態轉移方程，我們就選擇哪一種狀態表示。

推導狀態轉移方程：首先考慮前一種狀態表示。考慮最近的一步，要想到達[i, j]位置，只有2種情況：

• 先到達[i - 1, j]位置，再向下走一步，到達[i, j]位置。
• 先到達[i, j - 1]位置，再向右走一步，到達[i, j]位置。

如果能推出狀態轉移方程，那么狀態轉移方程一定形如dp[i][j] = f(dp[i - 1, j], dp[i, j - 1])。然而，[i, j]右下方的位置是有可能影響到dp[i][j]的。比如，如果右下方有一個房間是-1000，那么所需的初始健康點數就是一個很大的值；如果右下方都是正數，那么可能不需要很大的初始健康點數。也就是說，dp[i][j]和右下方的值相關，但是dp[i][j] = f(dp[i - 1, j], dp[i, j - 1])這個方程與右下方的值無關。從而，我們推導不出狀態轉移方程。

所以，我們選擇后一種狀態表示：用dp[i][j]表示：從[i, j]位置開始，到達終點，所需的最低初始健康點數。考慮最近的一步，要想從dp[i][j]位置出發到達終點，只有2種情況：

• 先向下走一步，到達[i + 1, j]位置，再從[i + 1, j]位置出發到達終點。所以，從[i, j]位置出發到達終點需要的最低初始健康點數dp[i][j]，在經歷了[i, j]房間后，健康點數變為dp[i][j] + dungeon[i][j]，而dp[i][j] + dungeon[i][j]必須至少是從[i + 1, j]位置出發到達終點所需要的最低初始健康點數dp[i + 1][j]，即dp[i][j] + dungeon[i][j] >= dp[i + 1][j]，從而dp[i][j] >= dp[i + 1][j] - dungeon[i][j]，又由于dp[i][j]表示最低初始健康點數，所以dp[i][j] = dp[i + 1][j] - dungeon[i][j]。
• 先向右走一步，到達[i, j + 1]位置，再從[i, j + 1]位置出發到達終點。同理可得此時dp[i][j] = dp[i][j + 1] - dungeon[i][j]。

從[i, j]位置出發到達終點所需要的最低初始健康點數，應該是上面2種情況的較小值，即dp[i][j] = min(dp[i + 1][j] - dungeon[i][j], dp[i][j + 1] - dungeon[i][j]) = min(dp[i + 1][j], dp[i][j + 1])?- dungeon[i][j]。

然而這個狀態轉移方程有個很大的漏洞。如果min(dp[i + 1][j], dp[i][j + 1]) <=?dungeon[i][j]，那么dp[i][j] =?min(dp[i + 1][j], dp[i][j + 1])?- dungeon[i][j] <= 0。然而血量是不能低于0的，所以我們還需要判斷一下，如果計算出來的dp[i][j] <= 0，那么dp[i][j] = 1。

綜上所述：狀態轉移方程為：dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1])?- dungeon[i][j])。

初始化：觀察狀態轉移方程，我們在計算dp表最后一行和最后一列的值時，會越界訪問。所以，我們要對其初始化。這里我們用增加輔助結點的方式來初始化。我們在dp表的最下面和最右邊分別加上一行一列輔助結點。接下來我們考慮，如何初始化輔助結點，才能保證后續的填表是正確的。我們把此時的dp表畫出來：

      ? *? *
? ? ? ? *
* * * * *

先考慮右下角的?位置。這個?位置表示，直接從dungeon的右下角出發，到達右下角，所需要的最低初始健康點數。顯然這個?位置的值只需要保證，在更新完處于dungeon的右下角的健康點數之后，其值依然大于等于1，也就是說，如果dungeon的右下角是正數，那么?位置的值是1；如果dungeon的右下角是負數，那么?位置的值是1減去dungeon的右下角的值（負負得正）。再觀察狀態轉移方程：dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1])?- dungeon[i][j])，我們發現，如果dp[i + 1][j] =?dp[i][j + 1] = 1，那么dp[i][j] = max(1, min(1, 1)?- dungeon[i][j]) =?max(1, 1 - dungeon[i][j])，1代表dungeon的右下角是正數的情況，1 - dungeon[i][j]代表dungeon的右下角是負數的情況，剛好符合預期。所以，對于右下角的?位置，我們要把它的下面和右邊的2個*位置的值初始化為1。

      ? *? *
? ? ? ? 1
* * * 1 *

接著考慮除了右下角的?位置之外，其余的?位置。觀察狀態轉移方程：?dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1])?- dungeon[i][j])，我們發現，dp[i + 1][j]和dp[i][j + 1]會涉及到輔助結點。我們只需要把這些輔助結點初始化為+∞，在計算min(dp[i + 1][j], dp[i][j + 1])時，輔助結點的值就不會影響到結果了。由于并沒有導致溢出風險的運算，我們用INT_MAX代表+∞即可。

綜上所述：我們在dp表的最下面和最右邊分別加上一行一列輔助結點，并且把[m - 1, n]和[m, n - 1]位置的值初始化為1，其余輔助結點初始化為INT_MAX。

填表順序：根據狀態轉移方程，dp[i][j]依賴于dp[i + 1][j]和dp[i][j + 1]，所以應從下往上，從右往左填表。

返回值：應返回dp表左上角的值，即dp[0][0]。

細節問題：由于新增了一行一列輔助結點，dp表的規模比dungeon的規模大一行一列，即dp表的規模為(m + 1) x (n + 1)。由于輔助結點是在dp表的右下方，并不影響下標的映射關系，所以dp表的[i, j]位置依然對應dungeon的[i, j]位置。

時間復雜度：O(m x n)，空間復雜度：O(m x n)。

class Solution {
public:int calculateMinimumHP(vector<vector<int>>& dungeon) {int m = dungeon.size(), n = dungeon[0].size();// 創建dp表vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));// 初始化dp[m - 1][n] = dp[m][n - 1] = 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];}
};