動的計画法（DP）
再帰的な部分問題を一度だけ解いて結果を記憶し、再計算を避ける最適化手法。1950年代のRichard Bellmanによるもので、「動的」という名はRANDの管理職に立派に聞こえるよう付けたものだという。
やり方は二通りある。再帰とメモ化を使うトップダウンと、表を順に埋めていくボトムアップだ。古典的な例は、フィボナッチ数、最長共通部分列、ナップサック問題、編集距離、連鎖行列積などである。
適用できるのは、問題が最適部分構造（大きな解が小さな解から組み立てられる）と重複部分問題（同じ部分問題が何度も現れる）を持つときだ。重複がなければ分割統治法、貪欲法が代替になる。