2D Dynamic Programming: A Table, Not an Array

One-dimensional DP got away with a single array because its state was one moving part — a position, an amount. The problems here don’t fit in a line because their state has two independent parts, and dp[i][j] is how you hold both at once. Everything else — the recurrence, the base cases, the space trick — is the 1D recipe with a second index bolted on. So the only new question 2D DP asks is where that second dimension comes from, and there are three usual answers.

Where the second axis comes from

• Two sequences. When a problem compares two strings or arrays, dp[i][j] means “the answer for the first i of one and the first j of the other.” Longest Common Subsequence, Edit Distance, Distinct Subsequences, Interleaving String, and Regular Expression Matching all live on this grid — the rows walk one input, the columns the other.
• An actual grid. Unique Paths and Longest Increasing Path in a Matrix come with their two dimensions built in; the table is the board.
• A position plus a mode. Best Time to Buy and Sell Stock with Cooldown is a 1D walk over days with a second axis for what state you’re in — holding, sold, resting. Coin Change II and Target Sum add an axis for which coins or which running sum are in play. The second dimension here is a state you can be in, not a second sequence.

The recurrence reads its neighbors

In the two-string family, dp[i][j] depends on a tiny neighborhood — the cells directly up, left, and diagonally up-left — which is why a table works so cleanly there. (Grid-path, stock-state, and interval problems reach for different cells; the neighborhood is per-recurrence, not universal.) Edit Distance is the archetype: to turn the first i characters of one word into the first j of another,

if (a.charAt(i - 1) == b.charAt(j - 1)) {
    dp[i][j] = dp[i - 1][j - 1];                        // characters match: nothing to do
} else {
    dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],          // replace
                   Math.min(dp[i - 1][j], dp[i][j - 1])); // delete / insert
}

Those three neighbors are the three edits, and once you see that, the LCS/Edit-Distance pair reads the same way: a match takes the diagonal, a mismatch combines the neighbors. (Distinct Subsequences, Interleaving String, and regex matching share the two-index table but wire their cells together differently.) What dp[i][j] means determines which neighbors it combines and the order you fill the table — row by row, columns left to right.

Not every 2D problem fills top-to-bottom

Two problems here break the neat row-by-row order and are worth flagging so they don’t trip you. Longest Increasing Path in a Matrix has dependencies that don’t follow the grid — a cell’s answer depends on taller neighbors in any direction — so it’s cleaner as a memoized DFS than a bottom-up sweep, the recursion discovering the fill order for you. Burst Balloons is interval DP: dp[i][j] is over a range of balloons, and you build it by increasing range length rather than by index, which is a genuinely different fill pattern hiding in the same 2D table.

Rolling two rows

Because most of these recurrences reach back only one row, you rarely need the whole $O(mn)$ table in memory. Keep the previous row and the current one — or, with care about read order, a single row you overwrite left to right — and the space drops to $O(n)$ while the time stays $O(mn)$. It’s the same rolling-variable trick 1D DP uses to fall from $O(n)$ to $O(1)$, one dimension up: you never needed the rows you already finished.

The table behind a diff

The two-string grid runs every time you read a diff. git diff finds what changed between two versions of a file by aligning their lines — LCS-style, using Myers’ algorithm by default, a relative of the table above rather than that exact fill — and the added and removed lines are the non-matching cells. Spell-checkers and autocorrect rank suggestions by edit distance; bioinformatics aligns DNA with the same recurrence at genome scale. The line-level diff you read every day is this family of algorithms with whole lines standing in for characters — the interview problem running inside a tool most engineers touch daily without ever calling it DP. I tend to keep that connection in mind, because it’s the one that makes the abstract table feel like something worth getting right.

Get the base edges right first

The interior recurrence is the part everyone rehearses, but the bug that actually eats time is the base row and column — the empty-prefix cases that seed the table. In Edit Distance, dp[0][j] = j because turning an empty string into j characters takes j insertions, and dp[i][0] = i symmetrically; set those two edges wrong and every interior cell inherits the error without complaint. The order I trust for these is: name the two axes, write down what one cell means, fill in the base edges from that meaning, and only then write the recurrence that reads the neighbors. Do the edges last, as an afterthought, and you’ll spend the debugging time you thought you saved.

References

• NeetCode 150 — 2-D Dynamic Programming — the eleven problems built on a table.