動的計画法とは？どうてきけいかくほう
動的計画法とは、大きな問題を部分問題に分解し、一度計算した部分問題の結果を記録（メモ化）しておくことで、同じ計算の重複を避けながら効率的に解く手法。単純な再帰（手順の中で自分自身を呼び出すやり方）では、データが増えると処理時間が急激に伸びる（指数的な計算量になる）問題を、もっと緩やかな伸び方（多項式時間）に抑えられることがある。
最終更新：2026-10-09
基本情報を最短で暗記・合格する →具体例
フィボナッチ数列を単純な再帰だけで計算すると同じ値を何度も計算し直してしまうが、一度計算した値を配列に記録して再利用することで、計算量を大幅に削減できる。
試験での引っ掛け
分割統治（問題を小さく分けて解き、結果を組み合わせる方法）との違いは、部分問題が重複し、記録した結果を再利用する点。貪欲法（その場その場で最も得な選択を重ねる方法）と違い、組合せを網羅的かつ効率的に調べるので最適解が保証される。ナップサック問題（容量の決まった袋に、価値の合計が最大になるよう品物を選ぶ問題）や最短経路問題が典型例として問われる。
関連用語
出典・参考
公式シラバスの1 基礎理論 ＞ 2. 応用数学 ＞ (7) 最適化問題に掲載されている用語です。
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。