DPとは何か フィボナッチで
主に漸化式で与えられる問題を解くのに使われる動的計画法(DP)。
DPとメモ化再帰の定義を、フィボナッチ数列を計算するプログラムを例にして考える。
/* 「フィボナッチ 再帰バージョン」 * フィボナッチ数列を漸化式の通りに実装したもの * この計算ではO(1.618^N)つまり指数オーダーの時間がかかる */ #include <stdio.h> int fib(int n) { if(n==0)return 0; if(n==1)return 1; return fib(n-1)+fib(n-2); } int main(int argc, char **argv) { printf("%d\n", fib(10)); return 0; }
/* 「フィボナッチ メモ化再帰バージョン」 * 計算結果を配列に保存するようにした再帰 * この計算では線形時間でできる */ #include <stdio.h> int fib_memo[10000] = {0}; int fib(int n) { if(n==0)return 0; if(n==1)return 1; if(fib_memo[n] != 0) { return fib_memo[n]; } return fib_memo[n] = fib(n-1)+fib(n-2); } int main(int argc, char **argv) { printf("%d\n", fib(46)); return 0; }
/* 「フィボナッチ 動的計画法バージョン」 * メモ化再帰とは計算の方向が逆(nが増加する方向)になる。 * 再帰が無くなる。 * この計算でも線形時間でできる */ #include <stdio.h> int fib_memo[10000]; int fib(int n) { int i; fib_memo[0] = 0; fib_memo[1] = 1; for(i = 2; i <= n; ++i) { fib_memo[i] = fib_memo[i-1] + fib_memo[i-2]; } return fib_memo[n]; } int main(int argc, char **argv) { printf("%d\n", fib(46)); return 0; }
まとめ