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.