路径问题（greedy）：地下城游戏

 题目描述：

恶魔们抓住了公主并将她关在了地下城 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

题目解析：

这道题是比较难的。这道题我们可以形象的理解为打怪游戏，骑士的血条是>0的，在迷宫打怪的过程中，骑士会消耗自己的血条。但是，在某个位置会有血包，会让骑士的血条增加。这道题给了一个二维数组，骑士从左上角到右下角，骑士的血条一定是大于等于某个值的，不然的话那还救什么公主。

通过对示例1的分析，发现骑士的血条值最低应为7。

算法原理：动态规划

状态表示：

（经验+题目要求）同学们可能会发现，这道题和上一道题一样（路径下降最小和），我们以某一个位置为结尾这一条经验是推不出状态转移方程的，感兴趣的同学可以去推导一下。这时，我们就不得不考虑其他的经验值了。既然以某一个位置为结尾推导不出，那我们不妨试一下，如果是以某一个位置为起点呢？

dp[i][j]表示：从[i,j]位置出发到达终点，所需要的最低健康点数（血条值）。

状态转移方程：（分情况讨论）

不论是往那边走，都满足x+dp[i][j]>=dp[i][j+1]或者x+dp[i][j]>=dp[i+1][j],可以得到x>=dp[i][j+1]-dp[i][j]或者x>=dp[i+1][j]-dp[i][j]。

往右走：dp[i][j+1]-dp[i][j]

往下走：dp[i+1][j]-dp[i][j]

最低健康点数（血条值）：min(sp[i][j+1],dp[i+1][j])-dp[i][j];

处理下负数情况：dp[i][j]=max(1,dp[i][j]);

初始化：

(考虑边界情况）由于之前我们都需要考虑下标的映射关系，所以就显得很麻烦，为了方便，这道题的初始化我们仅只初始化最下边一行和最右边一行（不会初始化的考虑无穷大和特殊值）。

填表顺序：

从下往上，从右往左。

返回值：

返回dp[0][0]

代码：

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+1][j],dp[i][j+1])-d[i][j];dp[i][j]=max(1,dp[i][j]);}}return dp[0][0];}
};