Dynamic Programmingについて
動的計画法(DP, Dynamic Programming)について
最近やたらと動的計画法という単語を聞くので、基本をまとめておく。
動的計画法とは？
動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP）は、計算機科学の分野において、アルゴリズムの分類の1つである。対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。
引用:Wikipedia
え？それって分割統治法じゃない？
同じものなのかな？
分割統治法と動的計画法の違いについて
アルゴリズムを設計する際には、まず全体をいくつかの小問題に分解して、その一つ一つを解いていくことにより全体の解を得る方法があります。このような手法を、分割統治法(divid and rule)と言います。
この方法は、ある程度複雑な問題を解く際には妥当な方法であるような感じがします。しかし、現実問題として、この方法には大きな欠点があります。なぜなら、実際に運用してみると、同じ問題を何回も解かなくてはならないようなケースに遭遇するからです。
そこで、「実際に必要とされるかどうかはわからないが、必要になりそうな小問題をあらかじめ解いておいて保存しておき、必要なときに取り出して使う、というアプローチも存在します。これが動的計画法(dynamic programming)の考え方です。
引用:
納得。したつもり。
また分からなくなるかもだけどそのときはまた調べよう。
