概要
概要
再帰で Fibonacci 数をそのまま求めると、同じ計算を何度も繰り返します。メモ化や DP の必要性を示す代表例です。
動的計画法・再帰 / Fibonacci（フィボナッチ数列）
再帰で Fibonacci 数をそのまま求めると、同じ計算を何度も繰り返します。メモ化や DP の必要性を示す代表例です。
目次
このページでわかること
概要
再帰で Fibonacci 数をそのまま求めると、同じ計算を何度も繰り返します。メモ化や DP の必要性を示す代表例です。
考え方
fib(n) = fib(n-1) + fib(n-2)
base cases: fib(0), fib(1)要点
O(2^n)
O(n)
重複部分問題
DP
補足
遅さの理由が再帰木ではっきり見えます。
メモ化で一気に変わります。
同じ fib(3) が何回出るかを数えるとよいです。
動きで確認
ここでは「状態が何か」を見ながら、上で読んだ内容を動きと結びつけます。
次に見る
比較すると違いがわかりやすいページを先に置いています。