### 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)`.