LeetCode 174 Dungeon Game：動態規劃求騎士最小初始血量

問題描述

M×N 地下城，騎士從左上角 (0,0) 出發，只能向右或向下移動，目標到達右下角 (M-1,N-1) 救公主。每個格子有數值：負數扣血，正數加血，0 無影響。騎士血量降至 0 或以下即死亡。求騎士最少需要多少初始血量才能成功救出公主。

動態規劃分析

定義 dp[i][j] 為從 (i,j) 到達終點所需的最小血量（進入該格子前的血量）。逆向思考：從終點反推起點。

狀態轉移

• 終點：dp[M-1][N-1] = max(1, 1 - dungeon[M-1][N-1])。
• 最後一行：只能向右，dp[M-1][j] = max(1, dp[M-1][j+1] - dungeon[M-1][j])。
• 最後一列：只能向下，dp[i][N-1] = max(1, dp[i+1][N-1] - dungeon[i][N-1])。
• 一般情況：dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])。

空間優化

只需一維陣列 dp[N]，從右下向左上滾動更新，空間 O(N)。

複雜度

• 時間：O(M×N)。
• 空間：O(N) (滾動陣列) 或 O(M×N)。

參考程式碼 (C++)

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

關鍵點總結

逆向 DP 避免了正向決策的不確定性。滾動陣列優化空間。注意血量至少為 1。