DP配列でフィボナッチ

前回、答えを書き留めることで計算回数は n に比例するところまで落ちました。それでも再帰のままだと、もう 1 つ別の限界にぶつかります。

n を 3000 にすると、今度は落ちる

import sys
print(sys.getrecursionlimit())   # 1000

fib(3000) を再帰で求めると、fib(3000) が fib(2999) を呼び、それが fib(2998) を呼び、と 3000 段ぶんの呼び出しが積み上がってから、ようやく一番下の答えが決まります。積める段数には上限があり、Python なら既定で 1000 段です。超えると RecursionError で止まります。書き留める場所を用意しても、この段数は減りません。

問題は、大きいほうから聞きに行っていることです。答えが決まる順番は、どうせ小さいほうからです。それなら最初から小さいほうで作ればよく、聞きに行く必要そのものが無くなります。

下から順に、置いていく

必要な数だけ箱を先に用意し、添字の小さいほうから 1 つずつ埋めます。途中までの売上合計を並べた配列なら、こう作れます。

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] はもう埋まっています。ボトムアップの気持ち良さはここにあります。参照する先が必ず「すでに終わった場所」になるよう順番を決めれば、再帰は一切要りません。関数呼び出しが消えるぶん、同じ回数でも実測は速くなります。

埋める前に読んでしまう

xs = [10, 20, 30]
print(xs[-1])    # 30 が返る。エラーにはならない

Python の負の添字は、末尾から数えた要素を返します。ループの開始位置を間違えて、まだ置いていない出発点より手前を読んでしまっても、止まらずに末尾の値が混ざります。JavaScript なら undefined との足し算で NaN になります。どちらも、出発点を先に手で置き、ループはその次から回す、で防げます。

もう 1 つ多いのが箱の数え違いです。n 番目の答えが欲しいなら、0 番から数えて n + 1 個の箱が要ります。

やってみよう

ひな形の TODO を完成させてください。初期状態と、小さい順に表を埋める更新を自分で書きます。入力を受け取る枠と説明つきの準備部分はそのまま使えます。

演習で使う書き方

本文の累積売上は一つ前の箱と今日の売上から次の箱を埋めます。演習では直前の二つの箱から決めます。[0] * (n + 1) は表の確保です。0 番と小さい入力の処理は用意し、もう一つの初期状態と更新する for を自分で書きます。

1. 初期状態と、小さい順に表を埋める更新を自分で実装する
2. 関数名と引数、入力と戻り値の形を保つ。説明つきの準備部分を使い、TODO の仮の処理を置き換える