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