フィボナッチ数列を例にして動的計画法を学ぶ
動的計画法とは
下記２条件を満たすアルゴリズム
1. 部分問題を解き、その結果を利用して、全体問題を解く
2. 部分問題の計算結果を再利用する
らしいです。
動的計画法 - Wikipedia
フィボナッチ数列を例にする
フィボナッチ数列が良く動的計画法を説明する時に用いられているので、参考にしてみる。
フィボナッチ数列とは、n番目の値がn-1とn-2番目の値の和となっている数列の事。
番目: 0 1 2 3 4 5 6 7 ...
値: 0 1 1 2 3 5 8 13 ...
動的計画法を使わないパターン
以下のコードは引数に指定したnum番目の値を算出するためのコードである。
この処理の計算量は以下のようになる。
fib(n)の処理に対してfib(n-1)とfib(n-2)の２つの処理を行う。またfib(n-1)の処理はfib(n-2)とfib(n-3)の処理を行う。
このように指数関数的に処理が増えていく。N番目の値を算出する時、計算量はO(2^N)となり、Nが大きいと莫大な値になる。
動的計画法を用いたパターン１(ボトムアップ)
動的計画法を用いる事で計算量をO(N)まで落とす事ができる。
これは、numに辿り就くまでi番目の値を埋めていき、その計算結果を用いて次の番目を計算する方法である。 dpはi番目の値を保存しておくための配列である。
dp[0] = 0;
dp[1] = 1;
の時点で、dpは{0, 1}となっている。
dp[i] = dp[i-1] + dp[i-2]なので
i=2の時は
dp[2] = dp[1] + dp[2]となり、dp[2]には0+1=> 1が代入される。この時点でのdpは{0, 1, 1}となる。
同様にi=3の時は
dp[3] = dp[2] + dp[1]となり、dp[3]には1+1=> 2が代入される。この時点でのdpは{0, 1, 1, 2}となる。
動的計画法を用いたパターン２(トップダウン)
この方法はメモ化再帰とも呼ばれている？？ ソースコードは以下です。
形は動的計画法を使わないパターンに似ていますが、以下のように同じ処理をすることが複数回あるので、その計算結果をメモしておく事で計算量を減らす事ができる。
