Here is the implementation for Edit Distance (CSES 1639):
function editDistance(A, B)
n := length of A
m := length of B
dp := 2D array of size (n + 1) × (m + 1)
// Base cases
for i from 0 to n
dp[i][0] := i
for j from 0 to m
dp[0][j] := j
// Fill table
for i from 1 to n
for j from 1 to m
if A[i] = B[j] then
dp[i][j] := dp[i - 1][j - 1]
else
replace := dp[i - 1][j - 1] + 1
delete := dp[i - 1][j] + 1
insert := dp[i][j - 1] + 1
dp[i][j] := min(replace, delete, insert)
return dp[n][m]
The three operations map directly to three neighbors in the table. Replace looks diagonally, delete looks up, insert looks left. When characters match, you take the diagonal value for free. Trace editDistance("CAT", "CUT"): the table fills to dp[3][3] = 1 (replace A with U).
Time complexity: .
Space complexity: , reducible to by keeping only two rows.