前言
动规五部曲
1.确定dp数组含义
2.确定递推公式
3.初始化数组
4.确定遍历方式
5.打印dp数组查看分析问题
LeetCode T62 不同路径
题目思路:
注:n行m列而不是m行n列
1.确定dp数组含义
代表到达此下标有多少条路径
2.确定递推公式
因为只能向右或者向下走,所以到达i,j这个点的路径只有从左边和从上面到达,所以到达这个的途径数就是左边的数和上面的数之和.
dp[i][j] = dp[i-1][j] + dp[i][j-1];
3.初始化数组
初始化的时候应该将左边边界和上面边界都初始化为1,因为只有一条路径能到达
for(int i = 0;i<m;i++){ dp[i][0] = 1; } for(int i = 0;i<n;i++){ dp[0][i] = 1; }
4.确定遍历方式
此题目跟遍历顺序无关,顺序遍历即可
5.打印dp数组查看分析问题
遇见问题可以打印dp数组并推导尝试是否有问题
最后直接返回右下角的值即可
题目代码:
class Solution { public int uniquePaths(int m, int n) { int[][] dp = new int[m][n]; for(int i = 0;i<m;i++){ dp[i][0] = 1; } for(int i = 0;i<n;i++){ dp[0][i] = 1; } //记得从下标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-1][n-1]; } }
LeetCode T63 不同路径II
题目链接:63. 不同路径 II - 力扣（LeetCode）
题目思路:
1.确定dp数组含义
此时的dp数组也是代表和上一题一样的含义,表示有多少条路径能到达这个坐标
2.确定递推公式
注:这里如果遇到障碍,也就是1的情况,我们就让dp这个点取得0,不然就是和上文一样的递推公式
dp[i][j] = (obstacleGrid[i][j] == 0)?dp[i-1][j] + dp[i][j-1]:0;
3.初始化数组
这里初始化在边界遇到障碍的时候就是代表后面的下标都是到达不了的地方,所以就不进行赋值
注意:如果起点或者终点为障碍,就直接返回0
4.确定遍历方式
顺序遍历即可
5.打印dp数组查看分析问题
题目代码:
class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int m = obstacleGrid.length; int n = obstacleGrid[0].length; int[][] dp = new int[m][n]; //起点和终点为障碍 if(obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1){ return 0; } for(int i = 0;i<m && obstacleGrid[i][0] == 0;i++){ dp[i][0] = 1; } for(int i = 0;i<n && obstacleGrid[0][i] == 0;i++){ dp[0][i] = 1; } for(int i = 1;i<m;i++){ for(int j = 1;j<n;j++){ dp[i][j] = (obstacleGrid[i][j] == 0)?dp[i-1][j] + dp[i][j-1]:0; } } return dp[m-1][n-1]; } }
