Pattern 4: Grid DP
When the DP has two dimensions, the table becomes a grid:
dp[r][c]. Each cell is built from already-computed neighboring cells — and watching the table fill in makes the recurrence obvious.
Try it first: Unique Paths
Before reading the theory, try to solve it. You can start with brute force, you can fail — the point is to feel the problem. The theory comes right below.
A robot is in the top-left corner of an m × n grid and wants to reach the bottom-right corner, moving only down or right. How many distinct paths are there?
Example: m = 3, n = 7 → 28.
Tried it? Counting all the paths by brute force (recursion without a cache) is exponential. The theory below fills a 2D table in O(m·n).
The theory: each cell comes from its neighbors
In Unique Paths, the robot only moves down or to the right. So, to
reach cell (r, c), it came from above (r-1, c) or from the left
(r, c-1). The number of paths to (r, c) is the sum of the paths to those
two:
dp[r][c] = dp[r-1][c] + dp[r][c-1]
base cases: 1st row and 1st column = 1 (there's only one straight-line path)
Fill the table row by row; each cell uses the one above and the one to the left,
which have already been computed. Watch the dp grid fill in, with the cursor on
the current cell:
The answer is dp[m-1][n-1] — the bottom-right corner.
Why is it O(m·n)?
There are m × n cells (states), each computed in O(1) (one sum) →
O(m·n) time, O(m·n) space. Again the "states × cost": here the
number of states is two-dimensional. And, since each row only depends on the
previous one, you can reduce the space to O(n) (keeping just one row) — the
same "I only need the last states" idea from 1D DP.
The shape of every grid DP
Many 2D problems follow this template, changing only the recurrence and the operation:
| Problem | dp[r][c] means | Recurrence |
|---|---|---|
| Unique Paths | paths to (r,c) | dp[r-1][c] + dp[r][c-1] |
| Minimum Path Sum | smallest sum to (r,c) | grid[r][c] + min(above, left) |
| Maximal Square | side of the largest square at (r,c) | 1 + min(above, left, diagonal) if '1' |
The method is the same as the other DPs: what dp[r][c] means, which
neighboring cells it depends on, and the base cases (usually the first row
and/or column). The only difference is the extra dimension.
Connection to the Matrix section: there you filled grids with traversals (spiral, DFS); here the grid is a table of answers that is built by recurrence. Same 2D structure, different use.
🧠 Review quiz
0/41. In Unique Paths, what is the recurrence and why?
2. What are the base cases of Unique Paths?
3. Why is Unique Paths O(m·n) time?
4. 'Smallest path sum from top-left to bottom-right in a grid of costs.' How do you adapt it?
Summary
- Grid DP: a 2D table
dp[r][c], each cell coming from the already-computed neighbors. - Unique Paths:
dp[r][c] = dp[r-1][c] + dp[r][c-1], borders = 1. - O(m·n) time; space reducible to O(n) (one row).
- Same template as the other DPs, with one more dimension.
Next lesson: comparing two sequences in a 2D table — string DP.