Unique Paths
Count the routes across a grid — the clearest introduction to filling a 2-D table, where each cell is the sum of two neighbours
Problem Statement
A robot starts at the top-left of an m × n grid. It can only move right or down. How many different paths reach the bottom-right corner?
Input: m = 3, n = 7
Output: 28
Input: m = 3, n = 2
Output: 3
down → down → right
down → right → down
right → down → downIntuition
Try it by hand on a 3 × 2 grid and you get 3. Try 3 × 7 and counting by hand stops being possible — the answer is 28, and enumerating 28 routes to be sure is not a method.
The recursive statement is easy: "paths to a cell = paths to the cell above + paths to the cell on the left", because those are the only two squares that can lead here.
That recursion alone is O(2^(m+n)). Same problem as Climbing Stairs — the same cells get recomputed over and over from different directions.
The insight
Turn the recursion around. Instead of asking "how do I reach the end", fill in how many ways reach each cell, starting from the corner you began at.
paths[r][c] = paths[r-1][c] + paths[r][c-1]
└ from above └ from the leftFill the grid top-left to bottom-right, and every cell you need has already been computed. No recursion, no cache — just a table filled in the right order.
This is the same idea as climbing stairs, one dimension up. Stairs looked back at two earlier positions; this looks back at two earlier cells.
The base cases matter
The first row and first column are special. There is only one way to reach any cell in the top row — keep moving right, with no choice ever offered. Same for the first column going down.
So they are all 1, and they are what the rest of the table builds on.
Approach
Make an m × n table
paths[r][c] will hold the number of ways to reach row r, column c.
Fill the first row and first column with 1
Only one route exists along an edge — you never get a choice.
Fill the rest, row by row
paths[r][c] = paths[r-1][c] + paths[r][c-1]. Both are already filled because you are moving down and right.
Solution
def unique_paths(m: int, n: int) -> int:
"""Count right/down paths across an m x n grid.
paths[r][c] = paths[r-1][c] + paths[r][c-1]
Filling top-left to bottom-right means both are already known.
"""
paths = [[1] * n for _ in range(m)]
for row in range(1, m):
for col in range(1, n):
paths[row][col] = paths[row - 1][col] + paths[row][col - 1]
return paths[m - 1][n - 1]Initialising everything to 1 handles both base cases at once — the loops then start at 1, so the edges are never overwritten.
Shrinking to one row — O(n) space
A cell only needs the value above it and the value to its left. Once a row is complete, the row before it is never read again.
So keep a single row and overwrite it in place:
row = [1, 1, 1, 1]
for each remaining row:
for col from 1:
row[col] = row[col] + row[col - 1]
└ above └ left (already updated this pass)row[col] still holds the previous row's value at the moment you read it — that is "above". Memory drops from O(m×n) to O(n) with no loss of clarity once you see why.
Complexity Analysis
Time Complexity
O(m × n)
Space Complexity
O(m × n)
Time — every cell is filled once with one addition. Compare the naive recursion at O(2^(m+n)): for a 3×7 grid that is thousands of calls instead of 21.
Space — the table. Reducible to O(n) with the single-row version above, or O(1) with the combinatorics formula below.
There is a closed-form answer
Every path is exactly m - 1 downs and n - 1 rights in some order. Choosing which positions are the downs gives:
C(m + n - 2, m - 1)For m=3, n=7: C(8, 2) = 28. ✓
That is O(min(m,n)) time and O(1) space — faster than the DP. It is worth knowing, but the table is the transferable skill: Unique Paths II adds obstacles and the formula collapses immediately, while the table needs one extra line.
Edge Cases
Related Problems
- Climbing Stairs — the same recurrence in one dimension
- Longest Common Subsequence — the other essential 2-D table
- Dynamic Programming — why filling in the right order removes recursion entirely