動的計画法（Dynamic Programming）入門
フィボナッチ第5項を求める際の関数の呼び出され方
上の図を見てもらうとわかりますが、fib(5)の計算をする際に、fib(3)の計算を2回行っています。つまり、同じ計算を余分に 1 回行うことになります。
動的計画法を使う場合（メモ化再帰）
このような再帰関数によるトップダウン型の動的計画法の実装方法を、メモ化再帰などと言うことがあります。
動的計画法を使う場合（漸化式）
dp[ i ] := フィボナッチの第 i 項
となるよう、以下のように i が0からn-2の時まで更新してやります。
dp[ i+2 ] = dp[ i+1 ] + dp[ i ]
このような、漸化式を利用したボトムアップ型の動的計画法の実装方法もあります。
ナップサック問題
価値が \(フィボナッチ数列の計算量について v_i\) 、重さが \(w_i\) で表される荷物が N 個ある。重さ B を超えないようにナップサックに入れる時、選んだ荷物の価値の合計は最大でどれだけか？
ここでは、AtCoder Beginner Contest 032 D – ナップサック問題 のデータセット 2 フィボナッチ数列の計算量について に対応する部分点を得る解答を考えることとします。（つまり、N≦200 かつ全ての i(1≦i≦N) について 1≦wi≦1000 を満たす）
動的計画法を使わない場合
荷物の選び方は、それぞれの荷物に対して「入れる or 入れない」の2通りがあるので、全体で\(2^N\)通りあります。
これは再帰関数を用いて計算することができます。 i 番目の荷物を選択するかしないかで分岐させてください。
これも、部分問題が構造的に現れています。knapsack(i,b) の計算をする上で、knapsack(i + 1, b – w[i]) や knapsack(i + 1, b) といった部分問題を解く必要があります。
動的計画法を使う場合（メモ化再帰）
動的計画法を使う場合（漸化式）
dp[ i ][ b ] := 残りの重さ(容量)が b 以上となる i 番目までの荷物の選び方で、最大となる価値の総和
仮に最適な選び方をしたとして、dp[ i+1 ][ b ] の値を考えてみましょう。
i 番目の荷物を使う時は dp[ i ][ b + w[ i ]]+v[ i ] が価値の総和の最大となり、使わない時は dp[ i ][ b ] となるはずです。
（残りの重さを考えていることに注意してください。i 番目の荷物を使う時は、残りが b+W[ i ] フィボナッチ数列の計算量について からW[ i ] だけ減って b になればよいはずです。）
dp[ i+1 ][ b ] = max(dp[ i ][ b + w[ フィボナッチ数列の計算量について i ]]+v[ i ], dp[ i ][ b ])
求める答えは、 dp[N][0] になります。
dp[ i ][ b ] := i 番目までの荷物について、今までに入れた重さの総和が b 以下となるもので、価値の総和の最大値
フィボナッチ数列と成長の仕組みについて
たった n=5 の場合でもかなり大変なことになっています。しかし、これくらいなら、最近のCPU演算能力による力技で何とかなるのです。では、これが n=40, n=50くらいになってくるとどうでしょう。さすがに厳しくなってきます。関数の呼び出しには実際の計算と関係のないオーバーヘッドがかかります。計算量より関数呼び出しにCPU処理時間が使われていて、その結果、答えを出すのにものすごく時間が必要になってしまうのです。
「関数呼び出し」を減らそう
先程のコードでは、関数呼び出しがボトルネックになっていましたので、アルゴリズムを少し改良してみます。
改良したコードでは、一度計算した結果を data[] という配列に格納しています。こうすることで、fib2()そのものは一度しか呼び出されません。
JavaScriptに限らず、配列参照は関数呼び出しに比べてコストがかからない処理なので、高速に実行されるというわけです。
これでも良いのですが、もっといい方法はないのでしょうか？
n番目のフィボナッチ数を求める公式がある
なぜ、整数しかとるはずのないフィボナッチ数にルートが出てくるのかは、数学の奥深いところですが(※この数は「黄金比」に関係があります）、「一般式があるのだから、公式にしたがって関数をつくればいいのでは？」と思いますよね。
プログラム言語の限界
困難な問題でも、答えがあるということがわかれば対処策も必ず出てくる
あなたは、ここにアクセスしてFibonacci(103)フィボナッチ数列の計算量について と入力するだけで必要なフィボナッチ数の答えを得ることができます。答えを得るだけなら、アルゴリズムのボトルネックをリファクタリングしたり、ゼロからコードを書く必要はまったくないのです。
成長と進化の流れの行き着く先
今回は数学の話でしたが、何かの問題を解決しようとするとき、1)自力でシンプルに解く、2)自力でシンプルな解法を改良する、3)もっとうまくやる人に依頼する、4)専門の道具を使う、という価値変化の流れがあります。人がやっていることはいずれ道具に必ず置き換わりますので、フィボナッチ数列同様、私たちも少しずつ「成長」していきたいものですね。
コメント