LeetCode 62 · 2-D DP

Unique Paths, explained with a picture

A delivery robot that only goes right or down.

Medium2-D DP
▶ Watch it step by step

The problem

A robot stands in the top-left corner of an m × n grid and wants to reach the bottom-right corner. It may only move right or down. How many different routes are there?

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

Picture it

Picture a grid of street corners. The delivery robot starts at the top-left and can only drive right or down, never back. We write on every corner the number of different routes that reach it. Corners on the top row and left column have only 1 route (keep going straight). Any other corner can only be entered from the corner above it or from the corner to its left, so its number is those two numbers added together. Fill the grid row by row; the number in the bottom-right corner is the answer.

How to recognise it

  • You must count routes, not list them or find the shortest one.
  • Moves only go forward (right or down), so you can never return to a cell and the problem has no cycles.
  • The number of routes into a cell depends only on two neighbouring cells that you can compute first.
  • The same sub-question ("how many ways to reach this cell?") is asked again and again from different directions.
  • Sizes up to 100 × 100 rule out enumerating routes one by one: the answer for a 100 × 100 grid has 59 digits, so even a computer cannot walk every route.

Start with brute force

Recursion from the start: at each cell try going right and going down, and add up the routes found from each.

def paths_brute(m, n):
    def go(r, c):
        if r == m - 1 and c == n - 1:
            return 1
        total = 0
        if r + 1 < m: total += go(r + 1, c)
        if c + 1 < n: total += go(r, c + 1)
        return total
    return go(0, 0)

Every route ends in a call that returns 1, so the number of calls is at least the answer itself. For 18 × 18 that is already about 4.7 × 10^9 calls, and 100 × 100 is hopeless. Time is exponential, roughly O(2^(m+n)), and space is O(m + n) for the recursion depth.

From brute force to the idea

  1. Find the waste. go(1, 1) is reached by many different routes, and each time the whole subtree below it is recomputed from scratch.
  2. Count backwards, not forwards. Instead of "how many routes leave this cell", ask "how many routes arrive at this cell". A robot enters (r, c) only from above (r − 1, c) or from the left (r, c − 1), so ways[r][c] = ways[r-1][c] + ways[r][c-1].
  3. Fix the border. In the first row and first column there is only one way in (straight along the edge), so the table starts filled with 1s. Row 0 and column 0 are never overwritten.
  4. Fill in order. Going row by row, both neighbours are already finished when a cell is computed. The bottom-right cell holds the answer.

This is the key idea: each cell is solved once, and its value is the sum of the two cells it can be entered from.

The key idea

paths[r][c] = paths[r − 1][c] + paths[r][c − 1]. Fill in row order. O(m × n).

Python solution

def unique_paths(m, n):
    ways = [[1] * n for _ in range(m)]   # first row and column: one way
    for r in range(1, m):
        for c in range(1, n):
            ways[r][c] = ways[r - 1][c] + ways[r][c - 1]   # from above + from the left
    return ways[m - 1][n - 1]

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceExponential, about 2^(m+n): one call per route and moreO(m + n): recursion depth
DP table (shown code)O(m · n): each cell is filled once with one additionO(m · n): the whole table is kept, though only the previous row is needed

Edge cases

  • One row or one column (m = 1 or n = 1): the table is all 1s and the answer is 1. unique_paths(1, 100) is 1.
  • 1 × 1 grid: the start is the finish, so the answer is 1 and both loops are skipped.
  • Symmetry: unique_paths(3, 2) and unique_paths(2, 3) are both 3, because rows and columns play the same role.
  • Large grids: Python integers do not overflow. LeetCode promises the answer fits in 2 × 10^9, but in a fixed-width language the table values could overflow for sizes beyond the limits.
  • Closed form: the answer equals the number of ways to choose which of the m + n − 2 moves go down, C(m + n − 2, m − 1), for example C(8, 2) = 28 for 3 × 7.

Common mistakes

  • Starting the table with zeros and forgetting to set the first row and column to 1, so every cell stays 0.
  • Swapping m and n when building the table, which gives an IndexError on non-square grids.
  • Counting with a "visited" set, which stops different routes from sharing a cell and undercounts.
  • Starting the loops at 0, which reads ways[-1] and silently wraps around to the last row or column.
Your turn: blocked cells

Some cells of the grid are blocked (marked 1; free cells are 0). The robot still moves only right or down and cannot enter a blocked cell. Count the routes from the top-left to the bottom-right. Describe your approach, then write it if you like.

Compare with our answer

Same table, but a blocked cell always holds 0, and the first row and column are no longer automatically 1: a block on the edge cuts off everything behind it.

def paths_obstacles(g):
    m, n = len(g), len(g[0])
    ways = [[0] * n for _ in range(m)]
    for r in range(m):
        for c in range(n):
            if g[r][c]:
                continue                     # blocked: zero routes
            if r == 0 and c == 0:
                ways[r][c] = 1
            else:
                up = ways[r - 1][c] if r else 0
                left = ways[r][c - 1] if c else 0
                ways[r][c] = up + left
    return ways[m - 1][n - 1]

[[0,0,0],[0,1,0],[0,0,0]] gives 2, [[0,1],[0,0]] gives 1, and a blocked start or finish gives 0. Time and space O(m · n).

A strong answer mentions: setting blocked cells to 0, handling the first row and column separately (a block cuts off the rest of the edge), and the blocked-start case.

Check what stuck

1. Count the routes from the top-left to the bottom-right of a grid with some blocked cells, moving only right or down. Which approach fits best?

2. Why is the shown code O(m · n) when the recursive version is exponential?

3. A learner builds ways = [[0] * n for _ in range(m)], sets only ways[0][0] = 1, and keeps both loops starting at 1. What does unique_paths(3, 7) return?

Score 60% or more and the lesson is marked complete.