フィボナッチ数列で動的計画法に入門する

無数にある同様の記事の二番煎じになってしまうが、自分でまとめたいのでご容赦を。Pythonでフィボナッチ数列を実装することで、動的計画法に入門することが目的。

フィボナッチ数列とは

フィボナッチ数列とは、前の2つの数の和が次の数字となる数列のことである。

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... といった具合に無限に続く。

再帰的に実装

再帰的に書くと以下の通りだ。

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

nが1になるまでfib(n-1) + fib(n-2)の両項で再帰を繰り返すので、同じ処理が2回発生する。これは計算量がO(2^n)となり、nの大きさに応じで計算量が指数関数的に増大する。nが小さい場合は計算可能だが、nが大きくなると計算できなくなってしまう。

最近atcoderにpythonで参加しているが、tle（制限時間超過）になってしまうことがしばしばあるので、計算量を意識してプログラミングしたいと思っている。一度計算した値をメモリに保存しておくことで、再度同じ処理が呼ばれた際に計算しなくていいメモ化という方法がある。これは参照透過性、すなわち引数に対して返り値が一意に定まる関数（単射）のことである。

from functools import lru_cache

@lru_cache(max_size=None)
def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)