LC 62 Unique Paths(M)

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?

边界判断 当m 和 n都为1时候，直接出结果。

解题思路 (组合计算， DP)

• 当成算数的组合计算，以 3x7为例，路径应该是 2个下，6个右的 组合 D R R D R R R R 这样的组合公式就是 (m + n)!/(m! * n!) 如果 m < n 公式简化为 (m + n) *...(m+1)/m!

public int uniquePaths(int m, int n) {
    if(m == 1 || n == 1)
        return 1;
    m--;
    n--;
    if(m < n) {              // Swap, so that m is the bigger number
        m = m + n;
        n = m - n;
        m = m - n;
    }
    long res = 1;
    int j = 1;
    for(int i = m+1; i <= m+n; i++, j++){       // Instead of taking factorial, keep on multiply & divide
        res *= i;
        res /= j;
    }        
    return (int)res;
}

• 当(m==0 || n==0)路径始终为1， 因为不能左或上， 其他情况

  u(m, n) = u(m-1, n) + u(m, n-1);

 public int uniquePaths(int m, int n) {
    int[][] grid = new int[m][n];
    for(int i = 0; i<m; i++){
        for(int j = 0; j<n; j++){
            if(i==0||j==0)
                grid[i][j] = 1;
            else
                grid[i][j] = grid[i][j-1] + grid[i-1][j];
        }
    }
    return grid[m-1][n-1];
}