Unique Paths

Question (LC.62)

A robot is located at the top-left corner of a m x n grid. The robot can only move either down or right. How many possible unique paths are there for the robot to get to the bottom-right?

Analysis

Coordinate DP

Approach

1. Define subproblem
UP(i,j) = possible unique paths from (0,0) to (i,j)

2. Solve by prefix
UP(i,j) = UP(i-1,j) + UP(i,j-1)

3. Base case
UP(0,j) = 1
UP(i,0) = 1

4. Topo Order
for i from 1 to m-1
    for j from 1 to n-1

5. Final Answer
UP(m-1,n-1)

Note: Coordinate DP doesn't need to have dp[m+1][n+1] since we only keep track of what's going on in the grid.

Code

public int uniquePaths(int m, int n) {
    if (m < 1 || n < 1) {
        return -1;
    }

    // create memo table
    int[][] up = new int[m][n];

    // init base case
    for (int i = 0; i < m; i++) {
        up[i][0] = 1;
    }
    for (int j = 0; j < n; j++) {
        up[0][j] = 1;
    }

    // topo order
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            up[i][j] = up[i-1][j] + up[i][j-1];
        }
    }

    // final answer
    return up[m-1][n-1];
}

Follow Up (LC.63)

Now consider if some obstacles are added to the grids. How many unique paths would there be?

Example

I:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
O: The total number of unique paths is 2

Analysis

If there is an obstacle, then just count the number of paths as 0. Be careful on how you initialize it.

Code

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    int m = obstacleGrid.length, n = obstacleGrid[0].length;

    // create memo table
    int[][] up = new int[m][n];

    // init base case
    for (int i = 0; i < m; i++) {
        if (obstacleGrid[i][0] == 1) {
            break;
        }
        up[i][0] = 1;
    }
    for (int j = 0; j < n; j++) {
        if (obstacleGrid[0][j] == 1) {
            break;
        }
        up[0][j] = 1;
    }

    // topo order
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (obstacleGrid[i][j] != 1) {
                up[i][j] = up[i-1][j] + up[i][j-1];
            }
        }
    }

    // final answer
    return up[m-1][n-1];
}