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