【力扣一刷】代码随想录day39（动态规划part2：62.不同路径、63. 不同路径 II ）

目录

【62.不同路径】中等题

方法一  只初始化start位置

方法二  初始化第一行和第一列

【63. 不同路径 II】中等题

【62.不同路径】中等题

思路：

1、前提：只能向右或向下移动一步，当前格子只能由左边（向右移）或上边（向下移）到达

2、递推关系：到达当前格子的路径数 = 到达左边格子的路径数 + 到达上边格子的路径数

方法一  只初始化start位置

思路：

1、设置start位置的初始值为1

2、计算到达当前格子的路径数：当前格子只能由左边（向右移）或上边（向下移）到达

• 第一行只加左边
• 第一列只加上边
• 其余情况，左边+上边

class Solution {public int uniquePaths(int m, int n) {int[][] matric = new int[m][n];for (int i = 0; i < m; i++){for (int j = 0; j < n; j++){if (i == 0 && j == 0) {matric[i][j] = 1; // 注意：start位置的值为1continue;}// 当前格子只能由左边（向右移）或上边（向下移）到达if (i == 0) matric[i][j] = matric[i][j-1]; // 第一行只加左边else if (j == 0) matric[i][j] = matric[i-1][j]; // 第一列只加上边else matric[i][j] = matric[i][j-1] + matric[i-1][j]; // 其余情况，左边+上边}}return matric[m-1][n-1];}
}

• 时间复杂度：O(m×n)
• 空间复杂度：O(m×n)

方法二  初始化第一行和第一列

思路：

1、将第一行的格子和第一列的格子都初始化为1

2、其余格子都存在左边的格子和上边的格子，直接相加即可

class Solution {public int uniquePaths(int m, int n) {int[][] matric = new int[m][n];for (int j = 0; j < n; j++) matric[0][j] = 1;  // 将第一行的格子都初始化为1for (int i = 0; i < m; i++) matric[i][0] = 1;  // 将第一列的格子都初始化为1// 其余格子都存在左边的格子和上边的格子，直接相加即可for (int i = 1; i < m; i++){for (int j = 1; j < n; j++){matric[i][j] = matric[i][j-1] + matric[i-1][j];}}return matric[m-1][n-1];}
}

• 时间复杂度：O(m×n)
• 空间复杂度：O(m×n)

【63. 不同路径 II】中等题

思路：

1、如果开始位置或结束位置有障碍物，则肯定无法出发或到达，直接返回0

2、初始化第一行和第一列

• 如果第一行某个格子出现障碍物，则当前格子以及右边的所有格子都无法到达（直接使用初始化的默认值0即可）；如果当前格子没有障碍物，则直接设为1。
• 如果第一列某个格子出现障碍物，则当前格子以及下边的所有格子都无法到达（直接使用初始化的默认值0即可）；如果当前格子没有障碍物，则直接设为1。

3、遍历剩余格子

• 如果当前格子有障碍物，则无法到达，设为0
• 如果当前格子有障碍物，则到达当前格子的路径数 = 到达左边格子的路径数 + 到达上边格子的路径数

class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int rows = obstacleGrid.length;int columns = obstacleGrid[0].length;int[][] matric = new int[rows][columns];// 如果开始位置或结束位置有障碍物，则肯定无法出发或到达，直接返回0if (obstacleGrid[0][0] == 1 || obstacleGrid[rows-1][columns-1] == 1) return 0;for (int j = 0; j < columns; j++){// 如果第一行某个格子出现障碍物，则当前格子以及右边的所有格子都无法到达（直接使用初始化的默认值0即可）if (obstacleGrid[0][j] == 1) break; // 如果当前格子没有障碍物else{matric[0][j] = 1;}}for (int i = 0; i < rows; i++){// 如果第一列某个格子出现障碍物，则当前格子以及下边的所有格子都无法到达（直接使用初始化的默认值0即可）if (obstacleGrid[i][0] == 1) break; // 如果当前格子没有障碍物else{matric[i][0] = 1;}}for (int i = 1; i < rows; i++){for (int j = 1; j < columns; j++){if (obstacleGrid[i][j] == 1) matric[i][j] = 0;else {matric[i][j] = matric[i-1][j] + matric[i][j-1];}}}return matric[rows-1][columns-1];}
}

• 时间复杂度：O(m×n)
• 空间复杂度：O(m×n)