Grid Unique Paths

A robot is located at the top-left corner of an A x B 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?

Input : A = 2, B = 2
Output : 2

2 possible routes : (0, 0) -> (0, 1) -> (1, 1) 
              OR  : (0, 0) -> (1, 0) -> (1, 1)

思路:

DP, dp[i][0] = dp[0][j] = 1
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

Solution:

Time: O(A * B)
Space: O(A * B)

public class Solution {
    public int uniquePaths(int A, int B) {
        int[][] dp = new int[A][B];
        for (int i = 0; i < A; i ++) {
            for (int j = 0; j < B; j ++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[A - 1][B - 1];
    }
}

思路2:

往右要走B - 1步，往下要走A - 1步，总共是A + B - 2步，我们要决定每一步是往下走还是往右走，所以就变成了计算A + B - 2 Choose B -1或者A + B - 2 Choose A - 1，是一样的 

m+n-2 C n-1 = (m+n-2)! / (n-1)! (m-1)!

如果A = 2, B = 3, => 

3! / 1! * 2! = 6 / 2 = 3
                 = 1 * 2 * 3 / 1 * 1 * 2
                 = 2 * 3 / 1 * 2
                 = 2 * 3 / (2 - 1) * (3 - 1) 
                 = 2 / (2 - 1) * 3 / (3 - 1)

Solution:

Time: O(A + B - 1)
Space: O(1)

class Solution {
    public:
        int uniquePaths(int m, int n) {
            // m+n-2 C n-1 = (m+n-2)! / (n-1)! (m-1)! 
            long long ans = 1;
            for (int i = n; i < (m + n - 1); i++) {
                ans *= i;
                ans /= (i - n + 1);
            }
            return (int)ans;
        }
}