动态规划 之 路径问题 算法专题
一. 不同路径
不同路径
- 状态表示
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];
}
}