# Unique Paths

​A robot is located at the top-left corner of a m x n grid (marked as ‘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 as ‘Finish’ in the diagram below). How many possible unique paths are there?

Example :

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

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

Since the robot can only move right and down, when it arrives at a point, it either arrives from left or above. If we use `dp[i][j]` for the number of unique paths to arrive at the `point (i,j)`, then the state equation is `dp[i][j] = dp[i][j - 1] + dp[i - 1][j]`. Moreover, we have the base cases `dp[j] = dp[i] = 1` for all valid `i` and `j`. Check the below figure for a better understanding.

```class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) dp[i] = 1;
for (int i = 0; i < n; i++) dp[i] = 1;
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
}
```

The above solution runs in `O(m*n)` time and costs `O(m*n)` space. However, you may have noticed that each time when we update `dp[i][j]`, we only need `dp[i - 1][j]` (at the previous row) and `dp[i][j - 1]` (at the current row). So we can reduce the memory usage to just two rows (`O(n)`).

```class Solution {
public int uniquePaths(int m, int n) {
int[] previousRow = new int[n];
int[] currentRow = new int[n];
for (int i = 0; i < n; i++) {
previousRow[i] = 1;
currentRow[i] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
currentRow[j] = previousRow[j] + currentRow[j - 1];
}
previousRow = currentRow;
}
return currentRow[n - 1];
}
}
```

Further inspecting the above code, `previousRow[j]` is just the `currentRow[j]` before the update. So we can further reduce the memory usage to one row.

```class Solution {
public int uniquePaths(int m, int n) {
int[] currentRow = new int[n];
for (int i = 0; i < n; i++) {
currentRow[i] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
currentRow[j] = currentRow[j] + currentRow[j - 1];
}
}
return currentRow[n - 1];
}
}
```

The problem can also be solved using backtracking and Memoization. This approach is more useful when the robot can move in multiple directions like left, right, top, bottom or diagonally.

```class Solution {

public int uniquePaths(int m, int n) {
int[][] board = new int[m][n];
board[m - 1][n - 1] = 1;
int count = backTrack(board, m, n, 0, 0);
return count;
}

private int backTrack(int[][] board, int m, int n, int i, int j) {
if (i == m || j == n) return 0;
if (board[i][j] != 0) return board[i][j];
int c1 = backTrack(board, m, n, (i + 1), j);
int c2 = backTrack(board, m, n, i, (j + 1));
board[i][j] = (c1 + c2);
return board[i][j];
}
}
```

The backtracking solution also runs in `O(m*n)` times. ​