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)
class Solution {
public int uniquePaths(int m, int n) {
int dp[][] = new int[m + 1][n + 1];
dp[m][n] = 1;
for (int r = m; r >= 1; r--) {
for (int c = n; c >= 1; c--) {
if (r == m && c == n)
continue;
else if (c == n)
dp[r][c] = dp[r + 1][c];
else if (r == m)
dp[r][c] = dp[r][c + 1];
else
dp[r][c] = dp[r + 1][c] + dp[r][c + 1];
}
}
return dp[1][1];
}
}
Last updated