動的計画法とは？どうてきけいかくほう
動的計画法とは、大きな問題を重複する小さな部分問題に分解し、一度計算した部分問題の結果を記録（メモ化）しておいて再利用することで、無駄な再計算を省いて効率よく解く手法。
最終更新：2026-10-06
応用情報を最短で暗記・合格する →具体例
フィボナッチ数列を単純な再帰で計算すると同じ値を何度も計算し直して非効率だが、一度計算した値を配列に記録しておき次回は参照するだけにすれば、計算量を大幅に削減できる。ナップサック問題や最短経路問題にも応用される。
試験での引っ掛け
分割統治法との違いは部分問題が重複するか。マージソートのように部分問題が重ならないものは分割統治、同じ計算が何度も現れるものが動的計画法の対象。また貪欲法と違い、動的計画法は部分問題を網羅するため最適解が保証される。
関連用語
出典・参考
公式シラバスの1 基礎理論 ＞ 2. 応用数学 ＞ (7) 最適化問題に掲載されている用語です。
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。