二维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] = 1
4.填表顺序：从上到下从左向右
5.返回值：dp[m][n]
classSolution{publicintuniquePaths(intm,intn){int[][]dp=newint[m+1][n+1];dp[0][1]=1;for(inti=1;i<=m;i++){for(intj=1;j<=n;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]=1
4.填表顺序：从上到下从左向右
5.返回值：dp[m][n]
classSolution{publicintuniquePathsWithObstacles(int[][]obstacleGrid){intm=obstacleGrid.length;intn=obstacleGrid[0].length;int[][]dp=newint[m+1][n+1];dp[1][0]=1;for(inti=1;i<=m;i++){for(intj=1;j<=n;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表多创建一行和一列方便初始化为0
4.填表顺序：从上到下从左向右
5.返回值：dp[m][n]
classSolution{publicintjewelleryValue(int[][]frame){intm=frame.length;intn=frame[0].length;int[][]dp=newint[m+1][n+1];for(inti=1;i<=m;i++){for(intj=1;j<=n;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][j+1]) + m[i][j]
3.初始化：多创建一行和两列，多的一行初始化为0，多的两列初始为＋∞
4.填表顺序：从上到下从左向右
5.返回值：最后一行的最小值
classSolution{publicintminFallingPathSum(int[][]matrix){intn=matrix.length;int[][]dp=newint[n+1][n+2];//初始化for(inti=1;i<=n;i++){dp[i][0]=dp[i][n+1]=Integer.MAX_VALUE;}for(inti=1;i<=n;i++){for(intj=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];}}intret=Integer.MAX_VALUE;for(inti=1;i<=n;i++){ret=Math.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][j+1]) + grid[i][j]
3.初始化：dp[0][1] = dp[1][0] = 0,多的一行和一列剩余初始化为＋∞
4.填表顺序：从上到下从左向右
5.返回值：dp[m][n]
classSolution{publicintminPathSum(int[][]grid){intm=grid.length;intn=grid[0].length;int[][]dp=newint[m+1][n+1];//第一行for(inti=2;i<=m;i++){dp[i][0]=Integer.MAX_VALUE;}//第一列初始化为最大值for(inti=2;i<=n;i++){dp[0][i]=Integer.MAX_VALUE;}for(inti=1;i<=m;i++){for(intj=1;j<=n;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){intm=dungeon.length;intn=dungeon[0].length;int[][]dp=newint[m+1][n+1];//初始化多出来的一行和一列//最后一列for(inti=0;i<m;i++){dp[i][n]=Integer.MAX_VALUE;}//最后一行for(intj=0;j<n;j++){dp[m][j]=Integer.MAX_VALUE;}dp[m][n-1]=dp[m-1][n]=1;for(inti=m-1;i>=0;i--){for(intj=n-1;j>=0;j--){//当前位置向下 / 向右之后血量 >= 1dp[i][j]=Math.min(dp[i+1][j],dp[i][j+1])-dungeon[i][j];//可能这个位置是一个巨大血包(正整数)，导致初始为负数dp[i][j]=Math.max(1,dp[i][j]);}}returndp[0][0];}}