応用情報技術者 予想問題｜練習問題 第11問

解説

動的計画法（DP）が有効なのは、「最適部分構造（部分問題の最適解を組み合わせると全体の最適解が得られる）」と「部分問題の重複（同じ部分問題が計算中に何度も現れる）」の2条件を満たす場合である。部分問題の解を表に記録（メモ化）して再利用することで同じ計算の繰返しを排除し、素朴な探索では指数時間かかる問題を多項式時間で解けることが多い。貪欲法で最適解を構成できる問題は局所的な判断だけで解けるため、DPの適用条件そのものではない。部分問題が互いに独立で重複しない場合は通常の分割統治法で十分であり、メモ化の利点が生きない。入力が整列済みかどうかも無関係である。ナップサック問題や編集距離、最短経路計算が代表的な適用例として頻出である。