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.
Unique Paths
Core idea: A robot can only move right or down, so the only way to reach a cell is from the cell directly above it or the cell directly to its left. That means the number of paths to any cell is just the sum of the paths to those two neighbors:
dp[i][j] = dp[i-1][j] + dp[i][j-1]. Fill the grid from the top-left, and the bottom-right holds your answer.
Problem, rephrased
A delivery drone starts in the top-left corner of a warehouse laid out as an m × n grid of cells. It can only fly one cell right or one cell down at a time — never up, never left, never diagonal. The dispatcher in the bottom-right corner wants to know: how many distinct flight paths connect the start to the dock?
Every path is a sequence of moves; two paths are different if at any step the drone chose right where the other chose down. Your job is to count them, not to list them.
Inputs and outputs:
Input (m rows × n cols) |
Output | Why |
|---|---|---|
3 × 7 |
28 | Classic LeetCode 62 example |
3 × 2 |
3 | Down-down-right, down-right-down, right-down-down |
1 × 1 |
1 | Already at the dock; the empty path counts |
1 × 10 |
1 | Only one row → must go right every step |
7 × 3 |
28 | Same as 3 × 7 — the grid is symmetric in m and n |
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