メモ化再帰
再帰関数が同じ引数で何度も呼ばれるとき、その戻り値をメモしておいて$ 2回目以降は再帰呼び出しをせずにメモした値を返す。
Pythonではlru_cacheがいい感じにしてくれる。(PyPyでは使えないので注意)
code: a.py
from functools import lru_cache
@lru_cache(maxsize=None)
def rec(N):
if N == 0:
return 0
if N == 1:
return 1
return rec(N-1) + rec(N-2)
N = int(input())
print(rec(N))