編集距離（レーベンシュタイン距離）
ある単語を別の単語に変えるのに必要な 最小の編集回数を、表を 1 マスずつ埋めて求めます。
2 つの文字列（英字、最大 10 文字）
埋めるステップ
0
計算中
左上（置換 / 一致）
上（削除）
左（挿入）
復元経路
—
編集距離は、1 文字の 挿入・削除・置換を何回すれば文字列 A を B に変えられるかの最小値です
（スペルチェッカ・diff・DNA 比較などに使われます）。
表
・末尾が一致 → 左上をそのまま（操作不要）
・不一致 → 1 +（左上＝置換 / 上＝削除 / 左＝挿入 の最小）
表
dp[i][j] ＝「A の先頭 i 文字を B の先頭 j 文字に変える最小編集回数」。・末尾が一致 → 左上をそのまま（操作不要）
・不一致 → 1 +（左上＝置換 / 上＝削除 / 左＝挿入 の最小）
いま計算しているマス
ここが DP の本質
- 「文字列全体を変える最小回数」を 「先頭 i 文字 を 先頭 j 文字 に変える最小回数」の部分問題に分解。
- 各マスは 近所 3 マス（左上・上・左）だけで決まる ── 全パターンを試さない。
- 0 行目・0 列目は「片方が空文字」＝ そのぶん全部挿入／削除、で初期化する。
- 右下から左上へたどると、実際の編集手順（挿入・削除・置換）が復元できる。