動的計画法（DP）とナップサック問題の計算
意味・解説
大きな問題を小さな部分問題に分割し、その解をメモ（記録）して再利用することで、計算の重複を避けて最適解を求めるアルゴリズム手法。
ナップサック問題において、容量制限内で価値の合計を最大化する組み合わせを、1つ前の状態（部分問題の最適解）を用いて再帰的に算出する手法。全探索よりも大幅に計算量を削減できる。
くわしく
「過去の成功例をメモして、次の判断に使う」知恵です。
1.仕組み：
重さと価値がバラバラな複数の荷物がある時、容量1kgの時の最高額、2kgの時の最高額…と順番に表を埋めていきます。
2.メリット：
容量10kgの計算をする際、既に計算済みの9kgまでの結果を利用するため、同じ計算を何度も繰り返す必要がありません。ポイントは、配送ルートの最適化や予算配分など、組み合わせが膨大になるビジネス上の「最善の選択」を、現実的な時間で計算できるからです。
例文
限られた予算内で広告効果を最大化するため、動的計画法を用いて最適なメディア・ミックスの計算を行った。
過去問での出題状況
直近29回分の過去問（全2,900問）を解析した結果、2回登場しています（出題された年度: 2年度）。
出典: 本サイト独自集計（問題文および全選択肢テキストからの用語出現頻度・2026年6月時点）
同義語: メモ化再帰
対義語: 全探索 (総当たり)
分類: アルゴリズム設計技法