### The Problem

There is a robot on an `m x n`

grid. The robot is initially located at the **top-left corner** (i.e., `grid[0][0]`

). The robot tries to move to **the bottom-right corner** (i.e., `grid[m - 1][n - 1]`

). The robot can only move either down or right at any point in time.

Given the two integers `m`

and `n`

, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

*Check LeetCode link for more details and example input & output.*

### Dynamic Programming Solutions

Solve it use the bottom up approach.

```
dp(m, n) = dp(m, n - 1) + dp(m - 1, n)
```

`dp(m, n)`

is the problem with a `m x n`

grid as the input.

The answer of `dp(m, n)`

is the sum of `dp(m, n - 1)`

and `dp(m - 1, n)`

,
where `dp(m, n - 1)`

means the robot chooses to move right and `dp(m - 1, n)`

means the robot chooses to move down.

Base cases:

`dp(i, 1)`

is`1`

. That is if the grid is a one-column grid, the robot only has one choice, which is going down.`dp(1, i)`

is`1`

too. On a one-row grid, the robot can only go right.

The sub problem `dp(i, j)`

has two dimensions, so it’s a 2D dynamic programming problem.
We can use a matrix, i.e. a 2d array.

```
public int uniquePaths(int m, int n) {
// dp[i][j] is the answer for dp(i+1, j+1)
int[][] dp = new int[m][n];
// base case: dp(1, i) = 1
for (int i = 0; i < n; i++) {
dp[0][i] = 1;
}
// base case: dp(i, 1) = 1
for (int i = 0; i < m; i++) {
dp[i][0] = 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];
}
```

Actually, when calculate `dp[i][j]`

, we only need the “previous” row in
the matrix, i.e. `dp[i - 1][j]`

. So we can save some space, by using only two rows.
See Java code below.

```
public int uniquePaths(int m, int n) {
int[] row = new int[n];
// initial value for base case (the one-row grid case)
Arrays.fill(row, 1);
for (int i = 1; i < m; i++) {
int[] newRow = new int[n];
// a base case (the one-column grid case)
newRow[0] = 1;
for (int j = 1; j < n; j++) {
newRow[j] = row[j] + newRow[j - 1];
}
row = newRow;
}
return row[n - 1];
}
```

The time complexity is `O(n*m)`

.