1、题目链接
174. 地下城游戏
2、题目分析
假如说我们正向推状态转移方程，很难推出来，因为这道题有“加血”的说法，只能依靠后面的值判断前面所需要的血量，也就是说，如果正向的dp表示从起点出发，到达（i，j）需要最少的血量，那么[i][j+1]也会影响dp[i][j]的值，所以不建议正向dp的做法，
dp[i][j]表示从[i][j]位置到终点的所需要的最低健康值，
假设dp[i][j]所需的最低健康值是x，那么他满足
x+dungeon[i][j]>=dp[i+1][j]或者 x+dungeon[i][j]>=dp[i][j+1]
那么状态转移方程就是 dp[i][j]=min(dp[i+1][j],dp[i][j+1])-dungeon[i][j]
但是当前的位置dungeon[i][j]是一个比较大的正数时，dp[i][j]的值可能会变为0或者负数，但是我们要
求dp[i][j]最小为1，所以我们可以这样写：
dp[i][j] = max(1, dp[i][j])
状态转移方程出来了，剩下的就简单了
倒序dp：
3、代码实现
class Solution { public: int calculateMinimumHP(vector<vector<int>>& dungeon) { int m = dungeon.size(), n = dungeon[0].size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX)); dp[m][n - 1] = dp[m - 1][n] = 1; // dp[i][j]表示从当前位置出发到达终点时所需的最低健康数 for (int i = m - 1; i >= 0; i--) for (int j = n - 1; j >= 0; j--) { dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]; dp[i][j] = max(1, dp[i][j]); } return dp[0][0]; } };
注意我们的dp数组，要多开一行和一列，并初始化，方便我们dp[i][j]的计算
dp[m][n - 1] = dp[m - 1][n] = 1;
在dp表最后⾯添加⼀⾏，并且添加⼀列后，所有的值都先初始化为⽆穷⼤，然后让
dp[m][n - 1] = dp[m - 1][n] = 1即可。
