不同路径 1 2

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];
    }
}

原文地址：https://blog.csdn.net/qq_40386660/article/details/138254441

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！