メモ化再帰

下記のQiita記事を参考に、メモ化再帰を利用してフィボナッチ数列の項を求めるコードをPythonで書きました。

qiita.com

n = int(input())

fibdp = [0 for _ in range(n+1)]
def getFib(n):
        if n == 0: return 0
        if n == 1: return 1
        if (fibdp[n] is not 0): return fibdp[n]
        fibdp[n] = getFib(n-1) + getFib(n-2)
        return fibdp[n]

print(getFib(n))

chokudaiさんの下記スライドが元ネタだそうです。

www.slideshare.net

通常のDFSで発生する重複した計算(下図でいうとf(2))を省略するために、計算結果をメモしておく手法。

f:id:tx_driver:20181230092039p:plain