博客

代码随想录训练营 Day39

今日任务

62.不同路径



63.不同路径Ⅱ


语言：Java

62. 不同路径

链接：

https://leetcode.cn/problems/unique-paths/

class Solution {
    public int uniquePaths(int m, int n) {
        //1.明确dp数组及下标的含义: 到达第i行第j列共有dp[i][j]种方式
        //2.递归公式: dp[i][j]=dp[i-1][j]+dp[i][j-1]
        //3.初始化: dp[0][j]=1,dp[i][0]=1
        //4.遍历顺序: 外层按行，内层按列
        //5.打印dp数组
        if(m == 1 || n == 1) return 1;

        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. 不同路径Ⅱ

链接：

https://leetcode.cn/problems/unique-paths-ii/


本题初始化部分要注意

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        //1.明确dp数组及下标含义: 到第i行第j列共有dp[i][j]种走法，有障碍物为0
        //2.递归公式: dp[i][j]=dp[i-1][j]+dp[i][j-1];有障碍物为0
        //3.初始化: dp[0][j]=dp[0][j-1],dp[i][0]=dp[i-1][0];有障碍物为0
        //4.遍历顺序: 外层按行，内层按列
        //5.打印dp数组
        if(obstacleGrid[0][0] == 1) return 0;

        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        //初始化：较复杂，要注意细节
        int[][] dp = new int[m][n];
        dp[0][0] = 1; //最开始已经判断过，所以直接赋值为1
        for(int i = 1; i < m; i++){ //从1开始
            if(obstacleGrid[i][0] == 0){
                dp[i][0] = dp[i - 1][0];
            }
            else{
                dp[i][0] = 0;
            }
        }
        for(int j = 1; j < n; j++){ //从1开始
            if(obstacleGrid[0][j] == 0){
                dp[0][j] = dp[0][j - 1];
            }
            else{
                dp[0][j] = 0;
            }
        }

        //递归
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                if(obstacleGrid[i][j] == 0){
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
                else{
                    dp[i][j] = 0;
                }
            }
        }

        return dp[m - 1][n - 1];
    }
}

关于初始化时for写法的说明

写法一和写法二的结果及含义是截然不同的，写法一是错误的初始化，写法二是正确的初始化。

写法二代表一旦遇到某一行第一列的位置有障碍物，那么该行及该行下面的所有行都无法到达，这是正确的逻辑与思维；而写法一在遇到某一行第一列有障碍物时，会继续初始化它下面的行首元素，这是不对的。

//注意for循环终止条件
//写法一
for(int i = 0; i < m; i++){
    if(obstacleGrid[i][0] == 0){
        dp[i][0] = 1;
    }
}
//写法二
for(int i = 0; i < m && obstacleGrid[i][0] == 0; i++){
    dp[i][0] = 1;
}