一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7
输出：28示例 2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下示例 3：
输入：m = 7, n = 3
输出：28示例 4：
输入：m = 3, n = 3
输出：6提示：
1 <= m, n <= 100- 题目数据保证答案小于等于
2 * 109
解题思路
下面以图片的形式展现解题思路：（这里需要纠正一下图中的 m 和 n，它们都等于 5，而不是图中写的 4，粗心大意写错了！）
class Solution {
public:
int uniquePaths(int m, int n) {
// 创建dp表，dp[i][j]表示到达该位置时，总共的路径方式
// 为了判断方便，我们给dp表多加一行一列的虚拟位
// 还有注意的是这道题是二维dp
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
// 初始化，因为我们要从非虚拟位的左上角开始走，为了让
// 这个左上角为1，我们需要在左上角的上面或者左边格子
// 初始化为1，这样子的话从左上角开始判断的时候，根据
// 状态转移方程才能得到左上角的值为1
dp[0][1] = 1;
// 填表，顺序从上到下，从左往右，因为最后要推导右下角那个位置
for(int i = 1; i <= m; ++i)
{
for(int j = 1; j <= n; ++j)
{
// 当前位置又上边和左边位置推导出来
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m][n];
}
};2、不同路径II（medium）
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1：
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右示例 2：
输入：obstacleGrid = [[0,1],[0,0]]
输出：1提示：
m == obstacleGrid.lengthn == obstacleGrid[i].length1 <= m, n <= 100obstacleGrid[i][j]为0或1
解题思路
这道题和上面唯一的区别就是多了障碍物，但其实整体的思路都是不变的！
如果走到了障碍物处，此时 dp[i][j] 其实就走不通了，也就是说 dp[i][j] = 0， 而如果走到了不是障碍物的位置，就算上面还是左边格子是障碍物，此时 dp[i][j] 更新到旁边的障碍物，得到的还是加上 0，所以没有什么影响！
这道题最需要注意的点其实下标的映射问题，因为我们给 dp 表多开了虚拟行列，所以是从下标为 1 开始到 m 或者 n 的，这样子对于题目给出的 obstacleGrid 数组来说是会越界的并且是错位的，所以访问它的时候需要给 i 和 j 下标都减去一才行，这个我们在上面那道题中其实体现的不是很明显，这道题反而体现的更好一些！
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
dp[0][1] = 1;
for(int i = 1; i <= m; ++i)
{
for(int j = 1; j <= n; ++j)
{
// 不是障碍物的时候才进行填表更新
// 如果是障碍物的话则没必要进行填写，因为走不到该位置
// 此外还要注意下标问题！！！
if(obstacleGrid[i-1][j-1] == 0)
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m][n];
}
};3、礼物的最大价值（medium）
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
示例 1:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物提示：
0 < grid.length <= 2000 < grid[0].length <= 200
解题思路
还是依旧按照我们的五部曲来！
- 状态表示
- 按照 “经验 + 题目要求”，我们还是遵循以
dp[i][j]结尾，然后巴拉巴拉的情况哈哈 - 所以结合题目可以设定
dp[i][j]表示到达 [i, j] 位置时的礼物最大价值
- 按照 “经验 + 题目要求”，我们还是遵循以
- 状态转移方程
- 我们根据一个经验：从最近的一步入手。可以看到题目要求只能向右和向下走，也就是说当前位置 [i, j] 是与 [i-1, j] 和 [i, j-1] 位置处有关系！
- 通过状态表示，我们可以清楚得到左边或者上面格子的礼物价值也是最大的，那么我们只要选出它们两个其中最大的那个，然后加上当前位置处的礼物价值，即为当前位置的礼物最大价值！
- 即状态转移方程：
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + gift[i-1][j-1]（至于这里为什么 gift 数组是下标减一，这和我们初始化是有关系的，请看下面！
- 初始化
- 因为我们在更新 dp 数组的时候，需要用到上面和左面格子，所以势必会有越界问题，所以还是一样，我们开一行一列的虚拟位置，这个时候就需要关注两个问题：
- 保证让非虚拟位置的数据更新正确，所以虚拟位置的值要选好
- 下标的映射关系
- 这道题我们只需要让虚拟位置都设为 0 即可，因为对于非虚拟位置的第一行和第一列来说，它们并不需要依赖于左上角的礼物价值，所以这道题的虚拟位置其实功能就很单一，就是为了防止越界！
- 因为我们在更新 dp 数组的时候，需要用到上面和左面格子，所以势必会有越界问题，所以还是一样，我们开一行一列的虚拟位置，这个时候就需要关注两个问题：
- 填表顺序
- 从上往下，从左往右
- 返回值
- 因为我们需要的是右下角的值，所以返回 dp 表的右下角的值即可！
class Solution {
public:
int maxValue(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> dp(m+1, vector<int>(n+1, 0)); // 多开一行一列作为虚拟位置
for(int i = 1; i <= m; ++i)
{
for(int j = 1; j <= n; ++j)
{
// 状态转移方程
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1];
}
}
return dp[m][n];
}
};4、下降路径最小和（medium）
给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。
下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。
示例 1：
输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]
输出：13
解释：如图所示，为和最小的两条下降路径示例 2：
输入：matrix = [[-19,57],[-40,-5]]
输出：-59
解释：如图所示，为和最小的下降路径提示：
n == matrix.length == matrix[i].length1 <= n <= 100-100 <= matrix[i][j] <= 100
解题思路
关于这⼀类题，由于我们做过类似的，因此「状态表示」以及「状态转移」是比较容易分析出来的。比较难的地⽅可能就是对于「边界条件」的处理。但其实只要弄明白了，那也不是很难！
首先就是状态表示，还是一样，我们以 dp[i][j] 结尾，然后巴拉巴拉。根据题目要求， dp[i][j] 表示到 [i, j] 位置处，此时下降路径最小和。
接着就是状态转移方程，题目说可以从某个位置处的 左上方、正上方、右上方 走到当前位置，所以我们当前位置就和这三个位置有关！以左上方为例，它走到当前位置的下降路径最小和，就是左上角位置的下降路径最小和加上当前位置数值，也就是说 dp[i][j] = dp[i-1][j-1] + matrix[i][j]，而对于正上方以及右上方都是一样的！
现在我们要取从上一个位置来的下降路径最小和，其实就是取上面三个位置的最小值，然后加上当前位置的数值即可！
状态转移方程：dp[i][j] = max(dp[i-1][j-1] , dp[i-1][j], dp[i-1][j+1]) + matrix[i][j]
然后就是初始化问题了，很显然，为了防止越界问题的麻烦，我们添加虚拟行列，但这次和上面题目的区别就是这道题需要多加两列，而不是加一列，因为这次我们当前位置的最近一步涉及到了三个位置，最后一个位置可能也会越界！
所以我们就多加一行和两列作为虚拟位置，如下图：
并且还要注意到的是，我们不能简简单单的说给虚拟行列都初始化为 0，仔细想一下，虽然非虚拟位置的第一行需要的就是原来的路径大小，也就是第一行虚拟位置设为 0 没问题，但是下面的虚拟行列呢❓❓❓
假设设为 0，那么看上图中的最后一行的红色星号位置，如果假设它的左上角是 0，那么如果此时它的正上方和右上方都大于 0，那么此时就错了，因为就会取到这个原本不应该被处理的 0，因为它只是作为边界。
所以为了防止这种会被取到的情况，我们将除了第一行虚拟位置以外的其它虚拟位置，都设为 INT_MAX，这样子就保证不会影响到其对正确路径的获取情况了！对于其它的边界点情况也是如此！
接着就是填表顺序，很明显，要遍历整个表，所以要从上到下，从左往右去填。
最后就是返回值，因为我们的最小结果在最后一行，所以我们需要去遍历最后一行查找最后一行的最小值返回即可！
class Solution {
public:
int getMin(int a, int b, int c) // 求最小值
{
a = min(a, b);
a = min(a, c);
return a;
}
int minFallingPathSum(vector<vector<int>>& matrix) {
int n = matrix.size();
vector<vector<int>> dp(n+1, vector<int>(n+2, INT_MAX)); // 多开两列，并且全部都初始化为INT_MAX
for(int i = 0; i <= n+1; ++i) // 将第一行初始化为0
dp[0][i] = 0;
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= n; ++j)
{
// 状态转移方程
dp[i][j] = getMin(dp[i-1][j], dp[i-1][j-1], dp[i-1][j+1]) + matrix[i-1][j-1];
}
}
// 返回最后一行的最小值
int tmp = INT_MAX;
for(int i = 1; i <= n; ++i)
{
tmp = min(dp[n][i], tmp);
}
return tmp;
}
};5、最小路径和（medium）
给定一个包含非负整数的 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_MAX
dp[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];
}
};6、地下城游戏（hard）
恶魔们抓住了公主并将她关在了地下城 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];
}
};