72. Edit Distance

Work over prefixes: dp[i][j] is the minimum edits to turn the first i characters of word1 into the first j of word2. If the current characters match, you pay nothing and inherit the diagonal…