恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。

有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。

为了尽快解救公主，骑士决定每次只 向右 或 向下 移动一步。

返回确保骑士能够拯救到公主所需的最低初始健康点数。

注意：任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。

示例 1：

输入：dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
输出：7
解释：如果骑士遵循最佳路径：右 -> 右 -> 下 -> 下 ，则骑士的初始健康点数至少为 7 。

示例 2：

输入：dungeon = [[0]]
输出：1

提示：

• m == dungeon.length
• n == dungeon[i].length
• 1 <= m, n <= 200
• -1000 <= dungeon[i][j] <= 1000

---

整体移动方向是从左上到右下，骑士走到第［i ,j］个格子需要的健康点数（血量）和第［i+１ ,j］（下一步向右走）/ 第［i,j+1］（下一步向下走）相关。因此很容易想到采取动态规划的方式。

正向dp

正向dp，即从王子（左上）向公主（右下）进行规划。先考虑如下这种简单情况：每个格子只扣除血量。

 计算dp［i,j］只需将dp［i+1,j］和dp［i,j+1］中更大的值加上当前［i,j］的值即可。

（注：上面描述的方式中dp中的值是负的，需要的血量取绝对值+1即可）

第一次dp：

第二次dp：

取得到了最终的需要血量 1 - 公主格子中的值 = 16点初始健康点。

 而题目中有的格子是可以回血（正）的。

在这种情况下我们继续考虑正向dp：

如上图所示，如果按照之前的思路，在 -3 和 -8 中我们将选择-3，但是在未来的格子中，存在-20这样一个炸弹值，因此实际上在 ［0,0］处选择 -8 是全局最有解。也就是说：

即使知道了 dp［i+1,j］和 dp［i,j+1］，也不能根据哪个大就挑哪个（上图第一步选择 -3 还是-8 ）。因为有可能 dp［i+1,j］ 处的耗血量大（-8），但后续全为加血。而 dp［i,j+1］甚至更深处 dp[i+1][j+1] 是更多的减血，选dp［i+1,j］才是全局最优。

以上是比较感性的认知。理性的描述如下：

首先要理解后效性的概念。后效性是动态规划中的一个关键概念，它指一个问题的最优解可以通过其子问题的最优解来构造。换句话说，一个子问题的最优解不会影响其他子问题的最优解。

后效性提供了这点好处：简化了问题的求解，因为我们可以专注于子问题的最优解，而不用考虑它们之间的相互作用。

由于正值的存在，若从正向dp，后面的正值会影响到前面的判断，恰恰破坏了后效性。

考虑刚刚的正向dp，在这个过程其实需要维护两个值：当前所需最小初始生命值和到当前位置的路径和。我们希望需要的最初生命值尽量小，而到当前的路径和尽可能大，产生了两个重要程度相同的参数，正是这一点，破坏了后效性。

（也看到有的资料中描述动态规划是需要无后效性的，这里应该是描述差异，重点在于子问题间不要产生相互作用，也不要产生后向依赖，至于定义出的名词，没什么关系）

注意，也不是说这类问题正向dp完全不能做，可以通过记忆化搜索+动态规划+逻辑完善是可以解决的，但代价实在太大，并且不是最优解。

因而采取反向dp的方式。

继续以上面的例子分析为什么反向dp就不会产生后向依赖的问题？

按照反向dp，第一步结果如上图所示，注意，增加血量不能为之前的损失提供帮助，只会对后续有帮助。因此从在反向dp的过程中如果遇到了计算值 > 0，例如-5 + 30时，需要设置为0，因为你要想能到这个格子，前面扣除的血量是需要的，而不能用后面的加血预先抵扣前面的扣血。

以上只是分析过程，重复这个过程到左上角就不在这里赘述了。

接下来看dp数组的构造以及状态转移方程。

首先这里区分dp数组和原数组dungeon[i][j]的概念。

这是两个数组，虽然dp是依靠原数组计算出的，但分成两个数组看起来更清晰。

考虑问题输出结果：骑士需要的最小血量，注意骑士血量是不能为0的，0就死了，所以最小是1。

那么走到dp［i,j］的血量和dp［i+1,j］还有dp［i,j+1］是什么关系？

dp［i,j］= max（min（dp［i+1,j］，dp［i,j+1］）-  dungeon［i,j］，1）

注意这里就是区分原数组和dp数组的好处了，dp数组描述的是：从（i，j）出发，到达终点需要最少的血量。因此要取dp［i+1,j］和dp［i,j+1］中的较小值。而反映在dungeon数组中可能取的就是较大值。

接下来边界条件如何确定？因为起点是右下角，而到这里之后，骑士最低血是1，那么就外扩一行，并将右下格相邻的两个设为1。

而对于其他最外层格子，我们不需要使用到他们，因为dp取的是较小值，所以把他们都设为最大数就不会用到了。

 按上述公式填入对应值：

注意这里为什么是1，也就是公式外层为什么套一层max函数？

因为上文有提到：

按照反向dp，第一步结果如上图所示，注意，增加血量不能为之前的损失提供帮助，只会对后续有帮助。因此从在反向dp的过程中如果遇到了计算值 > 0，例如-5 + 30时，需要设置为0，因为你要想能到这个格子，前面扣除的血量是需要的，而不能用后面的加血预先抵扣前面的扣血。

当时所说设置为0只是在分析，而基于题目要求，骑士最小生命值为1。

进而完善整个dp数组，得到左上角骑士值7：

 代码：

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