動的計画法

動的計画法（DP）は、最適部分構造をもち同じ部分問題が重複して現れる問題について、部分問題の解を一度だけ計算・保存し、それらを組み合わせて全体解を得る設計手法です。

■ 試験で押さえるポイント

• 状態を『それまでの判断に必要な情報』として定義し、遷移式、初期値、計算順序、最終状態を決めます。状態が不足すると正解を表せず、多過ぎると計算量が増えます。

• トップダウンのメモ化は再帰で必要状態だけを保存し、ボトムアップの表計算は依存順に全状態を埋めます。どちらも重複計算を避けます。

• 計算量は$\text{状態数}\times\text{各状態の遷移数}$で評価します。直前の行だけ参照する場合などは、表全体を保持せず空間を圧縮できます。

• 局所的に最善を選ぶ貪欲法とは異なり、DPは複数候補の部分最適値を保持します。ナップサック、編集距離、最短経路、系列比較などに使います。

■ 選択肢での判断ポイント

重複部分問題、最適部分構造、状態・遷移、メモ化／表計算が手掛かりです。再帰を使うだけではDPではありません。

例: 容量5で品物(重さ2,価値3)、(3,4)、(4,5)を各一度選ぶ0-1ナップサックでは、重さ2と3を選ぶ価値7が最大です。