【动态规划：路径问题】最小路径和 地下城游戏
最小路径和（medium）
64. 最小路径和
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
**说明：**每次只能向下或者向右移动一步。
示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 2000 <= grid[i][j] <= 100
解题思路
首先还是状态表示，依照路径问题的经验和题目要求，可以很容易的设定 dp[i][j] 表示到达 [i, j] 位置时的最小路径和。
接着就是状态转移方程，根据最近一步来推导的话，和 [i, j] 有关系的就是 [i-1, j] 和 [i, j-1] 这两格了，以前者为例，dp[i-1][j] 表示到达 [i-1, j] 位置时候的最小路径和，那么 dp[i, j] 想得到最小路径和，不就是 用 [i-1, j] 的最小路径和，加上 [i, j] 当前的大小 吗，很简单明了，对于 [i, j-1] 也同样如此！
既然要的是最小的路径和，我们只需要取 dp[i-1][j] 和 dp[i][j-1] 中小的那个加上当前的大小即可！
所以状态转移方程为：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
然后还是初始化问题，因为我们要给表格加上虚拟行列，并且因为我们的状态转移方程是根据左边和上边格子得到的，这样子的话我们只需要多加一行一列，放在最上边和最左边这一行一列作为虚拟行列！
现在考虑两个问题，①虚拟行列的初始值不能影响后面填表的正确；②下标的映射关系。
其实最重要的还是第一个，因为我们在左上角开始遍历，需要让 dp[1][1] 得到的还是原来 gird 中的值，所以 得让 dp[0][1] 或者 dp[1][0] 为 0，保证加的时候加 0，就不会有影响了，而 其它位置都设为 INT_MAX，因为其它边界位置其实是不想收到这个虚拟行列的影响的，只希望收到附近的非虚拟位置的影响，所以用 INT_MAX 的时候进行最小值判断就不会取到它了！
填表顺序就是从上往下，从左往右！
最后返回的就是右下角的值也就是到达右下角的最小路径和！
class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int m = grid.size();int n = grid[0].size();vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX)); // 多开一行一列给虚拟行列，都设为INT_MAXdp[0][1] = 0; // 初始化虚拟位置for(int i = 1; i <= m; ++i){for(int j = 1; j <= n; ++j){dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1];}}return dp[m][n];}
};
地下城游戏（hard）
174. 地下城游戏
恶魔们抓住了公主并将她关在了地下城 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.lengthn == dungeon[i].length1 <= m, n <= 200-1000 <= dungeon[i][j] <= 1000
解题思路
这道题乍一看和上面几道路径题好像差不多，但其实这道题隐藏很多细节，稍不注意就出错，至少我是这样子的！为什么这么说呢❓❓❓
按我们上面做题的经验来看，我们都是以 [i, j] 为结尾怎么这么样这种情况，但是在这道题中，这种状态表示其实是不正确的，是推导不出来的，我们来举个例子：
注意：上图中的例子只是为了表达这种状态表示是错误的，其实例子的一些细节是错误的，注意即可！
所以我们就得改变一下思考方式，考虑从后面往前推导，也就是说以 [i, j] 为起点怎么怎么样这种情况，其实通过后面讲解会看到这样子是行得通的！
所以我们的状态表示 dp[i][j] 表示以 [i, j] 为起点，到达终点也就是右下角的最低健康点数！
也就是说现在我们推导的就是 dp[0][0] 了，那么就得 从后往前推导。
接着就是状态转移方程，既然是从后往前推导，那么肯定是和当前格子的右边或者下边有关系。解释如下图：
除此之外，上图中还解释了初始化的问题，并且我们并不需要去关心下标映射的问题，因为我们的虚拟行列是开在最后一行和最后一列！
填表的顺序的话，就是从下往上，每行从右往左！
返回值就是左上角的值！
这样子就结束了吗❓❓❓
结束就错了，还有一个细节我们没有处理！仔细想一下上面的状态转移方程，其中是涉及到了减法，要是遇到一种情况，就是 dungeon[i][j] 是一个正数，也就相当于这道题的一个加血点，如果它很大，导致减完之后得到的是一个负数，那么 dp[i][j] 是一个负数肯定是错误的啊，它表示的是最小健康点数，小于等于 0 不就挂了吗对不对！
所以我们必须处理一下，为了让其减去一个很大的负数之后还能得到一个最小的健康点数，我们想到的就是 1，所以我们在执行完状态转移方程之后还必须做一次判断，或者直接处理这个数，使得 dp[i][j] 不会成为一个负数，如果是负数了，就让它变成最小的健康点数 1 即可，代码如下：
dp[i][j] = max(1, dp[i][j]);
class Solution {
public:int calculateMinimumHP(vector<vector<int>>& dungeon) {int m = dungeon.size();int n = dungeon[0].size();vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX)); // 加入虚拟行列dp[m][n-1] = 1; // 将右下角的最近一步初始化为1，这样子的话保证了初始健康点数的q'z// 从下往上，从右往左填表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];}
};