14.7 まとめ¶
1. 要点の振り返り¶
- 動的計画法は問題を分解し、部分問題の解を保存して重複計算を避け、計算効率を高めます。
- 時間を度外視すれば、動的計画法の問題はすべてバックトラッキング（全探索）で解けます。ただし、再帰木に大量の重複した部分問題が含まれ、非常に非効率です。記録用リストを導入して計算済みの解を保存すれば、重複する部分問題を 1 回だけ計算できます。
- メモ化探索は上から下への再帰的な解法です。対応する動的計画法は下から上へ漸化式を適用する解法で、「表を埋める」ように進めます。現在の状態が一部の近隣の状態だけに依存するため、\(dp\) テーブルの次元を一つ減らして空間計算量を下げられます。
- 部分問題への分解は汎用的なアルゴリズムの考え方ですが、分割統治、動的計画法、バックトラッキングでは性質が異なります。
- 動的計画法の問題には、部分問題の重複、最適部分構造、後続の判断が過去の経路に依存しない性質という 3 大特徴があります。
- 元の問題の最適解を部分問題の最適解から組み立てられるなら、最適部分構造があります。
- 後続の判断が過去の経路に依存しない性質とは、その後の展開が現在の状態だけで決まり、過去に通ったすべての状態には依存しないことです。多くの組合せ最適化問題はこの性質を持たず、動的計画法で高速に解くことはできません。
ナップサック問題
- ナップサック問題は動的計画法の最も典型的な問題の一つで、0-1、個数制限なし、個数制限付きなどの変種があります。
- 0-1 ナップサック問題では、最初の \(i\) 個の品物から選んで容量 \(c\) のナップサックに入れたときの最大価値を状態に対応させます。「入れない」「入れる」の二つの選択から最適部分構造と状態遷移式が得られます。各状態は真上と左上の状態に依存するため、空間最適化では逆順に走査し、左上の状態が上書きされるのを防ぎます。
- 個数制限なしナップサック問題では各品物を選ぶ個数に制限がないため、入れる場合の状態遷移が 0-1 の場合と異なります。状態が真上と真左に依存するので、空間最適化では順方向に走査します。
- 硬貨の両替問題は、個数制限なしナップサック問題の変種です。価値の「最大化」が硬貨の枚数の「最小化」に変わるため、状態遷移式の \(\max()\) を \(\min()\) に変えます。また、容量を「超えない」条件が目標金額に「ちょうど一致する」条件に変わるため、\(amt + 1\) で「目標金額を作れない」という無効な解を表します。
- 硬貨の両替問題 II では、「硬貨の最小枚数」の代わりに「硬貨の組み合わせの数」を求めるため、状態遷移式も \(\min()\) から和に変わります。
編集距離問題
- 編集距離（Levenshtein 距離）は二つの文字列の類似度を測るもので、一方をもう一方に変換するための最小編集回数と定義されます。編集操作には、挿入、削除、置換があります。
- 編集距離問題では、\(s\) の先頭 \(i\) 文字を \(t\) の先頭 \(j\) 文字に変換する最小編集回数を状態に対応させます。\(s[i-1] \ne t[j-1]\) なら挿入・削除・置換の 3 通りの選択があり、それぞれに残る部分問題があります。そこから最適部分構造と状態遷移式を導けます。\(s[i-1] = t[j-1]\) なら、その文字は編集不要です。
- 編集距離では状態が真上、真左、左上に依存するため、空間最適化後は順方向でも逆方向でも、そのままでは正しく遷移できません。左上の状態を変数に一時保存すれば、個数制限なしナップサック問題と同じ状況になり、空間最適化後も順方向に走査できます。