Foundations — DP problems — edit distance (Levenshtein)

This page assumes nothing. Before you can read the parent note Edit Distance, you must own every symbol it throws at you. We build each one — meaning, then picture, then why the topic needs it — in an order where each rests on the last.

0. What is a "string"?

Picture the beads:

Why the topic needs this: edit distance is a question about two strings — how many single-bead changes turn one row of beads into another. Everything downstream is about comparing two of these wires.

1. Indexing — pointing at one bead

Why the topic needs this: the topic constantly compares "the current last character of A" against "the current last character of B". We need a precise way to point at those characters. That pointer is an index.

2. Prefix — a beginning slice of the string

Examples for A = "horse":

Why the topic needs this: edit distance between two prefixes is a genuinely smaller instance of the same question. That "same question, smaller size" property is what lets recursion and Dynamic Programming work at all — see Optimal Substructure.

3. The empty string ""

Why the topic needs this: it is the smallest possible starting point. To turn an empty wire into "ros" you can only add beads, so the cost is obvious (3 inserts). Those obvious cases are the base cases the whole grid is anchored to. Without the empty string, there's no floor to build up from.

4. The three edit operations

Why the topic needs this: "edit distance" is the count of these coins. Defining the moves and their price (all 1) is the rulebook of the game. If substitution cost 2 instead of 1, the whole table would change — so the cost model must be stated before anything else.

5. The subscript pair $(i,j)$ and the table dp[i][j]

Why the "+1"? Because $i=0$ and $j=0$ mean empty prefixes, and those are the base cases from step 3. We need a row and column to hold them.

Why the topic needs this: the entire method is "fill every box, then read the bottom-right box dp[m][n]." The table is the answer store. The pair $(i,j)$ is the address of each answer.

6. Base cases — the boxes you fill before any rule

The grid can't fill itself out of nowhere: the very first box, and the whole top row and left column, must be written by hand first. These starting values are called the base cases.

Why the topic needs this: every other box will be computed from boxes above and to the left of it. If the top row and left column aren't filled in first, those look-ups read empty boxes and the whole grid collapses. The base cases are the floor everything stands on.

7. min — picking the cheapest

Why this tool and not another? At each box there are several ways to have arrived (delete, insert, substitute). Each way has a coin cost. We want the fewest coins, so we compare the options and keep the smallest — that is exactly what \min does. We never use \max here because more coins is worse, not better.

8. "Recurrence" — the word for a rule that leans on smaller answers

Why the topic needs this word: the parent note calls the main formula "the recurrence" / "the transition." Now you know that just means "the rule that fills one box from smaller boxes." Nothing scary.

9. Putting the notation together

Now every symbol in the parent's rule is earned. Notice there are two cases — a match (freebie) and a mismatch (pay a coin) — so the rule is written piecewise with the big curly brace:

Everything the parent note does is now readable, because you can decode A[i-1], A[0..i), dp[i][j], base cases, \min, and "recurrence" one symbol at a time.

The prerequisite map

Each foundation flows upward into the recurrence, which flows into the full topic. The related vault ideas — Recursion and Memoization, Overlapping Subproblems, Optimal Substructure, Longest Common Subsequence, and Sequence Alignment — all reuse this same "table of prefix answers" machinery, and Space Optimization in DP shrinks the table once you understand it.

Equipment checklist

Test yourself — reveal only after you've answered aloud.