代码随想录算法训练营 | 62.不同路径，63. 不同路径 II

62.不同路径
题目链接：62.不同路径
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰不同路径
日期：2024-10-08

想法：第一行第一列只有一种方法，除此之外的各自的方法数由其左和上的格子的和得到。
Java代码如下：

class Solution {
    public 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 j = 0; j < n; j++) {
            dp[0][j] = 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];
    }
}

63. 不同路径 II
题目链接：63. 不同路径 II
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰不同路径 II
日期：2024-10-08

想法：总体思路跟上一题一样，在不是第一行第一列时的格子遇到障碍，到达方法为0；在第一行第一列时不仅该格子为0，后面的都为0
Java代码如下：

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        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++) {
                if(obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                }else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}

总结：没考虑起点和终点有障碍；初始化时，判断有无障碍的语句直接放在for上就能达到将后面的都为0的效果了。