动态规划 之 路径问题 算法专题
一. 不同路径
不同路径
- 状态表示
dp[i][j] 表示走到[i][j]位置, 有几种不同的路径 - 状态转移方程
以离[i][j] 最近的位置划分问题
1.从[i - 1][j] 到[i][j], 到[i][j]位置的不同路径数 就是和 到[i - 1][j]位置的不同路径数相同, 即dp[i][j] = dp[i - 1][j]
2.从[i][j - 1] 到[i][j], 到[i][j]位置的不同路径数 就是和 到[i ][j - 1]位置的不同路径数相同, 即dp[i][j] = dp[i][j - 1]
- dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
-
初始化
使用优化的思想进行初始化, 添加虚拟节点
在第一行和第一列的位置填表时会发生越界
所以需要添加一行一列
我们只需要像上表一样初始化虚拟节点, 就可以正确的进行填表 -
填表顺序
从上往下 从左往右 -
返回值
返回dp[m][n]
class Solution {public int uniquePaths(int m, int n) {//1. 创建表//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];}
}
二. 不同路径II
不同路径II
- 状态表示
dp[i][j] 表示走到[i][j]位置, 有几种不同的路径 - 状态转移方程
以离[i][j] 最近的位置划分问题
1.从[i - 1][j] 到[i][j], 到[i][j]位置的不同路径数 就是和 到[i - 1][j]位置的不同路径数相同, 即dp[i][j] = dp[i - 1][j]
2.从[i][j - 1] 到[i][j], 到[i][j]位置的不同路径数 就是和 到[i ][j - 1]位置的不同路径数相同, 即dp[i][j] = dp[i][j - 1]
但是如果此时的[i][j]是障碍物, 那么到达这个位置的路径数就为0, 所以dp[i][j] = 0
- dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
-
初始化
使用优化的思想进行初始化, 添加虚拟节点
在第一行和第一列的位置填表时会发生越界
所以需要添加一行一列
我们只需要像上表一样初始化虚拟节点, 就可以正确的进行填表 -
填表顺序
从上往下 从左往右 -
返回值
返回dp[m][n]
class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {//1. 创建表//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];}
}
三. 珠宝的最高价值
珠宝的最高价值
- 状态表示
dp[i][j] 表示走到[i][j]位置, 获得的珠宝的最高价值是多少 - 状态转移方程
以离[i][j] 最近的位置划分问题
到[i][j]位置的获得的珠宝的最高价值 就是到[i - 1][j]位置的获得的珠宝的最高价值 与 到[i][j - 1]位置的获得的珠宝的最高价值 的最大值, 然后加上[i][j]位置本来的价值
- dp[i][j] = max(dp[i - 1][j] + dp[i][j - 1]) + frame[i - 1][j - 1](采用优化的思想, 与原下标对应要 - 1)
- 初始化
使用优化的思想进行初始化, 添加虚拟节点
在第一行和第一列的位置填表时会发生越界
所以需要添加一行一列
我们只需要将虚拟节点都设为0即可 - 填表顺序
从上往下 从左往右 - 返回值
返回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];}
}四. 下降路径最小和
下降路径最小和
- 状态表示
dp[i][j] 表示走到[i][j]位置, 路径的最小和 - 状态转移方程
以离[i][j] 最近的位置划分问题
到[i][j]位置的路径的最小和 就是到[i - 1][j - 1]位置路径的最小和 与 到[i - 1][j]位置路径的最小和 与 [i - 1][j + 1]位置路径的最小和 的最小值, 然后加上[i][j]位置本来的值
- dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i - 1][j + 1]) + matrix[i - 1][j - 1](采用优化的思想, 与原下标对应要 - 1)
- 初始化
使用优化的思想进行初始化, 添加虚拟节点
在第一行和第一列和最后一列的位置填表时会发生越界
所以需要添加一行两列
我们需要将虚拟节点都设为最大值, 防止对原来的数进行干扰 - 填表顺序
从上往下 从左往右 - 返回值
返回最后一行中的最小值
class Solution {public int minFallingPathSum(int[][] matrix) {//1. 创建dp//2. 初始化//3. 填表//4. 返回值int n = matrix.length;int[][] dp = new int[n + 1][n + 2];for(int i = 1; i <= n; i++){dp[i][0] = Integer.MAX_VALUE;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(Math.min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i - 1][j + 1]) + matrix[i - 1][j - 1];}}int min = Integer.MAX_VALUE;for(int j = 1; j <= n; j++){min = Math.min(min, dp[n][j]);}return min;}
}
五. 最小路径和
最小路径和
- 状态表示
dp[i][j] 表示走到[i][j]位置, 路径的最小和 - 状态转移方程
以离[i][j] 最近的位置划分问题
到[i][j]位置的路径的最小和 就是到[i - 1][j]位置路径的最小和 与 [i][j - 1]位置路径的最小和 的最小值, 然后加上[i][j]位置本来的值
- dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1](采用优化的思想, 与原下标对应要 - 1)
- 初始化
使用优化的思想进行初始化, 添加虚拟节点
在第一行和第一列的位置填表时会发生越界
所以需要添加一行一列
我们需要将虚拟节点设为最大值, 但是[0][1]位置的值要设为0, 防止对原来的数进行干扰 - 填表顺序
从上往下 从左往右 - 返回值
dp[m][n]
class Solution {public int minPathSum(int[][] grid) {// 1. 创建dp// 2. 初始化// 3. 填表// 4. 返回值int m = grid.length;int n = grid[0].length;int[][] dp = new int[m + 1][n + 1];for (int i = 0; i <= m; i++) {dp[i][0] = Integer.MAX_VALUE;}for (int j = 0; j <= n; j++) {dp[0][j] = Integer.MAX_VALUE;}dp[0][1] = 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];}
}
六. 地下城游戏
地下城游戏
- 状态表示
dp[i][j] 如果表示走到[i][j]位置, 所需要的最小血量, 是没办法完成这道题的, 因为, 每走一步, 所需的最小血量都在更新
所以dp[i][j] 表示从[i][j]位置开始, 所需要的最小血量 - 状态转移方程
以离[i][j] 最近的位置划分问题
1.[i][j]位置所需要的最小血量 + [i][j]位置需要加或减的血量 一定是要 >= 到[i + 1][j]位置所需要的最小血量, 才能保证走下一个位置的时候不会死, 所以dp[i][j] = dp[i + 1][j] - 原表的[i][j]
2.[i][j]位置所需要的最小血量 + [i][j]位置需要加或减的血量 一定是要 >= 到[i][j + 1]位置所需要的最小血量, 才能保证走下一个位置的时候不会死, 所以dp[i][j] = dp[i][j + 1] - 原表的[i][j]
- dp[i][j] = Math.min(dp[i + 1][j], dp[i][j + 1]) - 原表的[i][j]
但是我们得出的dp[i][j] 必须是>0的, 如果<0, 就设为1, 所需要的最低血量
- 初始化
使用优化的思想进行初始化, 添加虚拟节点
在最后一行和最后一列的位置填表时会发生越界
所以需要添加一行一列
我们需要将虚拟节点设为最大值, 但是[m][n - 1]位置 和[m - 1][n]位置 的值要设为1, 所需要的最低血量 - 填表顺序
从下往上 从右往左 - 返回值
dp[0][0]
class Solution {public int calculateMinimumHP(int[][] dungeon) {// 1. 创建dp// 2. 初始化// 3. 填表// 4. 返回值int m = dungeon.length;int n = dungeon[0].length;int [][] dp = new int[m + 1][n + 1];for(int i = m; i >= 0; i--){dp[i][n] = Integer.MAX_VALUE;}for(int j = n; j >= 0; j--){dp[m][j] = Integer.MAX_VALUE;}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] = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];dp[i][j] = Math.max(1, dp[i][j]);}}return dp[0][0];}
}