二维dp问题不同路径不同路径||珠宝的最高价值下降路径最小和最小路径和地下城游戏不同路径题目解析从起始位置到Finish位置有多少种路径每次只可以向下/向右走一格1.状态表示dp[i][j]表示到(i,j)位置路径数2.状态转移方程dp[i][j] dp[i-1][j] dp[i][j-1]3.初始化可以让dp表多创建一行和一列方便初始化dp[0][1] 14.填表顺序从上到下从左向右5.返回值dp[m][n]classSolution{publicintuniquePaths(intm,intn){int[][]dpnewint[m1][n1];dp[0][1]1;for(inti1;im;i){for(intj1;jn;j){dp[i][j]dp[i-1][j]dp[i][j-1];}}returndp[m][n];}}不同路径||题目解析从起点到终点有多少种路径每次只可以向下或向右走中间有障碍物不可以走和上题一样只不过这里有了障碍物1.状态表示dp[i][j]表示到(i,j)位置路径数2.状态转移方程当这个位置对应是不是障碍物dp[i][j] dp[i-1][j] dp[i][j-1]3.初始化可以让dp表多创建一行和一列方便初始化dp[0][1] 1 / dp[1][0]14.填表顺序从上到下从左向右5.返回值dp[m][n]classSolution{publicintuniquePathsWithObstacles(int[][]obstacleGrid){intmobstacleGrid.length;intnobstacleGrid[0].length;int[][]dpnewint[m1][n1];dp[1][0]1;for(inti1;im;i){for(intj1;jn;j){//没有障碍物if(obstacleGrid[i-1][j-1]0){dp[i][j]dp[i-1][j]dp[i][j-1];}}}returndp[m][n];}}珠宝的最高价值题目解析从起点到终点中路径中可以拿到最高珠宝价值总和每次只可以向下/向右边走1.状态表示dp[i][j]表示到(i,j)位置所有路径中最高宝珠价值和2.状态转移方程当这个位置对应是不是障碍物dp[i][j] max(dp[i-1][j] dp[i][j-1])frame[i-1][j-1]3.初始化可以让dp表多创建一行和一列方便初始化为04.填表顺序从上到下从左向右5.返回值dp[m][n]classSolution{publicintjewelleryValue(int[][]frame){intmframe.length;intnframe[0].length;int[][]dpnewint[m1][n1];for(inti1;im;i){for(intj1;jn;j){dp[i][j]Math.max(dp[i-1][j],dp[i][j-1])frame[i-1][j-1];}}returndp[m][n];}}下降路径最小和题目解析从第一行到最后一行中路径最小和每次只可以向当前位置左下 / 右下/正下方动态规划1.状态表示dp[i][j]表示到以(i,j)为结尾最小路径和2.状态转移方程dp[i][j] min(dp[i-1][j] , dp[i-1][j] , dp[i-1][j1]) m[i][j]3.初始化多创建一行和两列多的一行初始化为0多的两列初始为∞4.填表顺序从上到下从左向右5.返回值最后一行的最小值classSolution{publicintminFallingPathSum(int[][]matrix){intnmatrix.length;int[][]dpnewint[n1][n2];//初始化for(inti1;in;i){dp[i][0]dp[i][n1]Integer.MAX_VALUE;}for(inti1;in;i){for(intj1;jn;j){dp[i][j]Math.min((Math.min(dp[i-1][j-1],dp[i-1][j])),dp[i-1][j1])matrix[i-1][j-1];}}intretInteger.MAX_VALUE;for(inti1;in;i){retMath.min(dp[n][i],ret);}returnret;}}最小路径和题目解析从左上角到右下角最小路径和每次只可以向下/向右移动动态规划1.状态表示dp[i][j]表示到以(i,j)为结尾最小路径和2.状态转移方程dp[i][j] min(dp[i-1][j] , dp[i-1][j] , dp[i-1][j1]) grid[i][j]3.初始化dp[0][1] dp[1][0] 0,多的一行和一列剩余初始化为∞4.填表顺序从上到下从左向右5.返回值dp[m][n]classSolution{publicintminPathSum(int[][]grid){intmgrid.length;intngrid[0].length;int[][]dpnewint[m1][n1];//第一行for(inti2;im;i){dp[i][0]Integer.MAX_VALUE;}//第一列初始化为最大值for(inti2;in;i){dp[0][i]Integer.MAX_VALUE;}for(inti1;im;i){for(intj1;jn;j){dp[i][j]Math.min(dp[i-1][j],dp[i][j-1])grid[i-1][j-1];}}returndp[m][n];}}地下城游戏题目解析骑士从左上角到右下角拯救公主需要的最小初始血量经过一个位置血量会发生对应变化成功拯救公主骑士的血量 1动态规划1.状态表示dp[i][j]表示到以(i,j)为起点拯救公主最小初始血量2.状态转移方程dp[i][j] min(dp[i-1][j] , dp[i-1][j] ) - dungeon[i][j]3.初始化dp[m][n-1] dp[m-1][n] 1,多的一行和一列剩余初始化为∞4.填表顺序从下到上每一行每一行从右到左5.返回值dp[0][0]classSolution{publicintcalculateMinimumHP(int[][]dungeon){intmdungeon.length;intndungeon[0].length;int[][]dpnewint[m1][n1];//初始化多出来的一行和一列//最后一列for(inti0;im;i){dp[i][n]Integer.MAX_VALUE;}//最后一行for(intj0;jn;j){dp[m][j]Integer.MAX_VALUE;}dp[m][n-1]dp[m-1][n]1;for(intim-1;i0;i--){for(intjn-1;j0;j--){//当前位置向下 / 向右之后血量 1dp[i][j]Math.min(dp[i1][j],dp[i][j1])-dungeon[i][j];//可能这个位置是一个巨大血包(正整数)导致初始为负数dp[i][j]Math.max(1,dp[i][j]);}}returndp[0][0];}}
二维dp问题不同路径不同路径||珠宝的最高价值下降路径最小和最小路径和地下城游戏不同路径题目解析从起始位置到Finish位置有多少种路径每次只可以向下/向右走一格1.状态表示dp[i][j]表示到(i,j)位置路径数2.状态转移方程dp[i][j] dp[i-1][j] dp[i][j-1]3.初始化可以让dp表多创建一行和一列方便初始化dp[0][1] 14.填表顺序从上到下从左向右5.返回值dp[m][n]classSolution{publicintuniquePaths(intm,intn){int[][]dpnewint[m1][n1];dp[0][1]1;for(inti1;im;i){for(intj1;jn;j){dp[i][j]dp[i-1][j]dp[i][j-1];}}returndp[m][n];}}不同路径||题目解析从起点到终点有多少种路径每次只可以向下或向右走中间有障碍物不可以走和上题一样只不过这里有了障碍物1.状态表示dp[i][j]表示到(i,j)位置路径数2.状态转移方程当这个位置对应是不是障碍物dp[i][j] dp[i-1][j] dp[i][j-1]3.初始化可以让dp表多创建一行和一列方便初始化dp[0][1] 1 / dp[1][0]14.填表顺序从上到下从左向右5.返回值dp[m][n]classSolution{publicintuniquePathsWithObstacles(int[][]obstacleGrid){intmobstacleGrid.length;intnobstacleGrid[0].length;int[][]dpnewint[m1][n1];dp[1][0]1;for(inti1;im;i){for(intj1;jn;j){//没有障碍物if(obstacleGrid[i-1][j-1]0){dp[i][j]dp[i-1][j]dp[i][j-1];}}}returndp[m][n];}}珠宝的最高价值题目解析从起点到终点中路径中可以拿到最高珠宝价值总和每次只可以向下/向右边走1.状态表示dp[i][j]表示到(i,j)位置所有路径中最高宝珠价值和2.状态转移方程当这个位置对应是不是障碍物dp[i][j] max(dp[i-1][j] dp[i][j-1])frame[i-1][j-1]3.初始化可以让dp表多创建一行和一列方便初始化为04.填表顺序从上到下从左向右5.返回值dp[m][n]classSolution{publicintjewelleryValue(int[][]frame){intmframe.length;intnframe[0].length;int[][]dpnewint[m1][n1];for(inti1;im;i){for(intj1;jn;j){dp[i][j]Math.max(dp[i-1][j],dp[i][j-1])frame[i-1][j-1];}}returndp[m][n];}}下降路径最小和题目解析从第一行到最后一行中路径最小和每次只可以向当前位置左下 / 右下/正下方动态规划1.状态表示dp[i][j]表示到以(i,j)为结尾最小路径和2.状态转移方程dp[i][j] min(dp[i-1][j] , dp[i-1][j] , dp[i-1][j1]) m[i][j]3.初始化多创建一行和两列多的一行初始化为0多的两列初始为∞4.填表顺序从上到下从左向右5.返回值最后一行的最小值classSolution{publicintminFallingPathSum(int[][]matrix){intnmatrix.length;int[][]dpnewint[n1][n2];//初始化for(inti1;in;i){dp[i][0]dp[i][n1]Integer.MAX_VALUE;}for(inti1;in;i){for(intj1;jn;j){dp[i][j]Math.min((Math.min(dp[i-1][j-1],dp[i-1][j])),dp[i-1][j1])matrix[i-1][j-1];}}intretInteger.MAX_VALUE;for(inti1;in;i){retMath.min(dp[n][i],ret);}returnret;}}最小路径和题目解析从左上角到右下角最小路径和每次只可以向下/向右移动动态规划1.状态表示dp[i][j]表示到以(i,j)为结尾最小路径和2.状态转移方程dp[i][j] min(dp[i-1][j] , dp[i-1][j] , dp[i-1][j1]) grid[i][j]3.初始化dp[0][1] dp[1][0] 0,多的一行和一列剩余初始化为∞4.填表顺序从上到下从左向右5.返回值dp[m][n]classSolution{publicintminPathSum(int[][]grid){intmgrid.length;intngrid[0].length;int[][]dpnewint[m1][n1];//第一行for(inti2;im;i){dp[i][0]Integer.MAX_VALUE;}//第一列初始化为最大值for(inti2;in;i){dp[0][i]Integer.MAX_VALUE;}for(inti1;im;i){for(intj1;jn;j){dp[i][j]Math.min(dp[i-1][j],dp[i][j-1])grid[i-1][j-1];}}returndp[m][n];}}地下城游戏题目解析骑士从左上角到右下角拯救公主需要的最小初始血量经过一个位置血量会发生对应变化成功拯救公主骑士的血量 1动态规划1.状态表示dp[i][j]表示到以(i,j)为起点拯救公主最小初始血量2.状态转移方程dp[i][j] min(dp[i-1][j] , dp[i-1][j] ) - dungeon[i][j]3.初始化dp[m][n-1] dp[m-1][n] 1,多的一行和一列剩余初始化为∞4.填表顺序从下到上每一行每一行从右到左5.返回值dp[0][0]classSolution{publicintcalculateMinimumHP(int[][]dungeon){intmdungeon.length;intndungeon[0].length;int[][]dpnewint[m1][n1];//初始化多出来的一行和一列//最后一列for(inti0;im;i){dp[i][n]Integer.MAX_VALUE;}//最后一行for(intj0;jn;j){dp[m][j]Integer.MAX_VALUE;}dp[m][n-1]dp[m-1][n]1;for(intim-1;i0;i--){for(intjn-1;j0;j--){//当前位置向下 / 向右之后血量 1dp[i][j]Math.min(dp[i1][j],dp[i][j1])-dungeon[i][j];//可能这个位置是一个巨大血包(正整数)导致初始为负数dp[i][j]Math.max(1,dp[i][j]);}}returndp[0][0];}}
