DP配列でフィボナッチ
前回、答えを書き留めることで計算回数は n に比例するところまで落ちました。それでも再帰のままだと、もう 1 つ別の限界にぶつかります。
n を 3000 にすると、今度は落ちる
Python
import sys
print(sys.getrecursionlimit()) # 1000fib(3000) を再帰で求めると、fib(3000) が fib(2999) を呼び、それが fib(2998) を呼び、と 3000 段ぶんの呼び出しが積み上がってから、ようやく一番下の答えが決まります。積める段数には上限があり、Python なら既定で 1000 段です。超えると RecursionError で止まります。書き留める場所を用意しても、この段数は減りません。
問題は、大きいほうから聞きに行っていることです。答えが決まる順番は、どうせ小さいほうからです。それなら最初から小さいほうで作ればよく、聞きに行く必要そのものが無くなります。
下から順に、置いていく
必要な数だけ箱を先に用意し、添字の小さいほうから 1 つずつ埋めます。途中までの売上合計を並べた配列なら、こう作れます。
Python
sales = [120, 80, 200, 60]
total = [0] * len(sales)
total[0] = sales[0]
for i in range(1, len(sales)):
total[i] = total[i - 1] + sales[i]
# total は [120, 200, 400, 460]向きが変わっただけで、計算している中身は前回とまったく同じです。前回は大きいほうから呼びに行って、帰りがけに答えを書き留めました。今回は小さいほうから書き留めていき、呼びに行く工程そのものを消します。
total[i] を埋める時点で、total[i - 1] はもう埋まっています。ボトムアップの気持ち良さはここにあります。参照する先が必ず「すでに終わった場所」になるよう順番を決めれば、再帰は一切要りません。関数呼び出しが消えるぶん、同じ回数でも実測は速くなります。
埋める前に読んでしまう
Python
xs = [10, 20, 30]
print(xs[-1]) # 30 が返る。エラーにはならないPython の負の添字は、末尾から数えた要素を返します。ループの開始位置を間違えて、まだ置いていない出発点より手前を読んでしまっても、止まらずに末尾の値が混ざります。JavaScript なら undefined との足し算で NaN になります。どちらも、出発点を先に手で置き、ループはその次から回す、で防げます。
もう 1 つ多いのが箱の数え違いです。n 番目の答えが欲しいなら、0 番から数えて n + 1 個の箱が要ります。
やってみよう
fibDp(n) を書いてください。再帰は使わず、配列とループだけで組み立てます。n が 0 と 1 のときは、配列を作る前に返してしまうほうが安全です。それ以外は箱を用意し、出発点の 2 つを先に置き、残りを添字の小さいほうから埋めていきます。最後に n 番目の箱を返します。n が 40 でも一瞬で返れば成功です。
要件
- 再帰呼び出しを使わず、ループで実装すること
- fib(0) = 0、fib(1) = 1 から始め、fib(k) = fib(k-1) + fib(k-2) で配列を埋めること
- n = 40 でも一瞬で結果が返ること (O(n) 時間)
入出力例
fibDp(0) → 0
fibDp(1) → 1
fibDp(2) → 1
fibDp(7) → 13
fibDp(15) → 610
fibDp(25) → 75025
fibDp(40) → 102334155ヒント
