算法训练Day39|62.不同路径 ● 63. 不同路径 II
LeetCode:62.不同路径
62. 不同路径 - 力扣（LeetCode）
1.思路
想象成矩阵填格子，两个关键点，初始化和递推公式。
初始化除点（0，0）第一行第一列均为1，递推公式推导dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
2.代码实现
1class Solution {2 public int uniquePaths(int m, int n) {3 // 二维数组4 int[][] dp = new int[m][n];56 // dp[m][n]:到达m,n位置，有dp[m][n]种路径7 // 初始化8 for (int i = 0; i < m; i++) {9 dp[i][0] = 1;
10 }
11 for (int i = 0; i < n; i++) {
12 dp[0][i] = 1;
13 }
14 for (int i = 1; i < m; i++) {
15 for (int j = 1; j < n; j++) {
16 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
17 }
18 }
19 return dp[m - 1][n - 1];
20 }
21}
22
3.复杂度分析
时间复杂度：O(m * n).
空间复杂度：O(m * n).
LeetCode:63. 不同路径 II
63. 不同路径 II - 力扣（LeetCode）
1.思路
确定dp[][]数组，
条件排除，各种情况的考虑很关键，首尾节点和首行首列会影响初始化，当前节点影响dp[i][j]的值，
2.代码实现
1class Solution {2 public int uniquePathsWithObstacles(int[][] obstacleGrid) {3 // 求出总路径数 - 障碍位置路径数？45 int m = obstacleGrid.length; // 获取行数6 int n = obstacleGrid[0].length; // 获取列数7 // dp[m][n] 表示节点（m,n）处潜在路径数8 int[][] dp = new int[m][n];9 // 当起始节点和终止节点均有障碍时，无结果，直接返回0
10 if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) {
11 return 0;
12 }
13 // 每行的首位数字初始化(也即首列初始化)，遇到障碍设置为0
14 for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
15 dp[i][0] = 1;
16 }
17 // 每列的首位数字初始化(也即首行初始化)，遇到障碍设置为0
18 for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
19 dp[0][j] = 1;
20 }
21 // 遍历输出dp[][]数组值
22 for (int i = 1; i < m; i++) {
23 for (int j = 1; j < n; j++) [
24 if (obstacleGrid[i][j] == 0) { // 当前节点没有障碍时，正常执行
25 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
26 } else {
27 dp[i][j] = 0; // 有障碍时直接赋值为0
28 }
29 ]
30 }
31 // 数组下标从0 开始，m - 1, n - 1也就代表（m,n）位置
32 return dp[m - 1][n - 1];
33
34 }
35}
36
3.复杂度分析
时间复杂度：O(m * n).
空间复杂度：O(m * n).