動的計画法とは？
動的計画法とは、大きな問題を小さな部分問題に分け、その答えを表に記録して再利用することで、同じ計算の繰り返しを避ける手法。部分問題が重複して現れる問題に効き、素朴な再帰では指数時間になる処理を多項式時間に落とせる。
どうてきけいかくほう
動的計画法の意味
大きな問題を小さな部分問題に分け、その答えを表に記録して再利用することで、同じ計算の繰り返しを避ける手法。部分問題が重複して現れる問題に効き、素朴な再帰では指数時間になる処理を多項式時間に落とせる。
動的計画法の具体例
ナップサック問題、編集距離（レーベンシュタイン距離）、フィボナッチ数の計算が典型。フィボナッチを単純な再帰で書くと呼び出し回数が指数的に増えるが、算出済みの値を配列に残せば線形時間で済む。
動的計画法は試験でどう引っ掛けられる？
分割統治法との違いを問われる。分割統治は部分問題が互いに独立で重複しないのに対し、動的計画法は重複するからこそ記録が効く。表のぶんメモリ使用量は増える。
動的計画法と関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。