【Leetcode每日一题】动态规划 - 地下城游戏（难度⭐⭐⭐）（61）

1. 题目解析

题目链接：174. 地下城游戏

这个问题的理解其实相当简单，只需看一下示例，基本就能明白其含义了。

2.算法原理

一、状态表定义

在解决地下城游戏问题时，我们首先需要对状态进行恰当的定义。一个直观的想法是，从起点开始，到达[i, j]位置时所需的最低初始健康点数。然而，这样的定义会导致状态转移时面临困难，因为当前位置的健康点数会受到后续路径的影响。

为了解决这个问题，我们采用另一种状态定义方式：从[i, j]位置出发，到达终点时所需的最低初始健康点数。这样定义的好处在于，当我们在[i, j]位置时，后续的最佳状态已经确定，从而可以顺利地进行状态转移。

因此，我们定义状态表dp如下：dp[i][j]表示从[i, j]位置出发，到达终点时所需的最低初始健康点数。

二、状态转移过程

在[i, j]位置，玩家有两种选择：向右走或向下走。我们需要根据这两种选择来推导dp[i][j]的值。

向右走到达下一个位置，然后从该位置继续到达终点。根据状态定义，这要求我们在[i, j]位置的最低健康点数加上当前位置的消耗，应大于等于右边位置的最低健康点数。即：x + dungeon[i][j] >= dp[i][j + 1]。通过移项，我们得到x的一个可能取值：x >= dp[i][j + 1] - dungeon[i][j]。
向下走到达下一个位置，然后从该位置继续到达终点。同样地，我们要求[i, j]位置的最低健康点数加上当前位置的消耗，应大于等于下边位置的最低健康点数。即：x + dungeon[i][j] >= dp[i + 1][j]。通过移项，我们得到x的另一个可能取值：x >= dp[i + 1][j] - dungeon[i][j]。

为了得到最小的初始健康点数，我们取这两种情况下的最小值作为dp[i][j]的候选值。因此，状态转移方程为：dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]。

然而，需要注意的是，如果当前位置的dungeon[i][j]是一个较大的正数，那么dp[i][j]的值可能会变成0或负数，这意味着最低点数会小于1，导致玩家死亡。因此，我们需要对dp[i][j]进行修正，确保其值至少为1。修正后的状态转移方程为：dp[i][j] = max(1, dp[i][j])。

三、初始化

为了正确地进行状态转移，我们需要对dp表进行初始化。一个常用的技巧是在dp表的最前面添加一行和一列辅助节点。这些辅助节点的值需要保证后续填表是正确的。在本题中，我们可以将所有辅助节点的值初始化为无穷大，然后设置dp[m][n - 1] = dp[m - 1][n] = 1，其中m和n分别是地图的行数和列数。

四、填表顺序

根据状态转移方程，我们需要从下往上逐行填写dp表，每行从左往右进行填写。这样的填表顺序可以确保在计算每个位置的dp值时，其右侧和下方的位置已经计算完毕，从而可以利用这些已知值进行状态转移。

五、返回值

最后，根据状态表定义，我们需要返回dp[0][0]的值，即从起点出发到达终点时所需的最低初始健康点数。

3.代码编写

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