少年安得长少年
海波尚变为桑田
这种题目，基本就能考虑套dp了。
然后发现按照从上到下，从左到右进行递推，并不能推出什么关系。
一般这个时候就可以考虑反向递推了。
解法实现已经很多了，我这里解释一下很多人没讲清楚的东西。
其实骑士在经过每个房间时，存在两种状态，一种是进入房间 (i, j) 之前，一种是进入房间 (i, j) 之后。
这里我们用 dp[i][j] 表示在进入房间 (i, j) 之前应该拥有能达到右下角的最少的健康数。
就以题中矩阵为例：
-2 -3 3
-5 -10 1
10 30 -5
显然因为 dungeon[2][2] == -5，且经过右下角时，应该最少剩余1，所以在进入 dp[2][2] 前，至少应该拥有6点健康数，也就是 dp[2][2] == 6。
所以在不考虑边界的情况下，就可以得到递推公式：
dp[i][j] = min(dp[i + 1][j] - dungeon[i][j], dp[i][j + 1] - dungeon[i][j])
也就是经过房间 (i, j) 之后，可以往右，也可以往下，于是就从这两个点反推。
当然，因为每次进入房间前，和离开房间后，都必须保持健康点数大于1.
所以，考虑边界：
dp[i][j] = max(1, min(dp[i + 1][j] - dungeon[i][j], dp[i][j + 1] - dungeon[i][j]))
同时要考虑的边界还有最下面那行和最右边那列。
for (int i = m - 2; i >= 0; i--)
dp[i][n - 1] = max(1, dp[i + 1][n - 1] - dungeon[i][n - 1]);
for (int j = n - 2; j >= 0; j--)
dp[m - 1][j] = max(1, dp[m - 1][j + 1] - dungeon[m - 1][j]);
充分考虑情况后，代码如下：
class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
int m = dungeon.size();
int n = dungeon[0].size();
vector<vector<int>> dp(m, vector<int> (n, 0));
dp[m - 1][n - 1] = max(1, 1 - dungeon[m - 1][n - 1]);
for (int i = m - 2; i >= 0; i--)
dp[i][n - 1] = max(1, dp[i + 1][n - 1] - dungeon[i][n - 1]);
for (int j = n - 2; j >= 0; j--)
dp[m - 1][j] = max(1, dp[m - 1][j + 1] - dungeon[m - 1][j]);
for (int i = m - 2; i >= 0; i--) {
for (int j = n - 2; j >= 0; j--) {
dp[i][j] = max(1, min(dp[i + 1][j] - dungeon[i][j],
dp[i][j + 1] - dungeon[i][j]));
}
}
return dp[0][0];
}
};
