题目描述
题目链接：174.地下城游戏
这里解释一下为什么要这么假设，因为这正是符合我之前的博客介绍的：按照从起点开始，到达 [i, j] 位置的时候…的这类经验的状态表示，可以从中看出我们的最低初始血量是受到后面的影响的。
算法原理
1.状态表示（经验+题目）
- 这道题如果我们定义成：从起点开始，到达 [i, j] 位置的时候，所需的最低初始健康点数。那么我们分析状态转移的时候会有一个问题：那就是我们当前的健康点数还会受到后面的路径的影响。也就是从上往下的状态转移不能很好地解决问题。专业一点来说这涉及到后效性的概念，这里感性理解一下就好，后面的博客会深入讲解。
- 这个时候我们要换⼀种状态表示：从 [i, j] 位置出发，到达终点时所需要的最低初始健康点数。这样我们在分析状态转移的时候，后续的最佳状态就已经知晓。
综上所述，dp[i][j] 表示：从 [i, j] 位置出发，到达终点时所需的最低初始健康点数。
2.状态转移方程
根据最近的一步划分问题。
对于 dp[i][j] ，从 [i, j] 位置出发，下⼀步会有两种选择（为了方便理解，设 dp[i]
[j] 的最终答案是 x ）：
- 走到右边，然后走向终点
那么我们在 [i, j] 位置的最低健康点数加上这⼀个位置的消耗，应该要大于等于右边位置的最低健康点数，也就是：
x + dungeon[i][j] >= dp[i][j + 1] 。 通过移项可得： x >= dp[i][j + 1] - dungeon[i][j] 。因为我们要的是最小值，因此这种情况下的 x = dp[i][j + 1] - dungeon[i][j]； - 走到下边，然后走向终点那么我们在 [i, j] 位置的最低健康点数加上这⼀个位置的消耗，应该要大于等于下边位置的最低健康点数，也就是：
x + dungeon[i][j] >= dp[i + 1][j] 。 通过移项可得： x >= dp[i + 1][j] - dungeon[i][j] 。因为我们要的是最小值，因此这种情况下的 x = dp[i + 1][j] - dungeon[i][j]；
综上所述，我们需要的是两种情况下的最小值，因此可得状态转移方程为：
dp[i][j] = min(dp[i + 1][j],dp[i][j + 1]) - dungeon[i][j];
//这里减 dungeon[i][j] 不要放在min里面，会超出 int 的范围
//因为根据初始可知有些地方的值需要用到 INT_MAX
但是，如果当前位置的 dungeon[i][j] 是⼀个比较大的正数的话，dp[i][j] 的值可能变成 0 或者负数。也就是最低点数会小于 1 ，那么骑士就会死亡。因此我们求出来的 dp[i][j] 如果小于等于 0 的话，说明此时的最低初始值应该为 1 。处理这种情况仅需让 dp[i][j] 与 1 取⼀个最大值即可：dp[i][j] = max(1, dp[i][j])
3.初始化
可以在最前面加上⼀个辅助结点，帮助我们初始化。使用这种技巧要注意两个点：
- 辅助结点里面的值要保证后续填表是正确的；
- 下标的映射关系。
在本题中，在 dp 表最后面添加一行，并且添加⼀列后，所有的值都先初始化为INT_MAX，然后让 dp[m][n - 1] = dp[m - 1][n] = 1 即可。
4.填表顺序
根据状态转移方程，我们需要从下往上填每一行，每一行从右往左。
5.返回值
根据状态表示，我们需要返回 dp[0][0] 的值。
代码实现
C++
class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
// 1.创建一个dp表
int m = dungeon.size(), n = dungeon[0].size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
// 2.初始化
dp[m][n - 1] = dp[m - 1][n] = 1;
// 3.填表
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]) - dungeon[i][j];
dp[i][j] = max(1, dp[i][j]);
}
// 4.返回值
return dp[0][0];
}
};
Java
class Solution {
public int calculateMinimumHP(int[][] d) {
// 1. 创建 dp 表
// 2. 初始化
// 3. 填表
// 4. 返回值
int m = d.length, n = d[0].length;
int[][] dp = new int[m + 1][n + 1];
for (int j = 0; j <= n; j++)
dp[m][j] = Integer.MAX_VALUE;
for (int i = 0; i <= m; i++)
dp[i][n] = Integer.MAX_VALUE;
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] = Math.min(dp[i][j + 1], dp[i + 1][j]) - d[i][j];
dp[i][j] = Math.max(dp[i][j], 1);
}
return dp[0][0];
}
}