動的計画法とは？
動的計画法とは、大きな問題を部分問題に分解し、一度計算した部分問題の結果を記録（メモ化）しておくことで、同じ計算の重複を避けながら効率的に解く手法。単純な再帰では指数的な計算量になる問題を、多項式時間に抑えられることがある。
どうてきけいかくほう
動的計画法の意味
大きな問題を部分問題に分解し、一度計算した部分問題の結果を記録（メモ化）しておくことで、同じ計算の重複を避けながら効率的に解く手法。単純な再帰では指数的な計算量になる問題を、多項式時間に抑えられることがある。
動的計画法の具体例
フィボナッチ数列を単純な再帰だけで計算すると同じ値を何度も計算し直してしまうが、一度計算した値を配列に記録して再利用することで、計算量を大幅に削減できる。
動的計画法は試験でどう引っ掛けられる？
分割統治との違いは部分問題が重複し、記録した結果を再利用する点。貪欲法と違いその場の最善ではなく組合せを網羅的かつ効率的に調べるので最適解が保証される。ナップサック問題や最短経路問題が典型例として問われる。
動的計画法と関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。