DP)は、計算機科学の分野において、アルゴリズムの分類の1つである。対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。細かくアルゴリズムが定義されているわけではなく、下記2条件を満たすアルゴリズムの総称である。帰納的な関係の利用:より小さな問題例の解や計算結果を帰納的な関係を利用してより大きな問題例を解くのに使用する。計算結果の記録:小さな問題例、計算結果から記録し、同じ計算を何度も行うことを避ける。programming)」という言葉は1940年代にリチャード・E・ベルマンが最初に使いはじめ、1953年に現在の定義となった[1]。効率のよいアルゴリズムの設計技法として知られる代表的な構造の一つである。対象となる問題を帰納的に解く場合にくり返し出現する小さな問題例について、解を表に記録し表を埋めていく形で計算をすすめ、冗長な計算をはぶくアルゴリズムのことをいう。特定のアルゴリズムを指すのではなく、上記のような手法を使うアルゴリズムの総称である。一般的に、帰納的な定義にしたがって再帰法でアルゴリズムを作ると計算結果の再利用は行わないが、入力が単純な構造で解が等しくなることの確認が容易であるとき、同じ入力について計算済であることの確認、結果の再利用をメモリ領域を消費して行い、計算を高速化する。初歩的な説明で使われるフィボナッチ数の計算、ハノイの塔の必要移動回数の計算などでは、一次元の表(列)によって指数オーダーの計算時間を入力の数の大きさに対して線形時間に落とすことができる。個用意してループすればことたりる。)効果が顕著なのが組合せ問題で、文字列の近似照合(編集距離の計算)、ナップサック問題の解法などが、二次元の表により指数時間の手続きが多項式時間に効率化される有名な例である。マルチプルアラインメントのように表が三次元以上必要になると、時間に対するトレードオフとなるメモリ領域量が大きくなりすぎるため、規模の大きな入力には実用的でなくなる。2種類の実現方法がある。分割統治法において、計算結果を記録(メモ化)して再利用する方法。recursion)とも呼ばれる。適用する場合、一般的に、以下の2つが適用する問題に成立していないといけない。subproblems)部分構造最適性とは、以下の2条件が成立していることをさす。部分問題も同じ最適化問題が成立している部分問題間が独立している部分問題を解き、それを利用して、全体の最適化問題を解く戦略のため、部分構造最適性が動的計画法には必要である。最短経路でないといけない(このことは背理法により証明可能)。部分問題間が独立であるためには、部分問題で資源の共有があってはならない。同じ辺が出現しないため(同じく背理法により証明可能)、資源の共有が発生していない。貪欲法においても厳密解を求めるのなら部分構造最適性は必要である。部分問題重複性とは、同一の部分問題が繰り返し出現することである。動的計画法では重複する部分問題の計算結果を記録し再利用する事により計算量を削減する。厳密なことを書くと、全体問題と部分問題は完全に同一である必要性はなく、また、部分問題間が独立でなくても、それらが何らかの計算式により依存関係を解決し結合させる方法があれば、部分構造最適性が成立しなくても動的計画法の定義を満たすアルゴリズムは作れる。項の和となる数列のことである。この問題は最適化問題ではない。定義に基づいてプログラムを作成すると、次のようになる。}}例えば、このプログラムを使ってフィボナッチ数列の第5項を求める場合を考えてみる。このプログラムは再帰的に呼び出されるので、その様子を以下に示す。呼び出し回数の和が結果の値となる。O(2^{n})}の指数関数時間となる。