174. 地下城游戏

链接: 174. 地下城游戏

恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。

有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。

为了尽快解救公主，骑士决定每次只 向右 或 向下 移动一步。

返回确保骑士能够拯救到公主所需的最低初始健康点数。

注意：任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。

题解

dp: 正难则反

• https://leetcode.cn/problems/dungeon-game/solutions/326171/di-xia-cheng-you-xi-by-leetcode-solution

如果按照从左上往右下的顺序进行动态规划，我们无法直接确定到达的方案，因为有两个重要程度相同的参数同时影响后续的决策。也就是说，这样的动态规划是不满足「无后效性」的。

于是我们考虑从右下往左上进行动态规划, 定义: $dp[i][j]$ 是 [i][j] -> [n][m] 的最小初始值

• 换句话说，当我们到达坐标 $(i,j)$ 时，如果此时我们的路径和不小于 $dp[i][j]$，我们就能到达终点。

• 这样一来，我们就无需担心路径和的问题，只需要关注最小初始值。对于 $dp[i][j]$，我们只要关心 $dp[i][j+1]$ 和 $dp[i+1][j]$ 的最小值 $minn$。记当前格子的值为 $dungeon(i,j)$，那么在坐标 $(i,j)$ 的初始值只要达到 $minn−dungeon(i,j)$ 即可。同时，初始值还必须大于等于 $1$。这样我们就可以得到状态转移方程: $dp[i][j]=max(min(dp[i+1][j],dp[i][j+1])−dungeon(i,j),1)$

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int n = dungeon.size(), m = dungeon[0].size();
        vector<vector<int>> f(n + 1, vector<int>(m + 1, 1e9));
        f[n][m - 1] = f[n - 1][m] = 1;
        // 正难则反
        for (int i = n - 1; i >= 0; --i) {
            for (int j = m - 1; j >= 0; --j) {
                f[i][j] = max(min(
                    f[i + 1][j],
                    f[i][j + 1]
                ) - dungeon[i][j], 1);
            }
        }
        return f[0][0];
    }
};

C++