Unique Paths

Q:
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.


A:

另外，其实，可以免掉recursive调用，直接在数组上来计算的。

----第二遍  Iterative way, using 2D array----

public class Solution {
    public int uniquePaths(int m, int n) {
        if(m<=1||n<=1)
            return 1;
        int[][] A = new int[m][n];
        Arrays.fill(A[0],1);
        for(int i =1;i<m;i++)
            for(int j =0;j<n;j++)
                A[i][j] = j==0?1:A[i-1][j]+A[i][j-1];
        return A[m-1][n-1];
    }
}

 利用一维数组  using 1D array 

public class Solution {
    public int uniquePaths(int m, int n) {
        int[] A = new int[n];
        Arrays.fill(A,1);
        for(int i =1;i<m;i++)
            for(int j =1;j<n;j++)
                A[j] += A[j-1];
        return A[n-1];
    }
}
 

第一个是recursively  调用，同时用一个数组，来记录已经用过的调用。

public class UniquePaths {
    public int uniquePaths(int m, int n) {
        // DP
        int[][] pathNum = new int[m + 1][n + 1];// ignore the 0 row and col
        return recursivePath(pathNum, m, n);

    }

    private int recursivePath(int[][] pathNum, int row, int col) {
        if (pathNum[row][col] != 0) {
            return pathNum[row][col];
        } else {
            // else ,we need calculate them
            if (row == 1 && col == 1) {
                pathNum[1][1] = 1;
                return 1;
            }
            // now we can reduce their case
            int stepDown = 0;
            if (row >= 2) {
                stepDown = recursivePath(pathNum, row - 1, col);
                pathNum[row - 1][col] = stepDown;
            }
            int stepRight = 0;
            if (col >= 2) {
                stepRight = recursivePath(pathNum, row, col - 1);
                pathNum[row][col - 1] = stepRight;
            }
            return stepRight + stepDown;
        }
    }
}