代码随想录训练营第38天|62.不同路径，63.不同路径II
代码随想录训练营第38天|62.不同路径，63.不同路径II
- 62.不同路径
- 文章
- 思路
- 代码
- 63.不同路径II
- 文章
- 思路
- 代码
- 总结
62.不同路径
文章
代码随想录|0062.不同路径
思路
d p [ i ] [ j ] = { 1 , i = 0 ∧ j = 0 d p [ i − 1 ] [ j ] + d p [ i ] [ j − 1 ] , e l s e \begin{equation}dp[i][j]=\left\{\begin{aligned} 1 & ,& i=0 \land j=0 \\ dp[i-1][j]+dp[i][j-1] &, & else \end{aligned}\right. \end{equation} dp[i][j]={1dp[i−1][j]+dp[i][j−1],,i=0∧j=0else
代码
class Solution {public int uniquePaths(int m, int n) {int[][] dp = new int[m][n];int i, j;for (i = 0; i < m; ++i) {for (j = 0; j < n; ++j) {if (i == 0 || j == 0) {dp[i][j] = 1;} else {dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}}return dp[m - 1][n - 1];}
}
63.不同路径II
文章
代码随想录|0063.不同路径II
思路
d p [ i ] [ j ] = { 0 , o b s t a c l e G r i d [ i ] [ j ] = 0 1 , o b s t a c l e G r i d [ i ] [ j ] ≠ 0 ∧ i = 0 ∧ j = 0 d p [ i ] [ j − 1 ] , i = 0 ∧ j > 0 d p [ i − 1 ] [ j ] , j = 0 ∧ i > 0 d p [ i − 1 ] [ j ] + d p [ i ] [ j − 1 ] , e l s e \begin{equation}dp[i][j]=\left\{\begin{aligned} 0 & ,& obstacleGrid[i][j]=0 \\ 1 &,& obstacleGrid[i][j]\neq0\land i=0\land j=0\\ dp[i][j-1]&,&i=0\land j>0\\ dp[i-1][j]&,&j=0\land i>0\\ dp[i-1][j]+dp[i][j-1] &, & else \end{aligned}\right. \end{equation} dp[i][j]=⎩ ⎨ ⎧01dp[i][j−1]dp[i−1][j]dp[i−1][j]+dp[i][j−1],,,,,obstacleGrid[i][j]=0obstacleGrid[i][j]=0∧i=0∧j=0i=0∧j>0j=0∧i>0else
代码
class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m, n;m = obstacleGrid.length;n = obstacleGrid[0].length;int i, j;int[][] dp = new int[m][n];for (i = 0; i < m; ++i) {for (j = 0; j < n; ++j) {if (obstacleGrid[i][j] == 1) {dp[i][j] = 0;} else if (i == 0 && j != 0) {dp[i][j] = dp[i][j - 1] == 0 ? 0 : 1;} else if (i != 0 && j == 0) {dp[i][j] = dp[i - 1][j] == 0 ? 0 : 1;} else if (i == 0 && j == 0) {dp[i][j] = 1;}else {dp[i][j] = dp[i][j - 1] + dp[i - 1][j];}}}return dp[m - 1][n - 1];}
}
总结
N刷不多说了