Interactive Lab · DSA & Algorithms

Fill the 2D DP table: Longest Common Subsequence & Edit Distance

Two strings, one grid. Cell dp[i][j] holds the answer for the first i letters of the top-left word and the first j letters of the other, and every cell is built from just three neighbours: diagonal, above and left. That's the whole of 2D dynamic programming. Plain recursion asks the same (i, j) question again and again, so its call count explodes; the table asks each one exactly once. Type two words, scrub the fill, watch the arrows say which neighbour won, then trace the answer back out of the grid.

▶ The playground, type two strings, then scrub the table filling in

problem

A B

try

Rows are letters of A, columns are letters of B. The orange cell is being filled, the blue cells are the neighbours it may read, and the green one is the neighbour that won. The little arrow in each cell remembers that choice (↖ diagonal, ↑ above, ← left), and after the fill those arrows are followed back from the corner to rebuild the answer.

step 0 / 0

speed 3 / 5

🧭 Where this fits

2D string DP is everywhere text is compared: git diff and diff are built on LCS, spell-checkers and “did you mean…?” rank words by edit distance, and DNA sequence alignment (Needleman–Wunsch) is the same grid with scored moves. In interviews, LCS and Edit Distance are the templates for a whole family: longest common substring, shortest common supersequence, distinct subsequences, wildcard and regex matching.

The code that's actually running, one grid, filled once

🔮 Predict, then test

Pick LCS and type two 10-letter strings with no letters in common, say ABCDEFGHIJ and KLMNOPQRST. The table has just 11 × 11 = 121 cells. Predict: how many calls does the naive recursion make? Every mismatch branches twice, into (i−1, j) and (i, j−1), and those branches keep meeting at the same cells, so the count is 369,511, about 3,000× the table. Now switch to Edit Distance on KITTEN → SITTING and trace the answer: which three edits does the grid find?

The takeaway

Your new mental model of 2D dynamic programming

Define the cell first. dp[i][j] = the answer for prefixes A[:i] and B[:j]. Once that sentence is right, the recurrence nearly writes itself.
Three neighbours, one decision. Letters match → take the diagonal (LCS +1, edit distance +0). Otherwise LCS keeps the better of above/left; edit distance pays 1 + the cheapest of replace (↖), delete (↑) or insert (←).
Base cases are the empty prefixes. Row 0 and column 0: LCS with an empty string is 0; turning a prefix into empty costs its length.
Overlapping subproblems are the whole point. Recursion re-solves the same (i, j) exponentially many times; the table solves each once: O(m·n) time.
The arrows are the answer. Store which neighbour won and you can walk back from dp[m][n] to recover the actual subsequence or the exact edit script, not just its size.

← Coin Change (1D DP)Placement prep →Try: Recursion