DPL_1 E Edit Distance (Levenshtein Distance)

dp[i][j] = (s1のi文字目まででs2のj文字目までを作る最小コスト) としてDPします。
各文字列に対する操作についてDPの遷移を考えると

• 挿入 dp[i][j] = dp[i][j-1] + 1
• 削除 dp[i][j] = dp[i-1][j] + 1
• 置換 dp[i][j] = dp[i-1][j-1] + 1

となります。さらにs1[i]とs2[j]が等しいときは置換を行う必要がありません。そのため、置換の代わりに

dp[i][j] = dp[i-1][j-1]

と遷移できます。