代码随想录训练营第38天|62.不同路径，63.不同路径II

62.不同路径

文章

代码随想录|0062.不同路径

思路

$$\begin{array}{c}dp[i][j]=\{\begin{array}{rlr}1& ,& i=0\wedge j=0\\ dp[i-1][j]+dp[i][j-1]& ,& else\end{array}\end{array}$$

代码

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

思路

$$\begin{array}{c}dp[i][j]=\{\begin{array}{rlr}0& ,& obstacleGrid[i][j]=0\\ 1& ,& obstacleGrid[i][j]\ne 0\wedge i=0\wedge j=0\\ dp[i][j-1]& ,& i=0\wedge j>0\\ dp[i-1][j]& ,& j=0\wedge i>0\\ dp[i-1][j]+dp[i][j-1]& ,& else\end{array}\end{array}$$

代码

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刷不多说了