動的計画法 わかりやすく

同じものをまた解く

再帰は大きな問題を小さな問題に分けて解きます。フィボナッチはまさにその例です。
fib(5)はfib(4)とfib(3)を、fib(4)はさらにfib(3)とfib(2)を呼びます。よく見ると、fib(2)があちこちの枝で何度も出てきます。
下の木でノードを一つ押して確かめてみましょう。

同じ小さな問題が木のあちこちにまた出てきます。（ノードを押す → 同じ値がすべて強調される）

同じfib(2)を、一度ではなく何度も解いています。fib(3)も同じです。
nが大きくなると、この重複は恐ろしいほどふくらみます。
もう解いた答えを何度も解き直すのは、どう見てももったいないことです。

答えを書いておく

解決策は意外に単純です。一度解いた答えをメモに書いておくのです。
次に同じものが必要になったら、計算し直さずにメモから取り出して使います。初めてのものだけ計算し、見たことのあるものは取り出して使えばよいのです。
ボタンを押して、呼び出しを一つずつ処理してみましょう。

初めてのものは計算して書きとめ、見たことのあるものはメモから取り出して使います。これがメモ化です。

計算するのは最初の一回だけです。残りはすべてメモから取り出すので、同じものを二度解くことがすっかりなくなります。
このように解いた答えを書いておいて使い回す方法を、メモ化と呼びます。
名前はおおげさでも、中身は「書いておくこと」です。

下から表を埋める

同じ考えを逆向きにすることもできます。上から割って下りる代わりに、いちばん下の小さな値から表を埋めて上がっていくのです。
fib(0)とfib(1)は最初からわかっています。その二つを足してfib(2)、fib(1)とfib(2)を足してfib(3)。
下のマスがもう書いてあるので、上のマスは足すだけで済みます。

0,1から一マスずつ上へ埋めます。（次のマス = すぐ下の二マスの和 · ボトムアップ）

このやり方では、メモさえ要りません。表そのものがメモだからです。
下から上へ順番に一度なぞるだけで、解き直すことはまったくありません。
メモ化が「必要なときに書いておく」なら、これは「先に全部書いておく」です。考え方の芯は同じです。

ぐっと速くなる

では、どれくらい速くなるのでしょうか。書いておくだけで、違いは途方もなく大きくなります。
素朴な再帰は重複まで全部解くので、nが大きくなるほど仕事量が爆発するように増えます。メモ化は各マスをちょうど一回ずつ、nに比例する分だけ解きます。
nを大きくしながら二つを比べると、差がはっきり見えてきます。

同じnで解く回数。（素朴な再帰 = 指数的に爆発 · メモ = nに比例する線形）

nが少し大きくなるだけで、素朴な再帰の棒は画面を突き抜けそうなほど伸びます。メモの棒はほとんど動きません。
同じ答えを解き直さない、このひとつが遅さと速さを分けるのです。

まとめ

動的計画法は難しそうな名前ですが、中身は三つの歩みです。
同じものをまた解いていると気づき、一度解いた答えを書いておき、使い回すので、ぐっと速くなる。
下のカードを一つずつ押して、三つの歩みをまとめましょう。

同じものをまた解く → 書いておく → ぐっと速くなる。かけらが重ならない分割統治では書いておく必要がなかったことも、ここで振り返ります。

前に見た分割統治では、割ったかけらが互いに重ならないので、書いておくものがありませんでした。
そこがまさに分かれ道です。かけらが重なるとき、つまり同じ小さな問題が何度も出てくるとき、はじめて書いておくという一手がすべてを変えるのです。