Unique Paths

A robot stands in the top-left corner of a grid. It can only move right or down. How many distinct paths reach the bottom-right corner?

dp[row][col] = dp[row-1][col] + dp[row][col-1]

Every cell is the sum of the cell above it and the cell to its left.

See it build

m = 3, n = 7 → 28 distinct paths to E.

The Problem

One robot, two moves

The grid is m rows by n columns. The robot starts at S and must reach E using only two moves: right, or down. Every cell along the way is reachable by some number of distinct routes, and that count is what we're solving for.

S start E end → move right ↓ move down

First row

Only reachable by moving right, again and again. Every cell here is reachable exactly one way.

First column

Only reachable by moving down, again and again. Every cell here is reachable exactly one way too.

The Key Idea

Every interior cell has exactly two doors in

To stand on any interior cell, the robot's last step was either a move down from the cell above, or a move right from the cell to the left. There is no third way in, so the number of paths to a cell is just the paths from above, plus the paths from the left.

from abovedp[row-1][col]

from leftdp[row][col-1]

this celldp[row][col]

dp[row][col] = dp[row-1][col] + dp[row][col-1]

Try It

Watch the grid fill, one cell at a time

Press play, or step through it by hand. Switch to the 1D view to see the exact same logic compressed into a single row of memory.

Row 0 · first row, boundary cells

before this pass

this pass

Press play or step forward to begin.

The amber ring marks the value used from above; the teal ring marks the value used from the left.

The Result

The filled grid

For m = 3, n = 7, the recurrence above produces this grid. The bottom-right corner is the answer.

28 distinct paths from S to E.

The Code

Same idea, two implementations

The 1D version drops the full grid and keeps only one row alive, overwriting it in place as it scans left to right.

First row and first column are boundary cases: exactly one way in, by definition, not by the recurrence.

Complexity

What the optimization actually buys you

2D DP

TimeO(m · n)

SpaceO(m · n)

1D DP

TimeO(m · n)

SpaceO(n)

Same time complexity, far less memory: only one row needs to stay alive at any point.

Pattern To Remember

Whenever a cell depends only on its top and left neighbors, you're looking at grid DP.

dp[row][col] = something(top) + something(left)

Same shape shows up in Minimum Path Sum, Unique Paths II, Triangle, and a good chunk of edit-distance-style problems.