leetcode62/63M不同路径

一. 62——不同路径

题目

思路：

以4*4的矩阵为例（如下图），首先考虑行数为1的情况（最下面一行），每个格子除了往右走之外别无选择，因此从这个格子出发可能的路径都是1，然后在此基础上考虑倒数第二行（从最右边的列开始），最后一列只能往下，有一种选择，倒数第二列可以往右或者往下，因此它的可能的选择等于它右边一格的选择数加上下边一格的选择数（1+1=2），同样的，第二列的选择数等于右边的2+下边的1=3，因此，我们可以得出结论，就是每一格的选择数等于它右边的格加下边的格的选择数。

4*4的格子的可选路径数

实现方法，初始化一个一维数组，长度为格子的列数，然后先得到倒数第一行，再得到倒数第二行，以此类推，最后数组的第一个元素就是结果：

代码：

public static int uniquePaths(int m, int n) {
        int[] arr=new int[m];
        Arrays.fill(arr, 1);
        for(int row=1;row<n;row++){
            for(int col=m-2;col>=0;col--){
                arr[col]=arr[col]+arr[col+1];
            }
        }
        return arr[0];
    }

一. 63——不同路径2

题目

思路：

和上一道题类似，区别在于如果矩阵中这个格子有障碍，则把他置0即可，下图是一个有障碍的4*4的格子和它对应的路径数表格，需要注意的一点是如果最后一行的某一个有障碍，那么这一行左边的路径数都是0，如果最右边的一列的某一格有障碍，那么这一列上面的所有路径数都是0

4*4的有障碍矩阵

代码：

public static int uniquePathsWithObstacles(int[][] arr) {
        int rowNum=arr[0].length;
        int[] pArr=new int[arr.length];
        for(int i=arr.length-1;i>=0;i--){
            if(arr[i][rowNum-1]==0){
                pArr[i]=1;
            }else{
                while(i>=0)pArr[i--]=0;
            }
        }
        for(int row=rowNum-2;row>=0;row--){
            for(int col=arr.length-1;col>=0;col--){
                if(arr[col][row]==1)pArr[col]=0;
                else{
                    if(col!=arr.length-1) pArr[col]=pArr[col]+pArr[col+1];
                }
            }
        }
        return pArr[0];
    }