62. Unique Paths

    public static int uniquePaths(int m, int n) {
        int top = 1;
        int left = 1;
        return pathSum(top,left,m,n);
    }
    public static int pathSum(int top,int left,int m,int n){
        if( left == m && top == n){
            return 1;
        }else if(top==n){
        return pathSum(top,left+1,m,n);
        }else if( left == m){
            return pathSum(top+1,left,m,n);
        }else if( left < m && top < n){
            return pathSum(top+1,left,m,n)+ pathSum(top,left+1,m,n);
        } 
        return 0;
     }

1.简化版的递归
     public int uniquePaths(int m, int n) {
        return uniquePaths(1,1,m, n);
    }
    
    public int uniquePaths(int currentRow, int currentColumn, int m, int n){
        if(currentRow==m || currentColumn==n){
            return 1;
        }    
        return uniquePaths(currentRow+1, currentColumn, m ,n ) + uniquePaths(currentRow,                    currentColumn+1, m, n);
    }

2.利用杨辉三角求解:
在Dynamic Programming思路的指引下，我们可以尝试将递归的方法改变为循环的方法来解决。这里就运用到了数学中的杨辉三角。很显然，最左侧一行和最顶侧一行的到达路径数都是1，而任何一个非该行列的节点都可以通过左侧节点和上侧节点的路径数相加得到从起点出发到达自己共有的路径数。我们可以利用二维数组来实现叠加。代码如下：
    public static int pathSum(int top,int left,int m,int n){
        int[][] a = new int[m][n];
        
        for (int i = 0; i < m; i++) {
            a[i][0] = 1;
        }
        
        for (int i = 0; i < n; i++) {
            a[0][i]=1;
        }
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                a[i][j] = a[i][j-1]+a[i-1][j];
            }
        }
        return a[m-1][n-1];
    }