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.

flowchart TD A["Two indices i and j"] --> B["Build a 2D table dp i j"] B --> C["Fill the base row and column"] C --> D["Each cell combines its neighbors"] D --> E["Collapse to a rolling row to save space"]

💡 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.

The problems

The grid-DP family: 2D DP dp[i][j] from neighbors branches into seven problems from Unique Paths to LCS

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.

Minimum Falling Path Sum

Core idea: Sweep the matrix row by row, top to bottom, keeping dp[i][j] = the cheapest cost to fall onto cell (i, j) from somewhere in the top row. Each cell can only be reached from the three cells directly above it — straight up, up-left, up-right — so dp[i][j] = matrix[i][j] + min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]). The only subtlety is clamping at the columns: column 0 has no up-left neighbour and column n-1 has no up-right neighbour, so you drop the missing terms. The answer is the minimum of the last row — the cheapest place to land after falling all the way down.

Problem, rephrased

Imagine a square mountainside rendered as an n × n grid of descent costs. A skier starts at any cell in the top row and drops one row at a time. From a cell, a single drop lands either straight down, diagonally down-left, or diagonally down-right — the three cells touching it from above-the-other-way. The cost of a run is the sum of every cell the skier touches, including the starting cell and the final landing cell on the bottom row. Find the cheapest possible run from the top all the way to the bottom.

Formally (LeetCode 931): given an n × n integer matrix, a falling path starts at any element in the first row and chooses, at each step, the element directly below or diagonally below-left / below-right. Return the minimum sum of all elements along some falling path.

The values can be negative, so the cheapest path is not simply "always pick the smallest neighbour" — a greedy step into a small number can strand you next to two large ones on the row below.

Input (matrix)	Output	Why
`[[2,1,3],[6,5,4],[7,8,9]]`	`13`	`1 → 5 → 7` or `1 → 4 → 8` both total `13`
`[[-19,57],[-40,-5]]`	`-59`	`-19 → -40` is the cheapest two-row fall
`[[17]]`	`17`	A single cell is a complete (length-1) path
`[[1,2,3],[4,5,6],[7,8,9]]`	`12`	`1 → 4 → 7` down the left edge beats `1 → 5 → 7` (= 13)

Foundations

Grid & 2D DP

What is this?

One loop, different combine rules

The problems

Key takeaways

Minimum Falling Path Sum

Problem, rephrased

Sign in to continue reading

Foundations

Grid & 2D DP

What is this?

One loop, different combine rules

The problems

Key takeaways

Minimum Falling Path Sum

Problem, rephrased

Sign in to continue reading

Sign in to MAANG.io