Edit Distance — Filling the Levenshtein DP Matrix and Tracing the Edit Script

dp[i][j] = edit distance between the first i chars of A and the first j chars of B. Watch the matrix fill cell by cell, then trace back the match / insert / delete / substitute operations.

step 0

DP matrix (A down the rows, B across the columns)

A =    B =
Each interior cell takes dp[i-1][j-1] (match/substitute), dp[i-1][j]+1 (delete), or dp[i][j-1]+1 (insert).
diagonal (sub/match) up (delete) left (insert) traceback path

Edit script (traceback)

Press Step to begin. We fill the matrix row by row; each cell reads its three neighbors. After the corner is reached, we trace back to recover the edit operations.
Self-contained visualization. Unit-cost Levenshtein distance (insert / delete / substitute each cost 1; a match is free). The answer is the bottom-right cell dp[n][m]. See junior.md and professional.md for the proof that each cell is the optimal cost of aligning two prefixes.