概要
概要
1 文字の挿入、削除、置換で文字列を変換する最小コストを求めます。表の各マスで 3 通りを比較します。
動的計画法・再帰 / Edit Distance（編集距離）
1 文字の挿入、削除、置換で文字列を変換する最小コストを求めます。表の各マスで 3 通りを比較します。
目次
このページでわかること
概要
1 文字の挿入、削除、置換で文字列を変換する最小コストを求めます。表の各マスで 3 通りを比較します。
考え方
dp[i][j] = min(delete, insert, replace)要点
O(nm)
O(nm)
insert/delete/replace
文字列類似度
補足
各接頭辞同士の最小変換回数を積み上げます。
3 方向を比較する点が大きな違いです。
上・左・左上の意味を言語化すると迷いません。
動きで確認
ここでは「状態が何か」を見ながら、上で読んだ内容を動きと結びつけます。
次に見る
比較すると違いがわかりやすいページを先に置いています。