代码随想录算法训练营第39天|● 62.不同路径 ●63. 不同路径 II

不同路径

62. 不同路径 - 力扣（LeetCode）

1.确定dp数组（dp table）以及下标的含义

dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。

2.确定递推公式

p[i][j] = dp[i - 1][j] + dp[i][j - 1]

3.dp数组的初始化

先dp[i][0]一定都是1，因为从(0, 0)的位置到(i, 0)的路径只有一条，那么dp[0][j]也同理

4.遍历顺序

行列从前到后

class Solution {public int uniquePaths(int m, int n) {int[][]dp=new int[m+1][n+1];for (int i = 1; i <=m ; i++) {dp[i][1]=1;}for (int i = 1; i <=n ; i++) {dp[1][i]=1;}for (int i = 2; i <=m ; i++) {for (int j = 2; j <=n ; j++) {dp[i][j]=dp[i-1][j]+dp[i][j-1];}}return dp[m][n];}
}

不同路径II

63. 不同路径 II - 力扣（LeetCode）

与上题不同的是在初始化的时候要保存障碍物的地方要dp[i][j]==0

class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m=obstacleGrid.length;int n=obstacleGrid[0].length;int [][]dp=new int[m][n];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++) {if(obstacleGrid[i][j]==1){continue;}else {dp[i][j]=dp[i-1][j]+dp[i][j-1];}}}return dp[m-1][n-1];}
}