Explore 2-D dynamic programming interview patterns: unique paths, LCS, edit distance, regex matching and burst balloons. Watch each table fill cell by cell.
The pattern
2-D Dynamic Programming: a table of subproblems
Same idea as 1-D DP, but each subproblem is described by two numbers: a cell of a grid, a position in each of two strings, a coin and an amount, or the ends of a range. The answers go in a 2-D table, filled in an order where every cell's inputs are ready.
1Two things change, so the table has two sides
When a subproblem is described by two numbers (a cell's row and column, a position in each of two strings), store the answers in a grid. Here each cell counts the paths from it to the corner.
2Two strings: match or skip
For two strings, cell (i, j) answers the question for the rests from i and j. A matching pair of letters uses the diagonal; otherwise the cell takes the better of moving on in one string or the other.
3Fill in an order that works
Each cell reads cells that must already be filled. Most of these tables fill from the bottom-right corner back to the top-left; interval problems like Burst Balloons fill short ranges before long ones.
How to spot the table
- Two strings (LCS, edit distance, regex): positions i and j.
- A grid (paths, increasing paths): the cell itself.
- Items and a budget (coins, target sums): which items are left and the amount.
- A range that splits (Burst Balloons): its two ends; think about the last operation.
Reading the pictures
- The table is drawn as a grid; blue cells along the edges are the letters or values each row and column stands for (∅ is “nothing left”).
- Teal is the cell being filled, amber the cells it reads, green the answer.
- For an editable grid DP, see the Dynamic Programming visualizer.
NeetCode 150 · 2-D Dynamic Programming
All 11 problems
Pick a problem to see it solved step by step. They're in NeetCode's order, roughly easiest first.
Unique Paths
MediumBlind 75A robot starts at the top-left of an m × n grid and moves only right or down. How many different paths reach the bottom-right corner?
m = 3, n = 7
paths[r][c] = ways from this cell to the bottom-right corner
variables
- grid
- 3 × 7
Press Play or Step to watch the solution run.
Brute force vs the pattern
On this input:
- Pattern: O(m × n)
- 21 ops
- Brute force
- 55 ops
On a bigger input (10 × 10):
- Pattern
- 100 ops
- Brute force
- 97,239 ops
Recursion with no memory: from each cell, try right and try down. It walks every path one by one, and there are tens of thousands of them on a 10 × 10 grid.
“ops” is an illustrative count of selected algorithm operations, with estimates for sorting. It excludes drawing and frame creation and is not a timing benchmark. The complexity describes the Python solution. On small inputs a brute-force search may find the answer sooner.
How it works: Unique Paths
Step by step
- Cell being filled
- The two cells it adds
- The answer
Press Start or Step: the step the animation is on lights up below.
- 1
Fill from the bottom-right
row = [1] * n - 2
Last row / column: 1 path
- 3
Right + down
new_row[j] = new_row[j + 1] + row[j] - 4
paths(0, 0)
return row[0]
The last move into the corner came from the left or from above, or equally: the first move from a cell goes right or down. So paths(r, c) = paths(r + 1, c) + paths(r, c + 1).
The bottom row and right column have exactly one path each (straight to the corner). Fill the rest from the bottom-right. NeetCode keeps just one row at a time, updating it in place.
Spot it in an interview
- Counting paths on a grid with moves in two directions: each cell adds its two neighbours.
- The model for most 2-D DP: a table whose entries depend on their neighbours.
Each cell is one addition; only one row is kept.
Credits
Learn more from NeetCode
The problem list and order come from the NeetCode 150 by NeetCode (neetcode.io). The solutions here follow the approaches NeetCode teaches in the linked videos; the animations, explanations and code were written for CodeQuest. If these help, NeetCode's videos and site are well worth your time.
Problem statements are summarised in our own words; the full versions are on LeetCode.