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