题目描述

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

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

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

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

编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。

例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。

-2 (K)  -3      3
-5      -10     1
10      30      -5 (P)

说明

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

算法1

(二分答案 + 动态规划判定) $O(mn \log S)$

1. 可以看到骑士的起始健康值满足单调性，可以二分这个健康值，找到下界。
2. 二分时，通过动态规划来判定是否可以到达终点。
3. 动态规划的状态表示为 $f(i, j)$ 表示从起点到 (i, j)，所剩下的最大健康值。
4. 初始时 $f(0, 0) = init + dungeon[0][0]$，其余为 0。
5. 转移时，若 $f(i - 1, j) > 0$，则 $f(i, j) = \max(f(i, j), f(i - 1, j) + dungeon[i][j])$；若 $f(i, j - 1) > 0$，则 $f(i, j) = \max(f(i, j), f(i, j - 1)) + dungeon[i][j])$。
6. 最终判断 $f(n, m)$。

时间复杂度

• 二分答案时间复杂度为 $O(\log S)$，$S$ 为答案上限。
• 动态规划的状态数为 $O(mn)$，转移时间为常数，所以每次需要 $O(mn)$ 的时间判定。
• 故总时间复杂度为$O(mn \log S)$。

空间复杂度

• 需要额外 $O(mn)$ 的空间存储状态。

C++ 代码

class Solution {
public:
    bool check(int initial, vector<vector<int>>& dungeon) {
        int m = dungeon.size(), n = dungeon[0].size();
        vector<vector<int>> f(m, vector<int>(n, 0));

        f[0][0] = initial + dungeon[0][0];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                if (i > 0 && f[i - 1][j] > 0)
                    f[i][j] = max(f[i][j], f[i - 1][j] + dungeon[i][j]);

                if (j > 0 && f[i][j - 1] > 0)
                    f[i][j] = max(f[i][j], f[i][j - 1] + dungeon[i][j]);
            }

        return f[m - 1][n - 1] > 0;
    }

    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        const int INF = 1000000000;
        int l = 1, r = INF;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(mid, dungeon)) r = mid;
            else l = mid + 1;
        }

        return l;
    }
};

算法2

(动态规划) $O(mn)$

1. 此题不能直接从正向动态规划的原因是不确定起始点的值，但我们可以发现，到终点之后健康值为 $1$ 一定是最优的。
2. 可以考虑从终点到起点进行动态规划。
3. 设状态 $f(i, j)$ 表示从 $(i, j)$ 成功到达终点，$(i, j)$ 处需要具备的最少健康值。
4. 初始时，$f(m - 1, n - 1)$ 为 $- \max(dungeon(m - 1, n - 1), 0) + 1$，其余为正无穷。
5. 转移时，$f(i, j) = \min(f(i + 1, j) , f(i, j + 1)) - dungeon(i, j)$；如果 $f(i, j) \le 0$，表示道路上的补给实在太多了，但此时健康值不能小于 $0$，所以此时需要修正 $f(i, j) = 1$，即下限为 $1$。
6. 最终答案为 $f(0, 0)$。

时间复杂度

• 动态规划的状态数为 $O(mn)$，转移时间为常数，故总时间复杂度为 $O(mn)$。

空间复杂度

• 需要额外 $O(mn)$ 的空间存储状态数。

C++ 代码

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        const int INF = 1000000000;
        int m = dungeon.size(), n = dungeon[0].size();
        vector<vector<int>> f(m, vector<int>(n, INF));

        f[m - 1][n - 1] = max(-dungeon[m - 1][n - 1], 0) + 1;

        for (int i = m - 1; i >= 0; i--)
            for (int j = n - 1; j >= 0; j--) {
                if (i < m - 1)
                    f[i][j] = min(f[i][j], f[i + 1][j] - dungeon[i][j]);

                if (j < n - 1)
                    f[i][j] = min(f[i][j], f[i][j + 1] - dungeon[i][j]);

                f[i][j] = f[i][j] <= 0 ? 1 : f[i][j];
            }

        return f[0][0];
    }
};