LeetCode | 174 地下城游戏

题目地址：https://leetcode-cn.com/problems/dungeon-game/description/
初看这题的时候，觉得是动态规划，自然而然地想到从左上角开始递推，把起点固定在 (0, 0)，用 min_hp[r][c] 表示终点在 r + 1 行 c + 1 列时，起点所需最小的 HP，但是问题在于，在这种情况下如果我知道 min_hp[r - 1][j] 和 min_hp[i][j - 1]，其实是很难得到 min_hp[i][j] 的。举个例子：

当走到第 3 行第 3 列的时候，min_hp[2][1] 和 min_hp[1][2] 都为 2，由于当前格子为 -3，所以求得答案为 5，但正确答案是 3。尝试了加入 hp 数组保存当前 HP，不仅使程序更复杂，而且不能使程序变得正确。

这时候只能转换思路，固定终点，使 min_hp[r][c] 表示的是起点为第 r + 1 行第 c + 1 列时的最小初始 HP，问题就很好解决了，得到递推式：
min_hp[r][c] = max(min(min_hp[r + 1][c], min_hp[r][c + 1]) - dungeon[r][c], 1)

加上一些初始化处理之后，就得到了正确的程序：

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int rows = dungeon.size();
        int cols = dungeon[0].size();

        int min_hp[rows][cols];
        min_hp[rows - 1][cols - 1] = dungeon[rows - 1][cols - 1] < 0 ? -dungeon[rows - 1][cols - 1] + 1 : 1;

        for (int r = rows - 2; r >= 0; --r) 
            min_hp[r][cols - 1] = max(min_hp[r + 1][cols - 1] - dungeon[r][cols - 1], 1);

        for (int c = cols - 2; c >= 0; --c) 
            min_hp[rows - 1][c] = max(min_hp[rows - 1][c + 1] - dungeon[rows - 1][c], 1);

        for (int r = rows - 2; r >= 0; --r)
            for (int c = cols - 2; c >= 0; --c)
                min_hp[r][c] = max(min(min_hp[r + 1][c], min_hp[r][c + 1])  - dungeon[r][c], 1);

        return min_hp[0][0];

    }
};

这道题对于我这个在动态规划方面还不是很熟悉的新手提供了一个新的视角：动态规划的问题并不一定就是 dp[m][n]，有时候这样得不到递推式，这时候不妨转换方向，变换一个顺序来进行递推。