動的計画法

動的計画法(Dynamic Programming)とは

• 動的計画法は、対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法です。

• 細かくアルゴリズムが定義されているわけではなく、下記2条件を満たすアルゴリズムの総称である。

1. 帰納的な関係の利用： より小さな問題例の解や計算結果を帰納的な関係を利用してより大きな問題例を解くのに使用する。
2. 計算結果の記録： 小さな問題例、計算結果から記録し、同じ計算を何度も行うことを避ける。帰納的な関係での参照を効率よく行うために、計算結果は整数、文字やその組みなどを見出しにして管理される。

Wikipediaより

考え方

1. いくつかの小さな問題の解が、大きな問題の解になるように再帰を設定する。
2. 小さば問題を一度解決し、解をテーブルに記録する。
3. そのテーブルから最初の問題の解を取り出す。

※ 問題を独立した部分問題に分割し、それらを再帰的に解く分割統治法とは異なる。

使用例

フィボナッチ数列の再帰呼び出し

𝐹(𝑛) = 𝐹(𝑛−1) + 𝐹(𝑛−2)
n = 0 のとき 𝐹(0) = 0
n = 1 のとき 𝐹(1) = 1

n番目のフィボナッチ数を再帰的に（トップダウンで）計算する

                  𝐹(𝑛)

    𝐹(𝑛 − 1)      +      𝐹(𝑛 − 2)

𝐹(𝑛−2) + 𝐹(𝑛−3)       𝐹(𝑛−3) + 𝐹(𝑛−4)
                . . .

連鎖行列積問題

連続した行列の積を計算するとき、計算回数を最小にする積の順序を求める
https://qiita.com/mk668a/items/bc5cc36f472487eaf0d8

その他

• 二項係数の計算
• 最長共通部分列問題
• 推移閉包のためのワーシャルのアルゴリズム
• 最短経路に対するフロイド法
• 最適二分探索木の構築
• 離散最適化問題のいくつかの例：
  • 巡回セールスマン問題
  • ナップザック問題