代码随想录第40天|62.不同路径，63. 不同路径 II

62.不同路径

到达右下角那格的路径数量要么是从上来的，要么是从左来的

dp[i][j]含义：表示到达(i,j)的路径数

初始化：因为题目说明了只能往下或者往右走，所以第一行和第一列初始化为1

代码实现

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp=new int[m][n];//dp[i][j]表示在(i,j)的路径数
        //机器人每次只能向下或者向右移动一步。
        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][j-1]+dp[i-1][j];
            }
        }
        return dp[m-1][n-1];
    }
}

 

63. 不同路径 II

思路和上一题基本一样，只是添加了障碍物需要增加一些判断，同时如果起点就是障碍物，那么直接return 0；

 

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m=obstacleGrid.length;//行
        int n=obstacleGrid[0].length;//列
        int[][] dp=new int[m][n];
        if(obstacleGrid[0][0]==1){return 0;}
        //初始化
        for(int i=0;i<m;i++){
            if(obstacleGrid[i][0]==1){break;}
            dp[i][0]=1;
        }
         for(int j=0;j<n;j++){
             if(obstacleGrid[0][j]==1){break;}
              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][j-1]+dp[i-1][j];
                }
 
 
            }
        }
        return dp[m-1][n-1];
 
    }
}