Exercises — DP problems — edit distance (Levenshtein)

$dp[0][4]=4$. The row $i=0$ means "string $A$ contributes zero letters" — it is empty. To build the first 4 letters of $B$ out of nothing, the only move that adds letters is insert, and you need exactly 4 of them. No cheaper route exists, so it is a base case, not a computed cell.

The letters match, so $dp[i][j]=dp[i-1][j-1]$: the pure diagonal, with no $+1$. Matching a letter is free — you neither insert, delete, nor substitute at this position.

• $dp[i-1][j]$ → delete a letter from $A$ (we shortened $A$'s prefix by one, kept $B$'s).
• $dp[i][j-1]$ → insert a letter into $A$ (we shortened $B$'s prefix, meaning $A$ needed that extra letter).
• $dp[i-1][j-1]$ (differing letters) → substitute (we shortened both prefixes and paid to swap the letter).

Align right-to-left. 't'='t' → free. 'a' vs 'u' → differ, one substitute (+1). 'c'='c' → free. Total $=\boxed{1}$.

$A=$abc (rows), $B=$yabd (cols).

Bottom-right $dp[3][4]=\boxed{2}$. Path: insert y at the front (+1), then a,b match for free, then substitute c→d (+1). One insert + one substitute = 2.

Every letter is 'a', so no substitutions are ever needed — matches carry the cost straight down the diagonal. The only difference is length: $A$ has two extra 'a's. Delete both → $\boxed{2}$. (This equals the length difference here precisely because no letter ever needs changing.)

The winning neighbour is $dp[4][3]=2$ (the cell directly above). "Above" encodes a delete from $A$: we delete the trailing 'e' of horse. So the last move on the optimal path is delete e, and the remaining cost 2 fixes hors→ros. The other two options (substitute via $dp[4][2]=3$, insert via $dp[5][2]=4$) were strictly more expensive.

Every operation has an exact inverse of equal cost: an insert of a letter into $A$ is undone by a delete of that letter (and vice-versa); a substitute x→y is undone by the substitute y→x. So any editing script that turns $A$ into $B$ in $k$ moves can be reversed move-by-move to turn $B$ into $A$ in the same $k$ moves. Hence any cost achievable one way is achievable the other, and the minimums are equal: $d(A,B)=d(B,A)$.

$d(A,B)\ge |m-n|$. Reason: only insert and delete change a string's length, and each changes it by exactly 1. Substitute leaves length untouched. To go from length $m$ to length $n$ you therefore need at least $|m-n|$ length-changing moves. So the difference in lengths is a floor, never exceeded downward — but it is only a lower bound, because substitutions add cost without changing length. For horse(5)→ros(3): bound is $|5-3|=2$, yet true answer is 3.

Removing substitution deletes the "substitute" candidate from the min. The recurrence becomes:

This is exactly the delete-both-then-reinsert cost, and it is tied to the Longest Common Subsequence: distance $=m+n-2\cdot |\text{LCS}|$. For cat→cut: LCS is ct of length 2, so distance $=3+3-2\cdot 2=\boxed{2}$. (One delete of a, one insert of u — versus a single substitute if it were allowed.)

Replace the substitute term's $+1$ with $+2$:

For the single mismatch a vs u: substitute costs 2, but delete-a + insert-u costs $1+1=2$ as well — a tie at $\boxed{2}$. The general rule: when substitution costs $\ge 2$, delete+insert is always at least as good, so substitution never strictly wins.

$A=$ab (rows), $B=$ba (cols). Row 0 (base) is $[0,1,2]$.

Compute row 1 (A[0]='a'), reading only row 0:

• $dp[1][0]=1$ (base column).
• $j=1$, 'a' vs 'b' differ → $1+\min (\text{diag }0,\text{up }1,\text{left }1)=1$.
• $j=2$, 'a' vs 'a' match → diagonal $=dp[0][1]=1$.

Row 1 $=[1,1,1]$. Discard row 0, keep row 1 as "previous".

Compute row 2 (A[1]='b'), reading only row 1:

• $dp[2][0]=2$ (base column).
• $j=1$, 'b' vs 'b' match → diagonal $=$ prev$[0]=1$.
• $j=2$, 'b' vs 'a' differ → $1+\min (\text{diag prev}[1]=1,\text{up prev}[2]=1,\text{left }dp[2][1]=1)=2$.

Row 2 $=[2,1,2]$. Answer $=dp[2][2]=\boxed{2}$ (swap ab→ba costs two edits: substitute both, or delete+insert). We never needed the full grid — two rows sufficed because the recurrence only ever reads row $i-1$.

True. With no shared letters, no diagonal match is ever free. The cheapest way to reconcile the overlapping positions is to substitute them (cost 1 each) for the first $\min (m,n)$ positions, then insert or delete the remaining $|m-n|$ leftover letters (cost 1 each). Total $=\min (m,n)+|m-n|=\max (m,n)$. No route beats this: you must account for all $\max (m,n)$ positions, and each costs at least 1 since nothing matches. So $d=\boxed{\max (m,n)}$.

Every letter differs (x vs y), lengths are equal, so no length change is needed and each of the $k$ aligned positions needs one substitute. Closed form: $d=k$. Check $k=3$: "xxx"→"yyy" needs 3 substitutions $=\boxed{3}$. This makes a clean regression test because the answer scales exactly linearly with $k$.

Traceback rule: at each cell, look at which neighbour produced it.

• Start $dp[3][4]=2$ (c vs d, differ). It equals $1+dp[2][3]$ via the diagonal → substitute c→d. Move to $dp[2][3]=1$.
• $dp[2][3]=1$ (b vs b, match) → came from diagonal $dp[1][2]=1$, no move. Move to $dp[1][2]$.
• $dp[1][2]=1$ (a vs a, match) → diagonal $dp[0][1]=1$, no move. Move to $dp[0][1]$.
• $dp[0][1]=1$ is on row 0 → we still have a y in $B$ to account for → insert y. Reach $dp[0][0]=0$. Done.

Reading forwards: insert y, keep a, keep b, substitute c→d → exactly 2 edits, matching the table. This traceback is why storing the whole grid (rather than one row) is worth it when you need the script, not just the number.

$d(\text{"cat"},\text{"cut"})$ with all costs 1 ::: 1 $d(\text{"aaaa"},\text{"aa"})$ ::: 2 $d(\text{"abc"},\text{"yabd"})$ ::: 2 Insert-and-delete-only distance of cat,cut ::: 2 (equals $m+n-2\cdot \text{LCS}$) Lower bound on $d$ from lengths ::: $|m-n|$ $d(\text{"xxx"},\text{"yyy"})$ ::: 3 Distance when strings share no letters ::: $\max (m,n)$