「動的計画法」の版間の差分

}

}

例えば、このプログラムを使ってフィボナッチ数列の第5項を求める場合を考えてみる。このプログラムは再帰的に呼び出されるので、その様子を以下に示す。

fib(5)

return memo[n];

}

 

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

return memo[n];

}

 

近年は色々な[[プログラミング言語]]が[[メモ化]]を言語レベルでサポートしている。その機能を利用した場合、より簡単に書ける場合がある。例えば [[Groovy]] の場合、@Memoized を付けることでメモ化するが、下記のように、定義を直接実装したプログラムに @Memoized を付けると動的計画法になる。

}

}

 

== 関連項目 ==