動的計画法とは？
動的計画法とは、大きな問題を複数の部分問題に分解して解く点は分割統治法と似ているが、同じ部分問題が何度も繰り返し現れる場合に、一度計算した結果を記憶（メモ化）しておき、再利用することで無駄な計算を省き効率化を図るアルゴリズムの設計手法。単純な再帰処理では同じ計算を何度も繰り返してしまい非効率になることがあるが、動的計画法を用いることで計算量を大幅に削減できる場合が多い。
どうてきけいかくほう
動的計画法の意味
大きな問題を複数の部分問題に分解して解く点は分割統治法と似ているが、同じ部分問題が何度も繰り返し現れる場合に、一度計算した結果を記憶（メモ化）しておき、再利用することで無駄な計算を省き効率化を図るアルゴリズムの設計手法。単純な再帰処理では同じ計算を何度も繰り返してしまい非効率になることがあるが、動的計画法を用いることで計算量を大幅に削減できる場合が多い。
動的計画法の具体例
フィボナッチ数列を単純な再帰だけで計算すると同じ値の計算を何度も繰り返してしまうが、一度計算した値を表に記録しておき再利用することで、効率よく計算できるようになる。
動的計画法は試験でどう引っ掛けられる？
動的計画法は「部分問題に分ける」点で分割統治法と似ているが、計算結果を記憶して再利用する点が本質的な違いであり、両者を混同しないよう注意する。
動的計画法と関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。