# 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?

Note: A and B will be such that the resulting answer fits in a 32 bit signed integer.

Example :

```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];
}
}

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

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;
}
}```