Grid & 2D DP
What is this?
Some problems need two indices instead of one — your position in a grid, or how much of each of two strings you have used so far. Here each answer lives in a 2D table dp[i][j] and is built from a few nearby cells you already filled, like figuring out the cheapest path to a square from the squares just above and to its left. Once a cell is computed it is remembered, so the whole table fills in one sweep without ever redoing a square.
💡 Fun fact: The two-string version of this table is the engine behind tools you use daily —
git diff, spell-checkers, and DNA sequence aligners all compute a longest-common-subsequence or edit-distance grid exactly like the ones in this chapter.
🔓 The 7 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core idea: When the state needs two indices — a position in a grid, or a prefix of each of two strings — the DP becomes a 2D table
dp[i][j]filled from neighboring cells. Almost every famous string/grid DP is the same loop with a different "combine" rule: add the neighbors, take the min of three, or extend the diagonal on a match.
One loop, different combine rules
Get the base row/column and the direction of dependency right, and a cell just reads already-computed neighbors. Then collapse the table to a rolling row for O(n) space.
The problems
![The grid-DP family: 2D DP dp[i][j] from neighbors branches into seven problems from Unique Paths to LCS](https://maangioassets.blob.core.windows.net/diagrams/coding-interview/101/chapters/dynamic-programming/grid-dp/grid-dp-summary-diagram-2.svg)
- Unique Paths — the gentle intro: paths = from above + from left.
- Maximal Square / Minimum Falling Path Sum — min-of-neighbors recurrences over a grid.
- Paint House —
dp[i][color]with an adjacency constraint; state = your last choice. - Edit Distance, Longest Common Subsequence, Wildcard Matching — the two-string family: matches glide diagonally; the rest is the per-problem rule (3 operations, max-align, or
*'s two transitions).
Key takeaways
- Two indices ⇒ a 2D table; each cell combines a handful of neighbors.
- The family shares one loop — only the combine rule and base cases change.
- Matches move diagonally in two-string DPs (LCS, Edit Distance); mismatches branch.
- Collapse to a rolling row for O(min(m,n)) space once it works.
- Why interviewers love it: the 2D table is the most reused DP shape in real interviews (diff, alignment, grids).
Start here: Unique Paths (the template), then Longest Common Subsequence and Edit Distance.
Core idea: Walk down the row of houses once. For each house, the only thing the future cares about is which color you just used — so carry the cheapest total cost ending in each of the three colors, and at every house pick the cheaper of the two colors you're allowed to follow.
Problem, rephrased
You're repainting a street of n houses standing in a row. Each house must be painted exactly one of three colors — red, blue, or green — and your contractor quotes a different price per color per house (some houses are stucco, some brick, so green is cheap on one and pricey on another). The quotes come as a matrix costs, where costs[i][0], costs[i][1], costs[i][2] are the red/blue/green prices for house i.
There's one rule from the homeowners' association: no two adjacent houses may share a color (a block of identical houses looks dull). Minimize the total paint cost across the whole row.
Input costs |
Output | Why |
|---|---|---|
[[17,2,17],[16,16,5],[14,3,19]] |
10 |
blue(2) → green(5) → blue(3) = 10, all adjacent-different |
[[7,6,2]] |
2 |
one house, just take its cheapest color |
[[1,5,3],[2,9,4]] |
5 |
red(1) → green(4) = 5; red→red is illegal so 1+2 is out |
Colors are just labels 0/1/2; you return the minimum cost, not the coloring itself.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson