Micro-Drill #129 — Edit distance recurrence

Recursion & DP Target: 10s

Edit distance uses three operations: insert, delete, replace. Each maps to a DP neighbor.

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], dp[i][j-1], dp[i-1][j-1])

Type it from memory. Go.