Command Palette

Search for a command to run...

Problem: Unique Paths

Our first 2D DP problem demonstrates how the same problem-solving progression—recursion → memoization → tabulation—extends naturally to two dimensions.

Problem Statement

There is a robot on an m × 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.

Example 1:

Input: m = 3, n = 2
Output: 3

Explanation:
From the top-left corner, there are 3 ways to reach the bottom-right:
1. Right → Down → Down
2. Down → Right → Down
3. Down → Down → Right

Example 2:

Input: m = 3, n = 7
Output: 28

Constraints:

  • 1 ≤ m, n ≤ 100

Approach 1: Naive Recursion

Let's think recursively. How can we reach cell (i, j)?

We can reach cell (i, j) from:

  • Cell (i-1, j) by moving down
  • Cell (i, j-1) by moving right

Total paths to (i, j) = paths to (i-1, j) + paths to (i, j-1)

This gives us a recursive relationship:

paths(i, j) = paths(i-1, j) + paths(i, j-1)

Base cases:

  • paths(0, 0) = 1 (starting position, one way to be there)
  • paths(i, 0) = 1 for all i (only one way: go straight down)
  • paths(0, j) = 1 for all j (only one way: go straight right)
  • paths(i, j) = 0 if i < 0 or j < 0 (out of bounds)

Implementation

Java
public class UniquePaths {
    public long uniquePaths(int m, int n) {
        return pathsHelper(m - 1, n - 1);
    }

    private long pathsHelper(int i, int j) {
        // Base cases
        if (i == 0 && j == 0) return 1;  // Starting position
        if (i < 0 || j < 0) return 0;    // Out of bounds

        // Recursive case: sum paths from above and from left
        return pathsHelper(i - 1, j) + pathsHelper(i, j - 1);
    }
}

Tracing the Execution

Let's trace uniquePaths(3, 3) (simplified):

                           paths(2, 2)
                          /           \
                   paths(1, 2)       paths(2, 1)
                   /         \         /         \
            paths(0,2) paths(1,1) paths(1,1) paths(2,0)
                 /  \       /  \       /  \       /  \
               ...  ...   ...  ...   ...  ...   ...  ...

Notice the problem?

  • paths(1, 1) appears multiple times
  • paths(0, 2) appears multiple times
  • Many cells are recomputed repeatedly!

We're solving the same subproblems over and over!

Complexity Analysis

Time Complexity: O(2^(m+n)) - exponential

For each cell, we make 2 recursive calls, creating a binary tree of depth m+n.

Space Complexity: O(m + n) - call stack depth

Problem: This is unusably slow even for small grids!

Approach 2: Memoization (Top-Down DP)

The key insight: if we're computing paths(i, j) repeatedly, let's cache the results!

Memoization = recursion + 2D array for caching

Implementation

Java
public class UniquePaths {
    public long uniquePaths(int m, int n) {
        long[][] memo = new long[m][n];
        // Initialize with -1 to indicate "not computed"
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                memo[i][j] = -1;
            }
        }
        return pathsHelper(m - 1, n - 1, memo);
    }

    private long pathsHelper(int i, int j, long[][] memo) {
        // Base cases
        if (i == 0 && j == 0) return 1;
        if (i < 0 || j < 0) return 0;

        // Check if already computed
        if (memo[i][j] != -1) {
            return memo[i][j];
        }

        // Compute and store
        memo[i][j] = pathsHelper(i - 1, j, memo) + pathsHelper(i, j - 1, memo);

        return memo[i][j];
    }
}

How Memoization Works

Tracing uniquePaths(3, 3):

Initial: memo = all -1s

Call paths(2, 2):
  memo[2][2] = -1, need to compute
  Call paths(1, 2):
    memo[1][2] = -1, need to compute
    Call paths(0, 2):
      i=0, j=2: need to trace back to (0,0)
      Eventually returns 1
    Call paths(1, 1):
      memo[1][1] = -1, need to compute
      Eventually computes and stores memo[1][1] = 2
      return 2
    memo[1][2] = 1 + 2 = 3
    return 3
  Call paths(2, 1):
    memo[2][1] = -1, need to compute
    Call paths(1, 1):
      memo[1][1] = 2 ✓ (already computed!)
      return 2 (no recursion needed!)
    Call paths(2, 0):
      Eventually returns 1
    memo[2][1] = 2 + 1 = 3
    return 3
  memo[2][2] = 3 + 3 = 6
  return 6

Final: memo contains computed values for all cells visited

Key insight: When we need paths(1, 1) the second time, we just look it up!

Complexity Analysis

Time Complexity: O(m × n)

Each cell is computed exactly once. Computing each cell takes O(1) work.

Space Complexity: O(m × n)

  • O(m × n) for the memo array
  • O(m + n) for the call stack
  • Total: O(m × n)

Approach 3: Tabulation (Bottom-Up DP)

Memoization still uses recursion. Can we eliminate the call stack by building the solution bottom-up?

Tabulation = Build from base cases upward

Instead of starting from (m-1, n-1) and recursing down, start from (0, 0) and build up!

Implementation

Java
public class UniquePaths {
    public long uniquePaths(int m, int n) {
        // Create DP table
        // dp[i][j] = number of paths to reach (i, j) from (0, 0)
        long[][] dp = new long[m][n];

        // Base cases: first row and first column
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;  // Only one way: down, down, down...
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;  // Only one way: right, right, right...
        }

        // Fill table using recurrence
        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 answer
        return dp[m - 1][n - 1];
    }
}

How Tabulation Works

Tracing uniquePaths(3, 4) (3 rows, 4 columns):

Initialize base cases:

    j=0  j=1  j=2  j=3
i=0  1    1    1    1
i=1  1    ?    ?    ?
i=2  1    ?    ?    ?

Now fill row by row, left to right:

i=1, j=1:
  dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2

    j=0  j=1  j=2  j=3
i=0  1    1    1    1
i=1  1    2    ?    ?
i=2  1    ?    ?    ?

i=1, j=2:
  dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3

    j=0  j=1  j=2  j=3
i=0  1    1    1    1
i=1  1    2    3    ?
i=2  1    ?    ?    ?

i=1, j=3:
  dp[1][3] = dp[0][3] + dp[1][2] = 1 + 3 = 4

    j=0  j=1  j=2  j=3
i=0  1    1    1    1
i=1  1    2    3    4
i=2  1    ?    ?    ?

i=2, j=1:
  dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3

i=2, j=2:
  dp[2][2] = dp[1][2] + dp[2][1] = 3 + 3 = 6

i=2, j=3:
  dp[2][3] = dp[1][3] + dp[2][2] = 4 + 6 = 10

Final table:

    j=0  j=1  j=2  j=3
i=0  1    1    1    1
i=1  1    2    3    4
i=2  1    3    6   10

Return dp[2][3] = 10

Key insight: We compute values in order. By the time we need dp[i][j], we've already computed dp[i-1][j] and dp[i][j-1]!

Complexity Analysis

Time Complexity: O(m × n)

Two nested loops: m × n iterations, each doing O(1) work.

Space Complexity: O(m × n)

DP table of size m × n. No call stack overhead!

Approach 4: Space Optimization

Observation: To compute row i, we only need row i-1.

We don't need the entire 2D array - just the previous row!

Implementation

Java
public class UniquePaths {
    public long uniquePaths(int m, int n) {
        // Use only one row (size n)
        long[] dp = new long[n];

        // Initialize: first row all 1s
        for (int j = 0; j < n; j++) {
            dp[j] = 1;
        }

        // Process each subsequent row
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // dp[j] currently holds dp[i-1][j] (from previous row)
                // dp[j-1] holds dp[i][j-1] (from current row, already updated)
                dp[j] = dp[j] + dp[j - 1];
            }
            // After this loop, dp represents row i
        }

        return dp[n - 1];
    }
}

How Space Optimization Works

Tracing uniquePaths(3, 4):

Initial (row 0):
  dp = [1, 1, 1, 1]

Process row 1:
  j=1: dp[1] = dp[1] + dp[0] = 1 + 1 = 2  →  dp = [1, 2, 1, 1]
  j=2: dp[2] = dp[2] + dp[1] = 1 + 2 = 3  →  dp = [1, 2, 3, 1]
  j=3: dp[3] = dp[3] + dp[2] = 1 + 3 = 4  →  dp = [1, 2, 3, 4]

Process row 2:
  j=1: dp[1] = dp[1] + dp[0] = 2 + 1 = 3  →  dp = [1, 3, 3, 4]
  j=2: dp[2] = dp[2] + dp[1] = 3 + 3 = 6  →  dp = [1, 3, 6, 4]
  j=3: dp[3] = dp[3] + dp[2] = 4 + 6 = 10  →  dp = [1, 3, 6, 10]

Return dp[3] = 10 ✓

Key insight: We're reusing the same array, updating it in place as we process each row!

Complexity Analysis

Time Complexity: O(m × n) - same as tabulation

Space Complexity: O(n) - only one row instead of full m × n table!

Note

Note on data types: We use long instead of int to handle larger grids. For a 20×20 grid, the answer is C(38,19) ≈ 35 billion, which exceeds int range (max ~2.1 billion). A long handles grids up to about 30×30 comfortably. For the maximum constraint (100×100), the answer is a 59-digit number that would require BigInteger, but we use long here to keep the code focused on the DP pattern rather than overflow handling.

Comparing All Approaches

Approach Time Space Style Notes
Naive Recursion O(2^(m+n)) O(m+n) Recursive Too slow, repeated work
Memoization (Top-Down) O(m×n) O(m×n) Recursive Fast, natural structure
Tabulation (Bottom-Up) O(m×n) O(m×n) Iterative Fast, no recursion
Space Optimized O(m×n) O(n) Iterative Fastest, minimal memory

Connection to Mathematical Insight

For an m × n grid, each path requires exactly (m-1) down moves and (n-1) right moves.

Total moves: m + n - 2

Question: How many ways to choose positions for the (m-1) down moves?

Answer: C(m+n-2, m-1) = (m+n-2)! / ((m-1)! × (n-1)!)

For m=3, n=4: C(5, 2) = 10 ✓

DP discovers this without knowing the formula!

Key Takeaways

Problem-Solving Progression in 2D:

  1. Start with recursion: Express the 2D problem naturally
  2. Identify redundancy: Notice repeated subproblems in 2D space
  3. Add memoization: Cache results in a 2D array
  4. Convert to tabulation: Build solution bottom-up in 2D
  5. Optimize space: Identify that we only need one row at a time

2D DP Principles:

  • State requires two parameters: dp[i][j]
  • Base cases often involve edges: first row, first column
  • Recurrence combines values from multiple directions
  • Space can often be reduced from O(m×n) to O(n) by processing row-by-row

Pattern Recognition:

This is a grid traversal problem where:

  • State is 2D position in a grid
  • Recurrence sums contributions from allowed moves
  • Base cases are boundary conditions (edges)
Note

Key insight: The same problem-solving progression we learned in 1D—recursion → memoization → tabulation → optimization—works identically in 2D. The only difference is managing two dimensions instead of one!