Unique Paths: 2D Grid Dynamic Programming

You have a robot sitting in the top-left corner of an m x n grid. It can only move right or down. How many distinct paths can it take to reach the bottom-right corner?

This is LeetCode 62: Unique Paths, and it is the problem that teaches you 2D grid DP. If you have solved Climbing Stairs and Coin Change, this is the natural next step. It takes the same "build a table, fill it cell by cell" idea and extends it from a 1D array to a 2D grid.

Why this problem matters

A huge number of interview problems involve grids. Minimum path sum, dungeon game, edit distance, longest common subsequence. They all share the same core mechanic: you define a 2D table, figure out what each cell depends on, and fill it in order.

Unique Paths is the simplest version of that pattern. There are no obstacles, no costs, no min/max decisions. Just counting. That makes it the perfect place to learn 2D grid DP before tackling the harder variants.

Once you internalize how to set up the table, define the recurrence, and handle the base cases for a 2D grid, every grid DP problem that follows will feel like a variation on this theme.

Starting with recursion

Think about the robot at position (r, c). It could have arrived from the cell above (r-1, c) or the cell to the left (r, c-1). So the number of paths to (r, c) is the sum of paths to those two neighbors.

def unique_paths(m, n):
    def helper(r, c):
        if r == 0 or c == 0:
            return 1
        return helper(r - 1, c) + helper(r, c - 1)

    return helper(m - 1, n - 1)

The base case: any cell in the first row or first column has exactly 1 path to it (all right moves, or all down moves). Everything else branches into two recursive calls.

This is correct, but it is slow. Each call branches into two more, and the recursion tree grows exponentially. For a 20x20 grid, you are looking at billions of calls. The time complexity is roughly O(2^(m+n)).

Adding memoization (top-down DP)

Cache results so you never solve the same subproblem twice.

def unique_paths(m, n):
    memo = {}

    def helper(r, c):
        if r == 0 or c == 0:
            return 1
        if (r, c) in memo:
            return memo[(r, c)]
        memo[(r, c)] = helper(r - 1, c) + helper(r, c - 1)
        return memo[(r, c)]

    return helper(m - 1, n - 1)

Now each of the m * n cells is computed once. Time drops to O(m * n). Space is O(m * n) for the memo dictionary plus the call stack. A massive improvement, but we can clean it up further.

Building the 2D DP table (bottom-up)

Instead of recursing from the destination back to the start, build the table from the top-left corner forward. Define dp[r][c] as the number of unique paths to reach cell (r, c).

The recurrence:

• dp[0][c] = 1 for all columns (only way is to go right)
• dp[r][0] = 1 for all rows (only way is to go down)
• dp[r][c] = dp[r-1][c] + dp[r][c-1] for everything else

Let's trace through a 3x4 grid:

Each cell is the sum of the cell above it and the cell to its left. The answer sits in the bottom-right corner.

def unique_paths(m, n):
    dp = [[0] * n for _ in range(m)]

    # Base cases: first row and first column
    for c in range(n):
        dp[0][c] = 1
    for r in range(m):
        dp[r][0] = 1

    # Fill the rest
    for r in range(1, m):
        for c in range(1, n):
            dp[r][c] = dp[r - 1][c] + dp[r][c - 1]

    return dp[m - 1][n - 1]

Time: O(m * n). We visit every cell exactly once.

Space: O(m * n). We store the full 2D table.

No recursion, no call stack, no hash map overhead. Just a nested loop filling a grid from top-left to bottom-right. But we can do better on space.

Optimizing to O(n) space

Look at the recurrence: dp[r][c] = dp[r-1][c] + dp[r][c-1]. Each cell depends on the cell directly above it and the cell to its left. When processing row r, we only need row r-1. We do not need rows r-2, r-3, or anything earlier.

That means a single 1D array of length n is enough. As we process each row, the array holds the previous row's values. When we update dp[c], the old value at dp[c] is the "from above" contribution, and dp[c-1] (already updated) is the "from left" contribution.

def unique_paths(m, n):
    dp = [1] * n  # First row: all 1s

    for r in range(1, m):
        for c in range(1, n):
            dp[c] = dp[c] + dp[c - 1]

    return dp[n - 1]

Same O(m * n) time, but now O(n) space. One row instead of an entire grid. This is the optimal solution.

Let's trace this for a 3x4 grid:

• After row 0: [1, 1, 1, 1] (base case)
• Row 1, c=1: dp[1] = 1 + 1 = 2. c=2: dp[2] = 1 + 2 = 3. c=3: dp[3] = 1 + 3 = 4. Row 1: [1, 2, 3, 4]
• Row 2, c=1: dp[1] = 2 + 1 = 3. c=2: dp[2] = 3 + 3 = 6. c=3: dp[3] = 4 + 6 = 10. Row 2: [1, 3, 6, 10]
• Return dp[3] = 10

Complexity analysis

The progression is the same one you saw in Climbing Stairs:

1. Write the recursive solution to get the logic right.
2. Add memoization to eliminate redundant work.
3. Convert to bottom-up to remove recursion overhead.
4. Optimize space by keeping only what the recurrence needs.

That four-step pipeline works on nearly every DP problem. The only thing that changes is the shape of the table (1D vs 2D) and the recurrence.

Edge cases to watch for

• 1x1 grid: return 1. The robot is already at the destination.
• 1xn or mx1 grid: return 1. There is only one path (all right or all down).
• Large grids: m and n can be up to 100. The O(n) space solution handles this instantly and the result fits in a 64-bit integer.

The building blocks

This problem is built on a single reusable pattern: 2D grid DP. The idea generalizes the linear DP you learned in Climbing Stairs and Coin Change to two dimensions. Instead of a 1D array where dp[i] depends on previous entries, you have a 2D table where dp[r][c] depends on neighboring cells.

The pattern has a specific shape:

• State: dp[r][c] represents the answer for the subproblem at position (r, c) in the grid
• Transition: dp[r][c] combines values from adjacent cells (above, left, diagonal, etc.)
• Base cases: first row, first column, or specific boundary cells
• Space optimization: if the recurrence only looks at the current and previous row, collapse to a 1D array

The same building block appears in many other problems:

• Minimum Path Sum (LeetCode 64): same grid structure, but dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1]). Counting becomes minimizing.
• Unique Paths II (LeetCode 63): same problem, but with obstacles. Cells with obstacles get dp[r][c] = 0.
• Edit Distance (LeetCode 72): 2D table over two strings instead of a grid. Each cell depends on the cell above, the cell to the left, and the diagonal.
• Longest Common Subsequence (LeetCode 1143): another 2D table over two sequences with a similar fill pattern.

Once you internalize 2D grid DP as a building block, these problems stop looking like separate challenges. They are all the same structure with different transition functions.

From understanding to recall

You have read through four versions of the solution, from naive recursion to space-optimized DP. The logic makes sense. But here is the honest truth: understanding a solution and producing it from scratch under interview pressure are very different skills.

In an interview, nobody hands you the recurrence. You have to look at the grid, figure out that dp[r][c] depends on the cell above and the cell to the left, write the base cases, and implement the nested loop. That takes practice, not just comprehension.

Spaced repetition bridges that gap. You revisit this problem at increasing intervals, each time writing the 2D table setup and the space optimization from memory. After a few reps, the pattern is automatic. You see a grid problem and your hands know what to type.

The 2D grid DP pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is a far more effective strategy than grinding problems randomly and hoping the patterns stick.

Related posts

• Climbing Stairs - Your first DP problem, teaching the same recursion-to-table pipeline in 1D
• Coin Change - Classic 1D DP with variable lookback, the natural bridge between Climbing Stairs and 2D grid problems