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];//注意要-1，从0开始遍历的
    }
}

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int rows=obstacleGrid.length;
        int cols=obstacleGrid[0].length;
        int[][] dp=new int[rows][cols];
        for(int i=0;i<rows;i++){
            if(obstacleGrid[i][0]==1){//遇到障碍，后面都初始化不了,默认为0
             break;
            }else dp[i][0]=1;
        }
        for(int j=0;j<cols;j++){
            if(obstacleGrid[0][j]==1){//遇到障碍，后面都初始化不了,默认为0
             break;
            }else dp[0][j]=1;
        }
        for(int i=1;i<rows;i++){
            for(int j=1;j<cols;j++){
                if(obstacleGrid[i][j]==1){//障碍无法到达
                    dp[i][j]=0;
                }else dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[rows-1][cols-1];
    }
}