Visual walkthrough — DP problems — Longest Common Subsequence (LCS)

We use two short strings the whole way so you can see every cell: $X=\text{AGCAT},Y=\text{GAC}.$

Step 1 — What "subsequence" even means (the sliding picture)

WHAT. A subsequence is what you get by walking left-to-right through a string and, at each character, choosing keep or skip — never reordering.

WHY. Everything about LCS is trapped inside this one rule: order is sacred, gaps are free. If you forget "gaps are free" you slide into Longest Common Substring; if you forget "order is sacred" you get a set, not a sequence.

PICTURE. In the figure below, AGCAT is on top. The green highlighted letters A_C_T (skipping G and A) form a valid subsequence: the kept letters march left-to-right. The red attempt A_C_A reordered? — impossible, you cannot walk backwards.

Step 2 — Naming the goal: the prefix quantity $L(i,j)$

WHAT. We invent a number. Read the first $i$ letters of $X$ and the first $j$ letters of $Y$ — call those the prefixes. Then $L(i,j)=\underset{\text{just a count}}{\underbrace{\text{length}}}\text{ of the longest common subsequence of }\underset{\text{first }i\text{ of }X}{\underbrace{X[\mathrm{1..}i]}}\text{ and }\underset{\text{first }j\text{ of }Y}{\underbrace{Y[\mathrm{1..}j]}}.$

WHY a prefix quantity? Because we cannot solve AGCAT vs GAC in one leap. We instead build a grid where every cell is a smaller version of the same question. Solve the tiny ones, reuse them for the bigger ones — that reuse is the whole idea of Dynamic Programming.

PICTURE. The grid: rows are prefixes of $X$ (growing downward), columns are prefixes of $Y$ (growing rightward). The cell at row $i$, column $j$ is the number $L(i,j)$. Our final answer lives in the shaded bottom-right corner.

Step 3 — Why look at the LAST characters?

WHAT. To fill cell $L(i,j)$ we stare only at the two newest letters: $x_i$ (the $i$-th letter of $X$) and $y_j$ (the $j$-th letter of $Y$).

WHY only the last? A subsequence of the prefixes must end somewhere. Either the very last letters help end it, or they don't. That's a clean two-way split — and a two-way split is exactly what a recurrence needs. We never have to think about the middle.

PICTURE. Two prefix bars, one for each string, with the final letter of each circled. A hinge sits between the circles asking one question: same letter, or different? Two doors lead out — the "match" door and the "mismatch" door.

Step 4 — The MATCH door: $x_i=y_j$

WHAT. Suppose the two newest letters are equal. Then we grab that shared letter, pair it up as the ending of our LCS, and shrink both prefixes by one: $L(i,j)=\underset{\begin{array}{c}\text{the newly}\\ \text{shared letter}\end{array}}{\underbrace{1}}+\underset{\begin{array}{c}\text{best LCS of both}\\ \text{prefixes, one shorter each}\end{array}}{\underbrace{L(i-1,j-1)}}.$

WHY the $+1$, and WHY the diagonal cell? The $+1$ is the reward for finding a genuinely new shared character. We recurse into $L(i-1,j-1)$ — the diagonal neighbour — because consuming a letter from each string moves us up one row and left one column at once. That single diagonal step is "use both letters."

Is grabbing the pair always safe? Yes. If some optimal LCS ended differently, you could swap its ending for this matched pair without shortening it — so pairing loses nothing. (This is the exchange argument the parent note steel-manned.)

PICTURE. Both final letters are C. A diagonal arrow jumps from the diagonal neighbour into the current cell, carrying the value and adding one.

Step 5 — The MISMATCH door: $x_i\ne y_j$

WHAT. Now the newest letters differ. They cannot both be the final letter of one common subsequence (a sequence has one ending, and these two letters disagree). So at least one of them is useless as an endpoint — throw one away and keep the better remaining option: $L(i,j)=\max (\underset{\begin{array}{c}\text{drop }{x}_i,\\ \text{look up}\end{array}}{\underbrace{L(i-1,j)}},\underset{\begin{array}{c}\text{drop }{y}_j,\\ \text{look left}\end{array}}{\underbrace{L(i,j-1)}}).$

WHY no $+1$? No new shared character was found, so nothing is earned. We merely inherit the best answer already computed for a slightly smaller problem.

WHY max of up and left (never diagonal)? "Drop $x_i$" means shorten $X$'s prefix — that's the up neighbour $L(i-1,j)$. "Drop $y_j$" means shorten $Y$'s prefix — the left neighbour $L(i,j-1)$. We don't know in advance which discard is smarter, so we try both and keep the larger. The diagonal is forbidden here: dropping both letters could throw away a match hiding on one side.

PICTURE. Final letters T vs C disagree. Two arrows — one from up, one from left — feed the current cell; the fatter arrow (the larger value) wins.

Step 6 — The floor: empty prefixes give zero

WHAT. The recurrence keeps shrinking prefixes. It must stop somewhere. When either prefix is empty ($i=0$ or $j=0$) there is nothing to share: $L(0,j)=0,L(i,0)=0.$

WHY this base case? An empty string has no characters, so it shares nothing with anybody — a length-0 LCS. These zeros form the top row and left column and seed every later cell. Without them the recursion would fall off the edge of the grid.

PICTURE. The grid with its entire top row and left column pre-filled with 0s (the burnt-orange border). Every other cell will be computed from this border.

Step 7 — Fill the whole grid for AGCAT vs GAC

WHAT. Sweep row by row, left to right. Each cell picks its door (Step 4 or Step 5) and reads its already-finished neighbours.

WHY row-by-row order? Each cell needs its up, left, and diagonal neighbours — all of which lie above or to the left. So if we fill top-to-bottom, left-to-right, every neighbour is guaranteed ready before we need it.

PICTURE. The completed $6\times 4$ table. Diagonal (match) steps are drawn in teal, max (mismatch) inheritances in plum. Follow a few cells and check them against the rules.

Step 8 — Traceback: recovering the actual string

WHAT. The corner gives the length. To get the letters, walk backwards from the corner following the arrow that built each cell.

WHY does walking backward work? Each cell remembers how it was made. A diagonal (+1) cell means "this shared letter is in the LCS — record it, then step diagonally." A max cell means "no letter here — step toward whichever neighbour I copied." Reverse the construction and the letters fall out (in reverse, so read them backward at the end).

PICTURE. A path from bottom-right to top-left. Teal diagonal steps mark the letters we collect (C, then G); plum straight steps collect nothing. Reading the collected letters top-down spells GC.

The one-picture summary

WHAT. One diagram compresses the whole page: two letters enter a decision, and the answer flows in from one of three neighbours.

Related build-outs

• Dynamic Programming — the reuse-of-subproblems idea powering Step 2.
• Edit Distance — same grid, but mismatches cost a replace instead of a max.
• Longest Common Substring — swap Step 5 for "reset to 0", read the max over all cells.
• Longest Increasing Subsequence — reduces to LCS of an array with its sorted-unique copy.
• Diff Algorithm — the traceback of Step 8 is exactly a git diff.
• Sequence Alignment — the biology-flavoured Needleman–Wunsch version of this grid.

Active recall