メモ化再帰
下記のQiita記事を参考に、メモ化再帰を利用してフィボナッチ数列の項を求めるコードをPythonで書きました。
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))を省略するために、計算結果をメモしておく手法。