动态规划算法的欢乐密码(二)：路径问题

专栏：算法的魔法世界

个人主页：手握风云

一、例题讲解

1.1. 不同路径

题目要求是计算从网格的左上角（起点）到右下角（终点）的所有不同路径的数量。机器人每次只能向下或向右移动一步。如下图所示，在3*2的网格中，机器人可以“向右、向下、向下”，“向下、向下、向右”，“向下、向右、向下”一共三种路径。

根据题目要求，本题的状态表示为走到[i, j]为终点的位置时，一共有多少种走法。因为机器人只能向下或者向右走，那么我们要想知道[i, j]的路径数量，就需要直到从起点到达[i-1, j]的路径数和[i, j-1]的路径数，然后再向右走一步或者向下走一步就可以了。注意，这是只是走了一步，而不是走了一个路径。所以状态转移方程为dp[i][j] = dp[i-1][j] + dp[i][j-1]。根据状态转移方程，我们需要根据左侧和上侧的网格来计算，如下图所示的几个边界会出现越界的情况。我们仍然可以按照一维数组的方法增加虚拟节点。接下来就是要填写虚拟节点里的值，保证后面填表的结果是正确的。填表顺序从上到下填写每一行，从左到右填写每一列。

完整代码实现：

class Solution {public int uniquePaths(int m, int n) {// 创建一个二维数组dp，用于存储到达每个位置的路径数int[][] dp = new int[m + 1][n + 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];}
}

1.2. 不同路径 II

本题与上一题一样，计算不同的路径数，每次只能向右或向下移动一步，但某些网格是禁止通行的。
状态表示与上一题一样，同样是走到[i, j]为终点的位置时，一共有多少种走法。这里因为多了障碍物，如果有障碍物的网格，那么可到达的路径数就是0；如果没有障碍物，那么状态转移方程就是dp[i][j] = dp[i-1][j] + dp[i][j-1]。如果终点的左侧或者上侧有障碍物，我们根本过不来，路径数为0，最后的相加的结果也没影响。初始化与上一题的方法一样，我们只需要保证起点的值正确就可以。这里与上一题不同的是，上一题的参数是两个整数，这道题是一个二维数组，需要注意下标的映射，原始数组的下标与填表时的下标是[i-1][j-1]。填表顺序从上到下，每一行从左到右。

完整代码实现：

class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length;int n = obstacleGrid[0].length;// 创建一个二维数组dp，用于存储到达每个位置的路径数int[][] dp = new int[m + 1][n + 1];// 初始化dp[1][0]为1，表示从起点到第一列的路径数dp[1][0] = 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];}
}

1.3. 珠宝的最高价值

题目要求在一个二维矩阵中，从左上角开始，每次只能向右或向下移动，直到到达右下角，找出一条路径使得路径上珠宝的总价值最大。
首先根据题目要求，本题的状态表示为到达[i, j]位置时，此时珠宝的最大价值。状态表示就是通过最近的一步来分析问题，到达[i, j]的前一个位置：[i-1, j]、[i, j-1]的珠宝最大价值再加上当前珠宝的价值，所以状态转移方程dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]) + frame[i - 1][j - 1]。初始化的时候与上面一样，保证不越界，并且保证后面的填表是正确的，因为我们是要左侧和上面之中的最大值，因为珠宝的价值都是大于等于0的，所以所有的都初始化为0。填表顺序从上到下，每一行从左到右。

完整代码实现：

class Solution {public int jewelleryValue(int[][] frame) {// 获取框架的行数和列数int m = frame.length;int n = frame[0].length;// 创建一个二维数组dp，用于存储每个位置的最大珠宝价值int[][] dp = new int[m + 1][n + 1];// 遍历框架的每个位置for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {// 当前位置的最大珠宝价值等于当前位置的珠宝价值加上当前位置左边或上边的最大珠宝价值dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]) + frame[i - 1][j - 1];}}// 返回框架右下角的最大珠宝价值return dp[m][n];}
}

1.4. 下降路径最小和

给定一个包含整数的二维数组 matrix，要求找到从第一行下降到最后一行的最小路径和。每次下降只能从当前元素移动到下一行的左上、正下、右下三个方向之一。具体来说，对于矩阵中的每个元素matrix[i][j]，你可以选择移动到matrix[i+1][j-1]、matrix[i+1][j]或matrix[i+1][j+1]，并且需要保证这些移动是在矩阵的范围内。目标是找到从第一行任意元素开始，经过若干次下降后到达最后一行的路径中，路径和最小的值。

根据题目要求，本题的状态表示为dp[i][j]，到达[i,j]位置时的最小下降路径。接下来根据最近的一步划分问题，如下图所示，可以从A、B、C到达最后一行，那么此时的最小路径和分别为dp[i-1][j-1](表示为x)、dp[i-1][j](表示为y)、dp[i-1][j+1](表示为z)，到达最后一行的状态表示dp[i][j]为前一个位置的最小路径和再加上它本身，所以状态转移方程为dp[i][j]=min(x,y,z)+matrix[i][j]。

根据状态转移方程，下图中的几个位置会发生越界。我们可以将dp表新增一行二列，根据状态转移方程，新增前第一行dp表的值都为0，新增后第一行dp表的初始值也为0。为了不影响下一行的填表，必须保证最左侧和最右侧的两列不参与运算，我们可以将两列都初始化为无穷大。下标映射的时候，为了对应原始矩阵的下标，我们需要加上一行和两列，我们一开始就把dp表都初始化为无穷大，然后再把第一行改为0。填表的时候，从上往下即可，不用关心每一行的顺序。返回值要注意，我们只需返回最后一行的最小值即可。

完整代码实现：

class Solution {public int minFallingPathSum(int[][] matrix) {int n = matrix.length;// 创建一个二维数组dp，用于存储到达每个位置的最小路径和int[][] dp = new int[n + 1][n + 2];// 将dp的第一行和最后一行初始化为最大值，表示无法到达这些位置for (int i = 1; i <= n; i++) {dp[i][0] = dp[i][n + 1] = Integer.MAX_VALUE;}for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {// 计算到达当前位置的最小路径和dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i - 1][j - 1], dp[i - 1][j + 1])) + matrix[i - 1][j - 1];}}// 初始化最小路径和为最大值int ret = Integer.MAX_VALUE;// 遍历dp的最后一行，找到最小路径和for (int i = 1; i <= n; i++) {ret = Math.min(ret, dp[n][i]);}return ret;}
}

1.5. 最小路径和

给定一个包含非负整数的 m x n 网格 grid，找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。每次只能向下或者向右移动一步。返回一个整数，表示所有可能路径中的最小和。

根据题目要求，本题的状态表示为到达[i,j]位置时，最小的路径和dp[i][j]。根据最近的一步，到达这个终点位置的前一步为它的左侧和上方，那么状态转移方程dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]。根据状态转移方程，下图当中的几个位置会发生越界。为了不影响起点位置的值，我们可以将起点位置的左侧和上方都初始化为0，但起点位置的右上方不能初始化为0，因为起点位置的右侧必须要取最小值，所以我们可以将新增的都初始化为无穷大，再将dp[0][1]和dp[1][0]赋值为0。填表顺序为从上到下，每一行从左到右。返回值直接返回右下角的元素。

完整代码实现：

class Solution {public int minPathSum(int[][] grid) {// 获取网格的行数和列数int m = grid.length;int n = grid[0].length;// 创建一个二维数组dp，用于存储到达每个位置的最小路径和int[][] dp = new int[m + 1][n + 1];for (int i = 0; i <= m; i++) {dp[i][0] = Integer.MAX_VALUE;}for (int i = 0; i <= n; i++) {dp[0][i] = Integer.MAX_VALUE;}// 初始化dp数组的起点位置，表示从起点到起点的最小路径和为0dp[0][1] = dp[1][0] = 0;for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {// 到达当前位置的最小路径和等于到达上方位置和左方位置的最小路径和加上当前位置的值dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];}}return dp[m][n];}
}

1.6. 地下城游戏

给定一个二维的地下城，其中每个格子代表勇士的血量增减。勇士从左上角出发，需要到达右下角的公主所在的格子。勇士在任何时候的血量都不能小于1。请你计算出勇士初始需要的最小血量。

我们根据示例1推导一下初始血量：假设初始血量HP为3，才能走出第一个房间，但走不出第二个房间；假设HP为6时，能够走出前两个房间，接着吃血包恢复到5，但走到最后右下角房间时，血量为0，还是无法救出公主；因此初始血量必须为7。
根据前面几题的经验和题目要求：1. 以右下角为结尾，从起点出发到达[i, j]位置时的最低HP。但我们这样定义状态表示是不行的，因为根据示例1的分析，状态表示不光受到前面状态的影响，也会受到后面状态的影响，填表的时候也得需要后面路径选择的影响。2. 反过来，以左上角为起点，从[i, j]到达起点，所需最低的HP。

接下来根据最近的一步划分问题，设初始血量为x，当骑士向下走或者向右走的时候，我们需要保证他走出这个房间之后HP大于等于最低HP要求，也就是状态转移方程dp[i][j] = min(dp[i + 1][j] - dungeon[i][j], dp[i][j + 1] - dungeon[i][j])。但还有一个细节需要注意，如果dungeon[i][j]太大，一减成了负数，骑士提前死亡，无法吃到血包。所以我们还需要对max(dungeon[i][j],1)。

初始化的时候，根据状态转移方程，下图这些位置会越界，并且我们只需保证填表正确即可，不需要关注下标的映射关系。填表顺序从下往上填每一行，每一行从右往左。返回值dp[0][0]。

完整代码实现：

class Solution {public int calculateMinimumHP(int[][] dungeon) {// 获取地图的行数和列数int m = dungeon.length, n = dungeon[0].length;// 创建一个二维数组dp，用于存储从起点到每个点的最小生命值int[][] dp = new int[m + 1][n + 1];// 将dp数组的最后一行和最后一列初始化为最大值for (int i = 0; i <= n; i++) {dp[m][i] = Integer.MAX_VALUE;}for (int i = 0; i <= m; i++) {dp[i][n] = Integer.MAX_VALUE;}// 将dp数组的倒数第二行和倒数第二列初始化为1dp[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] = Math.min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j];// 如果当前点的最小生命值小于1，则将其设置为1dp[i][j] = Math.max(dp[i][j], 1);}}// 返回起点处的最小生命值return dp[0][0];}
}