The DP recurrence is: dp[i][j] = 0 if i=0, j=0 dp[i][0] = i, dp[0][j] = j (base cases) For each cell (i,j): — if s[i] == t[j]: dp[i][j] = dp[i-1][j-1] (match) — else: min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+1) (delete, insert, replace)
dp[i][j] = 0
i=0, j=0
dp[i][0] = i
dp[0][j] = j
(i,j)
s[i] == t[j]
dp[i][j] = dp[i-1][j-1]
min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+1)