Visual walkthrough — DP problems — edit distance (Levenshtein)

Everything here is a slow-motion replay of Dynamic Programming applied to strings.

---

Step 1 — What is a "string" and what is an "edit"?

WHAT. A string is just a row of letters written left to right, like beads on a wire: A = h o r s e. We number the beads starting at position 0, so A[0]='h', A[1]='o', and so on. The number of beads is the length, written $m$.

WHY. Before we can count "edits" we must agree on what one edit is. There are exactly three moves, and each costs 1 coin:

• insert — stick a new letter onto the wire.
• delete — pull one letter off the wire.
• substitute — swap one letter for a different one.

PICTURE. Each of the three moves shown on the same little word, with the coin cost printed underneath. This is the entire "vocabulary" of the problem — nothing else is allowed.

---

Step 2 — Why we cut the problem into prefixes

WHAT. A prefix is "the first few letters of a word". A[0..i) means "the first $i$ letters of $A$" — the little half-open bracket [0..i) reads from position 0 up to but not including position $i$. So A[0..0) is the empty word (zero letters), and A[0..5) is all of horse.

WHY. Solving horse → ros all at once is scary. But solving h → r (one letter each) is tiny. The whole trick of Dynamic Programming is: solve every small prefix pair first, write the answer down, and reuse it. This reuse-of-smaller-answers is exactly Optimal Substructure and Overlapping Subproblems.

PICTURE. Two words with a "cut line" sliding along each, showing prefixes of growing length. Each cut on $A$ is an index $i$; each cut on $B$ is an index $j$.

---

Step 3 — The base row and base column (the free walls)

WHAT. Two special situations where the answer needs no thinking:

• One word is empty. Turning the empty word "" into B[0..j) — what does that cost? You have nothing and need $j$ letters, so you insert $j$ times: $dp[0][j]=j$.
• The other word is empty. Turning A[0..i) into "" means deleting every one of its $i$ letters: $dp[i][0]=i$.

WHY. Every recurrence eventually shrinks its inputs; something must stop the shrinking. These two "walls" are that floor. Without them the grid has no starting numbers to build on (see the parent's "forgetting the base row/column" mistake).

PICTURE. The empty grid with the top row filled 0 1 2 3... (all inserts) and the left column filled 0 1 2 3... (all deletes). The corner $dp[0][0]=0$ (empty → empty, zero coins).

---

Step 4 — The one question every cell asks: "what about the last letters?"

WHAT. Pick any inner cell $dp[i][j]$. Look at the current letters — because we count from the first $i$, the last letter of that prefix sits at index $i-1$. So the two letters in play are A[i-1] and B[j-1] (this off-by-one is the parent's #1 mistake — the cell counts letters, so the newest letter is at index minus one).

WHY. Any full sequence of edits has to finish by dealing with the last letter of each prefix. There are only a handful of possible "last moves", and — crucially — once we decide the last move, everything before it is a smaller cell we already filled. That is why one question is enough.

PICTURE. The two prefix strips with their final letters highlighted, and a thought-bubble listing the only possible last moves.

---

Step 5 — Case A: the last letters MATCH (the free diagonal)

WHAT. If A[i-1] == B[j-1], the final letters already agree. We spend zero coins here and just inherit the cost of aligning the two smaller prefixes (drop the last letter from each):

$dp[i][j]=dp[i-1][j-1]\text{(no }+1\text{)}$

WHY. Why the diagonal $dp[i-1][j-1]$ and not up or left? Because dropping one letter from both words takes us diagonally up-and-left in the grid. Why no $+1$? Because matching letters need no edit — adding a coin here would over-count (parent's "min over the wrong neighbours" mistake).

PICTURE. A grid arrow pointing from the up-left neighbour into the current green cell, with o == o labelled and a "0 coins" tag.

---

Step 6 — Case B: the last letters DIFFER (three rescue routes)

WHAT. If A[i-1] != B[j-1], we must spend one coin, but we have three ways to spend it. Each route pays $1$ and then leans on an already-solved neighbour:

$dp[i][j]=1+\min (\underset{\text{substitute}}{\underbrace{dp[i-1][j-1]}},\underset{\text{delete from }A}{\underbrace{dp[i-1][j]}},\underset{\text{insert into }A}{\underbrace{dp[i][j-1]}})$

• ↖ Substitute — swap A[i-1] for B[j-1]; both prefixes shrink by one → diagonal neighbour, $+1$.
• ↑ Delete — throw away the extra letter A[i-1]; only $A$ shrinks → the cell above, $+1$.
• ← Insert — add the needed letter B[j-1]; only $B$ shrinks → the cell to the left, $+1$.

WHY. We take the minimum because we want the cheapest fix, and these three are the only possible last moves — so we can never miss the best one.

PICTURE. The current red cell with three incoming arrows (↖ substitute, ↑ delete, ← insert), each labelled with its neighbour and its +1, and the min picking the smallest.

---

Step 7 — Watch a real cell fill: dp[5][3] for horse → ros

WHAT. We fill the full grid, then zoom in on the bottom-right cell. Here A[4]='e', B[2]='s', and 'e' ≠ 's', so we use the differ rule:

$dp[5][3]=1+\min (\underset{3}{\underbrace{dp[4][2]}},\underset{2}{\underbrace{dp[4][3]}},\underset{4}{\underbrace{dp[5][2]}})=1+2=3$

WHY. The three candidates are $3,2,4$; the smallest is $2$ (the cell above, meaning "delete e"). Add the one coin and we land on 3 — the final answer $d(\text{horse},\text{ros})=3$.

PICTURE. The completed $6\times 4$ grid, the diagonal match cells shaded, and a coloured back-trace path showing delete h, delete r, substitute e→s.

---

Step 8 — Degenerate cases (never hit an unshown scenario)

WHAT. The corners of the problem:

• Both empty: $d(\text{""},\text{""})=dp[0][0]=0$.
• One empty: $d(\text{""},\text{"abc"})=3$ (pure base row) and $d(\text{"abc"},\text{""})=3$ (pure base column).
• Identical words: every letter matches, the whole path is the free diagonal → $d(A,A)=0$.
• Same length, all different: e.g. abc → xyz — no matches, three substitutions → distance $3$. This shows length difference ($0$ here) is only a lower bound, never the answer (parent's last mistake).

WHY. These are the boundaries where the recurrence "bottoms out". If any of them were wrong, every cell built on top would be wrong too.

PICTURE. Four mini-grids side by side, one per degenerate case, each with its answer circled.

---

The one-picture summary

WHAT. One figure holding the entire derivation: the base walls (Step 3), the match diagonal (Step 5), the three-arrow choice (Step 6), and the answer in the corner (Step 7).

Recall Feynman retelling of the whole walkthrough

Lay both words on a wire. Draw a grid: rows count how many letters of the first word you're looking at, columns count how many of the second. The top row and left column are free warm-ups — turning nothing into a word is just inserting each letter, and shrinking a word to nothing is just deleting each letter, so you fill them 0 1 2 3.... Now every other box asks one tiny question: do the two newest letters match? If yes, copy the box diagonally up-left — matching is free. If no, you must spend one coin, and you get to pick the cheapest of three neighbours: up-left (swap a letter), straight up (delete a letter from the first word), or straight left (add a letter). Fill boxes left-to-right, top-to-bottom, and the moment you fill the very last box in the bottom-right corner, the fewest-coins answer is written right there.

---

Connections

• Parent: Edit Distance — this page is its visual derivation.
• Dynamic Programming · Optimal Substructure · Overlapping Subproblems — why the grid works.
• Recursion and Memoization — the same recurrence, top-down.
• Longest Common Subsequence · Sequence Alignment — the match-diagonal is shared with these.
• Space Optimization in DP — keep only one row of the grid.