動的計画法

動的計画法（DP）は、問題を小さな部分問題に分け、その結果を表に保存して再利用しながら、全体の答えを求める手法です。

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

• 同じ部分問題が何度も現れる問題で、計算の重複を避けられます。

• 再帰で必要な分だけ保存するメモ化と、表を順に埋める方法があります。

• ナップサック問題、最短経路、文字列の比較などに使います。

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

部分問題の重複と結果の再利用が手掛かりです。その場で最善を選ぶ貪欲法とは異なります。