2D dynamic programming

What it is

A 2D dynamic program indexes its state by a pair of numbers rather than one, most often "how much of sequence A have I consumed" crossed with "how much of sequence B have I consumed," or "row" crossed with "column" on an actual grid. The table is conceptually rows × cols, and each cell's value comes from a small fixed set of already-computed neighbors — directly above, directly to the left, or diagonally up-left. The two-dimensional shape is what you get whenever a problem compares or merges two sequences, or asks about a literal 2D structure like a matrix.

When it applies

• You are comparing or transforming two strings/sequences and the natural question is "given the first i characters of one and the first j of the other, what's the answer" — edit distance, longest common subsequence, and interleaving checks all have this shape.
• You are working on an actual grid and a cell's value depends only on the cell above and the cell to the left (plus sometimes the diagonal) — path counting, path-sum minimization, or the largest square/rectangle of a given value.
• It does not apply once a single index (one sequence, one array) is enough to describe "how much have I processed so far" — that collapses to a 1D DP, and forcing a second dimension you don't need just adds complexity.
• It also stops applying once the recurrence needs to look outside the three standard neighbors (e.g., a cell can depend on any earlier row and column, not just the adjacent ones) — that usually needs a different technique (interval DP, or precomputed prefix aggregates) layered on top.

Tells in the problem

• "Given two strings, find the minimum number of operations to turn one into the other" — edit distance, transition reads the diagonal on a match, three neighbors otherwise.
• "Can this string be split so that it interleaves two other strings, preserving each one's order" — state is (i, j), consumed-from-first crossed with consumed-from-second; the position in the merged string is redundant since it equals i + j.
• "Largest square/rectangle of ones (or of a repeated value) in a binary matrix" — a corner-anchored DP whose transition is a min over three neighbors, not a search.
• "Number of distinct paths through a grid moving only right/down" — first-row and first-column base cases are all 1, then each interior cell sums its two neighbors.
• Two sequences of different roles appear together (a pattern and a text, an original and a transformed version) and the question is about compatibility or minimum edits between them — that pairing is the strongest tell for a two-index state.

The classic mistake

A common shape for this bug is a state tuple with a redundant third dimension — for example, separately tracking "position in the merged output" alongside (i, j) when consuming from two sources, forgetting that the merged position is always i + j and adds nothing. The result is a needlessly 3D table, extra bugs in keeping the dimensions in sync, and a much harder correctness argument. A second common mistake is filling the table in the wrong order so a cell's dependency (usually above-left) hasn't been computed yet, especially when the DP is space-optimized down to one rolling row — overwriting dp[j-1] before reading its old value as the "diagonal" input is the specific bug to watch for. Before compressing to O(n) space, write out on paper exactly which of the row's old and new values each transition needs.

Questions to start with

• Unique Paths — the purest form: every cell sums exactly two neighbors, and the base cases (first row and column) are trivial.
• Minimum Path Sum — the same two-neighbor structure with min and an added grid value instead of a sum of counts.
• Interleaving String — the two-sequence version, where the key realization is that the state is only (i, j), not a third position in the output.
• Maximal Square — a corner-anchored DP reading three neighbors (min, not sum), which is a different transition shape from simple path counting.
• Edit Distance — the full three-way transition (insert, delete, replace) with a diagonal shortcut on a matching character, the canonical hard 2D DP.