動的計画法を利用したプログラム

ウィキペディア小見出し辞書

動的計画法を利用したプログラム（ボトムアップ方式）

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/10/02 16:40 UTC 版)

「動的計画法」の記事における「動的計画法を利用したプログラム（ボトムアップ方式）」の解説

int fib(unsigned int n) { int memo[1000] = {0, 1}, i; for (i = 2; i <= n; i++) { memo[i] = memo[i - 1] + memo[i - 2]; } return memo[n];} fib(n - 1) と fib(n - 2) を先に計算しておいた上で、fib(n) を計算している。この場合は先ほどの実装と異なり、ループ部分の計算量は O(n) の多項式時間である。このように指数関数時間で行われる処理を、計算済みの結果を記録することにより多項式時間で処理できるように改良でき、計算時間を圧倒的に減らせる。

動的計画法を利用したプログラム（トップダウン方式）

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/10/02 16:40 UTC 版)

「動的計画法」の記事における「動的計画法を利用したプログラム（トップダウン方式）」の解説

トップダウンで、メモ化を併用したやり方。fib(n) を計算するのに、fib(n - 1) と fib(n - 2) が必要だが、計算結果を配列 memo に保存して再利用している。 #include int memo[1000] = {0, 1};bool in_memo[1000] = {true, true};int fib(unsigned int n) { if (!in_memo[n]) { memo[n] = fib(n - 1) + fib(n - 2); in_memo[n] = true; } return memo[n];} 近年は色々なプログラミング言語がメモ化を言語レベルでサポートしている。その機能を利用した場合、より簡単に書ける場合がある。例えば Groovy の場合、@Memoized を付けることでメモ化するが、下記のように、定義を直接実装したプログラムに @Memoized を付けると動的計画法になる。 import groovy.transform.Memoized@Memoizedint fib(int n) { switch (n) { case 0: return 0 case 1: return 1 default: return fib(n - 1) + fib(n - 2) }}