Memorize Recursive
code: python
from typing import Dict
# O(n), O(n)
def f(n: int, memo: Dictint, int = {}) -> int: if n in memo:
if n == 0:
return 0
if n == 1:
return 1
memon = f(n-1, memo) + f(n-2, memo) # f(0) -> 0
# f(1) -> 1
# f(2) -> f(1) + f(0) -> 1
# f(3) -> f(2) + f(1) -> 2
# f(4) -> f(3) + f(2) -> 3
# f(5) -> f(4) + f(3) -> 5
def test_f():
assert f(0) == 0
assert f(1) == 1
assert f(2) == 1
assert f(3) == 2
assert f(4) == 3
assert f(5) == 5
assert f(10) == 55