【代码随想录训练营】【Day39】第九章｜动态规划｜62.不同路径｜63. 不同路径 II

不同路径

题目详细：LeetCode.62

有点简单呀，做类似这种题型时，最好就是先画图：

• 可以像题目一样，画一个二维表格，表格内的值代表到达这个格子的不同路径总数
• 那么已知，如果图的大小为m == 1 || n == 1时，即只有一列或一行时，那么其不同路径总数都只有一条
• 当出现其他情况时，我们并不难发现格子内的数值刚好等于其上边和左边格子的和，即其不同路径总数为经过上边和左边格子的不同路径之和
• 那么我们以此规律就可以依次计算出除第一列和第一行外，到达其他各个格子的不同路径数目
• 最后我们即可得到右下角终点的值，即为到达终点的不同路径总数

详细的解题思路我都写在注释里了，也可查阅：《代码随想录》— 不同路径

Java解法（动态规划）：

class Solution {public int uniquePaths(int m, int n) {// 只有一列或一行时，那么其不同路径总数都只有一条if(m == 1 || n == 1){return 1;}// 主要初始化第一行和第一列的不同路径数都为1int[][] map = new int[m][n];for(int i = 0; i < m; i++){Arrays.fill(map[i], 1);}// 动态规划：从左往右，从上往下，计算到达每一个格子的不同路径总数for(int i = 1, j = 1; i < m;){// 递推公式map[i][j] = map[i - 1][j] + map[i][j - 1];// 先从左往右j++;if(j == n){// 到达右边界后，初始化列的下标j = 1;// 从上往下i++;}}return map[m - 1][n - 1];}
}

---

不同路径 II

题目详细：LeetCode.63

与上一题的区别在于这道题增加了障碍物，不过思路也不难，只要注意以下几点：

• 如果起点或终点出现了障碍物，则最终的不同路径总数都为0
• 对于第一列和第一行的初始化，按照从左往右，从上往下的顺序依次初始化为1，如果路径中出现了障碍物，则说明此路不通，后续的格子都初始化为0
• 将有障碍物的格子的不同路径总数记作0，只有遇到无障碍物的格子才累计其不同路径数目

那么只要根据以上三点，进行相对应的逻辑处理即可，累计格子的不同路径数目的思路与上一题的思路无异，详细的解题思路我都写在注释里了，也可查阅：《代码随想录》— 不同路径 II

Java解法（动态规划）：

class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length, n = obstacleGrid[0].length;// 特判，当障碍物出现在终点或起点时，不同路径总数都为0if(obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1){return 0;}// 定义一个辅助二维数组dp，防止直接操作原数组时，出现obstacleGrid[i][j] == 1的情况，将障碍物的表示数值累加进路径总数中int[][] dp = new int[m][n];// 对第一列和第一行进行赋值，路径总数为1，但是当路线上出现障碍物时，其后续的格子的路径总数都为0for(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;}// 从左往右，从上往下记录到达每个格子的不同路径数目// 这里利用二维数组dp来记录到达各个格子的路径总数// 而obstacleGrid相当于地图，仅用于判断是否出现障碍物for(int i = 1, j = 1; i < m;){if(i >= m || j >= n) break;// 格子没障碍物才进行累计，有障碍物的格子其路径总数默认为0if(obstacleGrid[i][j] == 0)dp[i][j] = dp[i - 1][j] + dp[i][j - 1];if(n == ++j){j = 1;i++;}}return dp[m - 1][n - 1];}
}

---