动态规划课堂2-----路径问题

引言：

例题1：不同路径

例题2：不同路径II

例题3：礼物的最⼤价值

例题4：下降路径最⼩和

例题5：最小路径和

结语：

引言：

在学习完动态规划斐波那契数列模型后，相信大家对动态规划已经有了一定的了解，下面我们继续深入学习动态规划的路径问题，我们一般的解题步骤还是1. 状态表示，2.状态转移方程，3.初始化，4.填表顺序，5.返回值。在写代码时一定要把这5步考虑清楚再写代码，写代码的步骤为1.创建 dp表2.初始化3.填表4.返回值。

例题1：不同路径

链接：不同路径

题目简介：

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

解法（动态规划）：

1. 状态表示：

对于这种「路径类」的问题，我们的状态表⽰⼀般有两种形式：

（1）从[i, j] 位置出发到终点有几种路径。

（2）从起始位置出发，到达[i, j] 位置有几种路径。

本题我们选择第二种，dp[i][j] 表示：⾛到[i, j] 位置处，⼀共有多少种⽅式。

2.状态转移方程

简单分析⼀下。如果dp[i][j] 表⽰到达[i, j] 位置的⽅法数，那么到达[i, j] 位置之前的⼀⼩步，有两种情况：

（1）从[i, j] 位置的上⽅（ [i - 1, j] 的位置）向下⾛⼀步，转移到[i, j] 位置

（2）从[i, j] 位置的左⽅（ [i, j - 1] 的位置）向右⾛⼀步，转移到[i, j] 位置。

由于我们要求的是有多少种⽅法，因此状态转移⽅程就呼之欲出了： dp[i][j] = dp[i - 1] [j] + dp[i][j - 1] 。

3.初始化

使用辅助结点。

注意点：（1）辅助结点⾥⾯的值要「保证后续填表是正确的」（2）下标的映射关系。在本题中，「添加⼀⾏」，并且「添加⼀列」后，只需将dp[0][1] 的位置初始化为1 即可。

4.填表顺序

根据「状态转移⽅程」的推导来看，填表的顺序就是「从上往下」填每⼀⾏，在填写每⼀⾏的时候「从左往右」。

5.返回值

根据「状态表⽰」，我们要返回dp[m][n]（添加了一个辅助节点）的值。

代码如下：

动态规划编写代码的步骤比较固定，上面那5步是想好思路，下面这4步是编写代码的步骤。

class Solution {public int uniquePaths(int m, int n) {//1.创建dp表//2.初始化//3.填表//4.返回值int[][] dp = new int[m + 1][n + 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];}
}

时间复杂度：O（n * m）

空间复杂度：O（n * m）

例题2：不同路径II

链接：不同路径II

题目简介：

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

解法（动态规划）：

本题是例题一的进阶版，但是两题的解题步骤是类似的不同的地方在于状态转移方程。[i - 1, j] 与[i, j - 1] 位置都是可能有障碍的，此时从上⾯或者左边是不可能到达[i, j] 位置的，也就是说，此时的⽅法数应该是0。由此我们可以得出⼀个结论，只要这个位置上「有障碍物」，那么我们就不需要计算这个位置上的值，直接让它等于0即可。

代码如下：

class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {//1.创建dp表//2.初始化//3.填表//4.返回值int m = obstacleGrid.length;int n = obstacleGrid[0].length;int[][] dp = new int[m + 1][n + 1];dp[0][1] = 1;for(int i = 1;i <= m;i++){for(int j = 1;j <= n;j++){if(obstacleGrid[i - 1][j - 1] == 1){dp[i][j] = 0;}else{dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}}return dp[m][n];}
}

时间复杂度：O（n * m）

空间复杂度：O（n * m）

例题3：礼物的最⼤价值

链接：礼物的最⼤价值

题目简介：

现有一个记作二维矩阵 frame 的珠宝架，其中 frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为：

只能从架子的左上角开始拿珠宝
每次可以移动到右侧或下侧的相邻位置
到达珠宝架子的右下角时，停止拿取

注意：珠宝的价值都是大于 0 的。除非这个架子上没有任何珠宝，比如 frame = [[0]]。

解法（动态规划）：

1. 状态表示：

dp[i][j] 表⽰：⾛到[i, j] 位置处，此时的最⼤价值。

2.状态转移方程

对于dp[i][j] ，我们发现想要到达[i, j] 位置，有两种⽅式：

(1)从[i, j] 位置的上⽅[i - 1, j] 位置，向下⾛⼀步，此时到达[i, j] 位置能拿到的礼物价值为dp[i - 1][j] + grid[i][j] .

(2)从[i, j] 位置的左边[i, j - 1] 位置，向右⾛⼀步，此时到达[i, j] 位置能拿到的礼物价值为dp[i][j - 1] + grid[i][j].

最终dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j] 。

3.初始化

添加辅助节点

4.填表顺序

填表的顺序是「从上往下填写每⼀⾏」，「每⼀⾏从左往右」。

5.返回值

返回dp[m][n]的值

代码如下：

class Solution {public int jewelleryValue(int[][] frame) {//1.创建dp表//2.初始化//3.填表//4.返回值int m = frame.length;int n = frame[0].length;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 - 1][j],dp[i][j - 1]) + frame[i - 1][j - 1];}}return dp[m][n];}
}

时间复杂度：O（n * m）

空间复杂度：O（n * m）

例题4：下降路径最⼩和

链接：下降路径最⼩和

题目简介：

给你一个 n x n 的方形整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。

下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

解法（动态规划）：

1. 状态表示：

dp[i][j] 表⽰：到达[i, j] 位置时，所有下降路径中的最⼩和。

2.状态转移方程

对于普遍位置[i, j] ，根据题意得，到达[i, j] 位置可能有三种情况：

（1）从正上⽅[i - 1, j] 位置转移到[i, j] 位置.

（2）从左上⽅[i - 1, j - 1] 位置转移到[i, j] 位置；

(3) 从右上⽅[i - 1, j + 1] 位置转移到[i, j] 位置；

由于我们要的是最小的于是 dp[i][j] = min(dp[i - 1][j], min(dp[i - 1][j - 1], dp[i - 1][j + 1])) + matrix[i][j] 。

3.初始化

辅助节点

在本题中，需要「加上⼀⾏」，并且「加上两列」。所有的位置都初始化为⽆穷⼤，然后将第⼀⾏初始化为0即可。

4.填表顺序

表的顺序是从上往下。

5.返回值

返回dp表中最后⼀⾏的最⼩值。

代码如下：

class Solution {public int minFallingPathSum(int[][] matrix) {//1.创建dp表//2.初始化//3.填表//4.返回值int m = matrix.length;//yint n = matrix[0].length;//xint[][] dp = new int[m + 1][n + 2];//辅助节点for(int i = 0;i <= m;i++){dp[i][0] = Integer.MAX_VALUE;dp[i][n + 1] = Integer.MAX_VALUE;}for(int i = 1;i <= n;i++){dp[m][i] = Integer.MAX_VALUE;}for(int i = m - 1;i >= 0;i--){for(int j = 1;j <= n;j++){int min = Math.min(Math.min(dp[i + 1][j - 1],dp[i + 1][j]),dp[i + 1][j + 1]);if(min == Integer.MAX_VALUE){min = 0;}dp[i][j] = matrix[i][j - 1] + min;}}int key = dp[0][1];for(int i = 1;i <= n;i++){if(key > dp[0][i]){key = dp[0][i];}}return key;}
}

时间复杂度：O（n * m）

空间复杂度：O（n * m）

例题5：最小路径和

链接：最⼩路径和

题目简介：

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

解法（动态规划）：

1. 状态表示：

dp[i][j] 表⽰：到达[i, j] 位置处，最⼩路径和是多少。

2.状态转移方程

简单分析⼀下。如果dp[i][j] 表⽰到达到达[i, j] 位置处的最⼩路径和，那么到达 [i, j] 位置之前的⼀⼩步，有两种情况：

（1）从[i - 1, j] 向下⾛⼀步，转移到[i, j] 位置；

（2）从[i, j - 1] 向右⾛⼀步，转移到[i, j] 位置。

由于到[i, j] 位置两种情况，并且我们要找的是最⼩路径，因此只需要这两种情况下的最⼩值，再加上 [i, j] 位置上本⾝的值即可。故最终结果为：dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]。

3.初始化

辅助节点

在本题中，「添加⼀⾏」，并且「添加⼀列」后，所有位置的值可以初始化为⽆穷⼤，然后让 dp[0][1] = dp[1][0] = 0 即可。如下图所示：

4.填表顺序

「从上往下」填每⼀⾏，每⼀⾏「从左往右」。

5.返回值

返回的结果是dp[m][n] 。

代码如下：

class Solution {public int minPathSum(int[][] grid) {//1.创建dp表//2.初始化//3.填表//4.返回值int m = grid.length;//yint n = grid[0].length;//xint[][] dp = new int[m + 1][n + 1];for(int i = 2;i <= n;i++){dp[0][i] = Integer.MAX_VALUE;}for(int i = 2;i <= m;i++){dp[i][0] = Integer.MAX_VALUE;}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];}
}

时间复杂度：O（n * m）

空间复杂度：O（n * m）