动态规划 之 路径问题 算法专题

一. 不同路径

不同路径

1. 状态表示
   dp[i][j] 表示走到[i][j]位置, 有几种不同的路径
2. 状态转移方程
   以离[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]

3. 初始化
   使用优化的思想进行初始化, 添加虚拟节点
   在第一行和第一列的位置填表时会发生越界
   所以需要添加一行一列
   
   我们只需要像上表一样初始化虚拟节点, 就可以正确的进行填表

4. 填表顺序
   从上往下 从左往右

5. 返回值
   返回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

1. 状态表示
   dp[i][j] 表示走到[i][j]位置, 有几种不同的路径
2. 状态转移方程
   以离[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]

3. 初始化
   使用优化的思想进行初始化, 添加虚拟节点
   在第一行和第一列的位置填表时会发生越界
   所以需要添加一行一列
   
   我们只需要像上表一样初始化虚拟节点, 就可以正确的进行填表

4. 填表顺序
   从上往下 从左往右

5. 返回值
   返回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];}
}

三. 珠宝的最高价值

珠宝的最高价值

1. 状态表示
   dp[i][j] 表示走到[i][j]位置, 获得的珠宝的最高价值是多少
2. 状态转移方程
   以离[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)

3. 初始化
   使用优化的思想进行初始化, 添加虚拟节点
   在第一行和第一列的位置填表时会发生越界
   所以需要添加一行一列
   我们只需要将虚拟节点都设为0即可
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];}
}

四. 下降路径最小和

下降路径最小和

1. 状态表示
   dp[i][j] 表示走到[i][j]位置, 路径的最小和
2. 状态转移方程
   以离[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)

3. 初始化
   使用优化的思想进行初始化, 添加虚拟节点
   在第一行和第一列和最后一列的位置填表时会发生越界
   所以需要添加一行两列
   我们需要将虚拟节点都设为最大值, 防止对原来的数进行干扰
4. 填表顺序
   从上往下 从左往右
5. 返回值
   返回最后一行中的最小值

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;}
}

五. 最小路径和

最小路径和

1. 状态表示
   dp[i][j] 表示走到[i][j]位置, 路径的最小和
2. 状态转移方程
   以离[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)

3. 初始化
   使用优化的思想进行初始化, 添加虚拟节点
   在第一行和第一列的位置填表时会发生越界
   所以需要添加一行一列
   我们需要将虚拟节点设为最大值, 但是[0][1]位置的值要设为0, 防止对原来的数进行干扰
4. 填表顺序
   从上往下 从左往右
5. 返回值
   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];}
}

六. 地下城游戏

地下城游戏

1. 状态表示
   dp[i][j] 如果表示走到[i][j]位置, 所需要的最小血量, 是没办法完成这道题的, 因为, 每走一步, 所需的最小血量都在更新
   所以dp[i][j] 表示从[i][j]位置开始, 所需要的最小血量
2. 状态转移方程
   以离[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, 所需要的最低血量

3. 初始化
   使用优化的思想进行初始化, 添加虚拟节点
   在最后一行和最后一列的位置填表时会发生越界
   所以需要添加一行一列
   我们需要将虚拟节点设为最大值, 但是[m][n - 1]位置 和[m - 1][n]位置 的值要设为1, 所需要的最低血量
4. 填表顺序
   从下往上 从右往左
5. 返回值
   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];}
}