Page 35Dynamic Programming

35 — Edit Distance

Insert/delete/replace DP grid with backtracked operations.

Edit Distance DP

Source Target

if A[i-1] == B[j-1]: dp[i][j] = dp[i-1][j-1] else: dp[i][j] = 1 + min( dp[i-1][j], // delete dp[i][j-1], // insert dp[i-1][j-1]) // replace