動的計画法
最適化問題に適用する場合、一般的に、以下の2つが適用する問題に成立していないといけない。(厳密には成立しなくても動的計画法の定義は満たせる)
部分構造最適性(英: optimal substructure)や最適性原理(英: principle of optimality)
部分問題重複性(英: overlapping subproblems)
部分構造最適性とは、以下の2条件が成立していることをさす。
部分問題も同じ最適化問題が成立している
部分問題間が独立している
部分問題を解き、それを利用して、全体の最適化問題を解く戦略のため、部分構造最適性が動的計画法には必要である。部分構造最適性の例として、最短経路問題では、A → B → C という最短経路において、A → B や B → C も最短経路でないといけない(このことは背理法により証明可能)。また、部分問題間が独立であるためには、部分問題で資源の共有があってはならない。最短経路問題では A → B と B → C で同じ辺が出現しないため(同じく背理法により証明可能)、資源の共有が発生していない。貪欲法においても厳密解を求めるのなら部分構造最適性は必要である。
部分問題重複性とは、同一の部分問題が繰り返し出現することである。動的計画法では重複する部分問題の計算結果を記録し再利用する事により計算量を削減する。
厳密なことを書くと、全体問題と部分問題は完全に同一である必要性はなく、また、部分問題間が独立でなくても、それらが何らかの計算式により依存関係を解決し結合させる方法があれば、部分構造最適性が成立しなくても動的計画法の定義を満たすアルゴリズムは作れる。しかし、そのような実用例は少ない。
「動的計画法(dynamic programming)」という言葉は1940年代にリチャード・E・ベルマンが最初に使いはじめ、1953年に現在の定義となった。
効率のよいアルゴリズムの設計技法として知られる代表的な構造の一つである。対象となる問題を帰納的に解く場合にくり返し出現する小さな問題例について、解を表に記録し表を埋めていく形で計算をすすめ、冗長な計算をはぶくアルゴリズムのことをいう。特定のアルゴリズムを指すのではなく、上記のような手法を使うアルゴリズムの総称である。一般的に、帰納的な定義にしたがって再帰法でアルゴリズムを作ると計算結果の再利用は行わないが、入力が単純な構造で解が等しくなることの確認が容易であるとき、同じ入力について計算済であることの確認、結果の再利用をメモリ領域を消費して行い、計算を高速化する。