定義

編集距離（Edit Distance）は、一つの文字列を別の文字列に変換するために必要な最小操作回数です。挿入(Insert)、削除(Delete)、置換(Replace)の3つの操作を使用できます。レーベンシュタイン距離とも呼ばれます。

主な特性

• ✓文字一致時: dp[i][j] = dp[i-1][j-1] (コスト0)
• ✓文字不一致時: dp[i][j] = 1 + min(削除, 挿入, 置換)
• ✓初期化: dp[0][j] = j (挿入回数), dp[i][0] = i (削除回数)
• ✓逆追跡で実際の操作順序を復元可能

時間計算量