代码随想录算法训练营第三十九天 | LeetCode 62. 不同路径、63. 不同路径 II
1. LeetCode 62. 不同路径
1.1 思路
- 本题是个二维矩阵，因此 dp 数组也定义为二维的，这样才能记录每个格的状态。从起始位置（0,0）到终止位置（m，n）
- dp 数组及下标的含义：dp[i][j] 的含义表示从（0，0）出发，到(i，j) 有dp[i][j]条不同的路径。
- 递推公式：由于只能向下和向右走，因此 dp[i][j]=dp[i-1][j]+dp[i][j-1]。还是和70. 爬楼梯一样，我们求的是方法数，不是步数，因此不用在这前两个位置的基础上+1。
- 初始化 dp 数组：因为中间那些格子需要从左方和上方推导出来的，因此左方和上方的格子都要初始化，即第 0 行和第 0 列，都初始化为 1 即可，因为我们只能往右和往下走，想走完第 0 行和第 0 列，只能一直向右和向下，都是 1 种路径
- 遍历顺序：从左往右，从上往下。因为需要依赖上方和左方的值
- 打印 dp 数组：用于 debug 验证
1.2 代码
// /** * 1. 确定dp数组下标含义 dp[i][j] 到每一个坐标可能的路径种类 * 2. 递推公式 dp[i][j] = dp[i-1][j] dp[i][j-1] * 3. 初始化 dp[i][0]=1 dp[0][i]=1 初始化横竖就可 * 4. 遍历顺序 一行一行遍历 * 5. 推导结果 。。。。。。。。 * * @param m * @param n * @return */ public static int uniquePaths(int m, int n) { int[][] dp = new int[m][n]; //初始化 for (int i = 0; i < m; i++) { dp[i][0] = 1; } for (int i = 0; i < n; i++) { dp[0][i] = 1; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = dp[i-1][j]+dp[i][j-1]; } } return dp[m-1][n-1]; }
2. LeetCode 63. 不同路径 II
2.1 思路
- 本题和62. 不同路径的区别在于，在图上多了个障碍
- dp 数组及下标的含义：dp[i][j] 的含义表示从（0，0）出发，到(i，j) 有dp[i][j]条不同的路径。和62. 不同路径基本一样
- 递推公式：dp[i][j]=dp[i-1][j]+dp[i][j-1] 也是一样的，但是多了个障碍，有了障碍的位置就不能走了，即 if（obstacleGrid[i][j]==0）再进行递推公式dp[i][j]=dp[i-1][j]+dp[i][j-1]
- 初始化 dp 数组：这是和62. 不同路径的最大区别，上面是第 0 行和第 0 列都是全 1，但这里如果在第 0 行（列）某个位置有障碍，那么右（下）方的就不是 1 而是 0 了，因为走不到这个位置，因为是只能往下或者往右走
- 遍历顺序：从左往右，从上往下。因为需要依赖上方和左方的值
- 打印 dp 数组：用于 debug 验证
- 注意这里你没必要在上述基础上遍历 dp 数组时加个条件：如果上面有障碍就只加上左边的，如果左边有障碍的就只加上上边的。这个没必要的。因为在有障碍的地方跳过了不给 dp[i][j] 赋值了，那个位置的 dp[i][j] 是为 0 的，后面即使加上也没事。
2.2 代码
// class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int m = obstacleGrid.length; int n = obstacleGrid[0].length; int[][] dp = new int[m][n]; //如果在起点或终点出现了障碍，直接返回0 if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) { return 0; } for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) { dp[i][0] = 1; } for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) { dp[0][j] = 1; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = (obstacleGrid[i][j] == 0) ? dp[i - 1][j] + dp[i][j - 1] : 0; } } return dp[m - 1][n - 1]; } }
