☕ DSA Java Articles

Topics › Dynamic Programming › 2D/3D DP and DP on Grids

Grid Unique Paths : DP on Grids (DP8)

Medium TUF ID 2795 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

A robot stands on the top-left cell (0, 0) of an m × n grid and wants to reach the bottom-right cell (m - 1, n - 1). At each step it can move only right or down. Count the distinct paths.

Constraints (LeetCode 62): 1 ≤ m, n ≤ 100, and the answer is guaranteed to be at most 2 × 10^9, so it fits in an int.

Example 1

m = 3, n = 7
answer = 28

Example 2

m = 3, n = 2
answer = 3          // down-down-right, down-right-down, right-down-down

Approach 1: Recursion

Intuition. This is the first DP on a grid, and the state is simply a cell. Let f(i, j) be the number of paths from (0, 0) to (i, j). The robot entered (i, j) with its last move, which was either a down move from (i - 1, j) or a right move from (i, j - 1). Those two groups of paths differ in their last move, so they do not overlap, and together they are all the paths. So

f(0, 0) = 1
f(i, j) = 0                              if i < 0 or j < 0   (off the grid)
f(i, j) = f(i - 1, j) + f(i, j - 1)      otherwise

The answer is f(m - 1, n - 1). Writing the recursion from the target back to the start makes the base case the fixed starting cell, which keeps it simple.

Algorithm.

  1. If (i, j) is (0, 0), return 1.
  2. If i < 0 or j < 0, return 0.
  3. Return f(i - 1, j) + f(i, j - 1).
static int recursive(int m, int n) {
    return paths(m - 1, n - 1);
}

static int paths(int i, int j) {
    if (i == 0 && j == 0) return 1;                         // reached the start
    if (i < 0 || j < 0) return 0;                           // walked off the grid
    return paths(i - 1, j) + paths(i, j - 1);               // arrived from above or from the left
}

Complexity. Time O(2^(m+n)): every call branches twice and the depth is up to m + n - 2. Space O(m + n) for the recursion stack.

Approach 2: Memoization

Intuition. There are only m · n cells, but the recursion reaches most of them by many routes. For instance, f(1, 1) is requested from both f(2, 1) and f(1, 2). Cache each cell’s count in dp[i][j].

Algorithm.

  1. Create dp[m][n] filled with -1.
  2. After the two base cases, return dp[i][j] if it is filled; otherwise compute it, store it, and return it.
static int memoization(int m, int n) {
    int[][] dp = new int[m][n];
    for (int[] row : dp) Arrays.fill(row, -1);
    return memo(m - 1, n - 1, dp);
}

static int memo(int i, int j, int[][] dp) {
    if (i == 0 && j == 0) return 1;
    if (i < 0 || j < 0) return 0;
    if (dp[i][j] != -1) return dp[i][j];
    return dp[i][j] = memo(i - 1, j, dp) + memo(i, j - 1, dp);
}

Complexity. Time O(m · n): each cell is computed once. Space O(m · n) for the table plus O(m + n) stack.

Approach 3: Tabulation

Intuition. f(i, j) reads the cell above and the cell to the left. If we fill the grid row by row, left to right, both of those are always ready. Cells in row 0 have nothing above and cells in column 0 have nothing to their left; those terms count as 0, matching the “off the grid” base case.

Algorithm.

  1. dp[0][0] = 1.
  2. For every other cell in row-major order: dp[i][j] = (i > 0 ? dp[i - 1][j] : 0) + (j > 0 ? dp[i][j - 1] : 0).
  3. Return dp[m - 1][n - 1].
static int tabulation(int m, int n) {
    int[][] dp = new int[m][n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0 && j == 0) { dp[i][j] = 1; continue; }
            int up = i > 0 ? dp[i - 1][j] : 0;
            int left = j > 0 ? dp[i][j - 1] : 0;
            dp[i][j] = up + left;
        }
    }
    return dp[m - 1][n - 1];
}

Dry run for m = 3, n = 7:

  j=0 j=1 j=2 j=3 j=4 j=5 j=6
i=0 1 1 1 1 1 1 1
i=1 1 2 3 4 5 6 7
i=2 1 3 6 10 15 21 28

Each cell is the one above it plus the one to its left. The bottom-right cell is 28.

Complexity. Time O(m · n), space O(m · n).

Approach 4: Space optimized

Intuition. Row i needs only row i - 1. Better still, one array is enough. When we are about to update row[j] during row i, it still holds the value from row i - 1 (the cell above), and row[j - 1] has already been updated for row i (the cell to the left). So row[j] += row[j - 1] is exactly “above plus left”.

Algorithm.

  1. row = [1, 0, 0, ..., 0].
  2. For each of the m rows, for j from 1 to n - 1: row[j] += row[j - 1].
  3. Return row[n - 1].

On the first pass row becomes all ones, which is row 0 of the table. Column 0 never changes from 1, which is also correct: the only path down the first column is straight down.

static int spaceOptimized(int m, int n) {
    int[] row = new int[n];
    row[0] = 1;
    for (int i = 0; i < m; i++) {
        for (int j = 1; j < n; j++) {
            row[j] += row[j - 1];                           // from above (old row[j]) + from the left (new row[j - 1])
        }
    }
    return row[n - 1];
}

Complexity. Time O(m · n), space O(n).

Approach 5: Combinatorics

Intuition. Every path consists of exactly m - 1 down moves and n - 1 right moves, in some order, and every such order is a valid path that stays inside the grid. So counting paths means counting the ways to choose which m - 1 of the m + n - 2 moves are downs:

answer = C(m + n - 2, m - 1)

Computing the factorials directly would overflow long before the answer does. Instead, build the binomial coefficient one factor at a time. With N = m + n - 2 and r = min(m - 1, n - 1), after step i the running value equals C(N - r + i, i), which is always an integer. So the division at each step is exact, and the intermediate product never exceeds the final answer times N, which fits in long.

Algorithm.

  1. N = m + n - 2, r = min(m - 1, n - 1), result = 1.
  2. For i from 1 to r: result = result · (N - r + i) / i.
  3. Return result.
static int combinatorics(int m, int n) {
    int total = m + n - 2;
    int r = Math.min(m - 1, n - 1);
    long result = 1;
    for (int i = 1; i <= r; i++) {
        result = result * (total - r + i) / i;              // result is now C(total - r + i, i): always an integer
    }
    return (int) result;
}

For m = 3, n = 7: N = 8, r = 2, and the steps give 1 · 7 / 1 = 7, then 7 · 8 / 2 = 28.

Complexity. Time O(min(m, n)), space O(1). This is the fastest method, but the DP versions are the ones that generalise: add obstacles, costs or forbidden moves, and the formula no longer applies while the table still does.

Edge cases and pitfalls