Type the edit-distance recurrence core (the else branch)

Answer

cost = 0 if s[i-1] == t[j-1] else 1 dp[i][j] = min( dp[i-1][j] + 1, # delete s[i] dp[i][j-1] + 1, # insert t[j] dp[i-1][j-1] + cost, # match / substitute )

Three predecessors feed each cell: up (delete), left (insert), diagonal (match if equal, else substitute at cost 1). That is the entire algorithm; the base row/column encode turning a prefix into the empty string.