Мемоизацuя - это метод, при котором сохраняются результаты выполненных вычислений, так что, когда они снова понадобятся, их можно найти, вместо того чтобы вычислять во второй (или миллионный) раз.
```
from typing import Dict
memo: Dict[int, int] = {0: 0, 1: 1} # базовые случаи
def fib3(n: int) -> int:
if n not in memo:
memo[n] = fib3(n - 1) + fib3(n - 2) # мемоизация
return memo[n]
```
Вызов fib3(20) даст только 39 вызовов fibЗ(), а не 21 891, как в случае без момоизации. Словарь memo изначально заполняется базовыми вариантами 0 и 1, избавляя fibЗ() от излишней сложности, связанной со вторым оператором if.
### Автоматическая мемоизация
В Python есть встроенный декоратор для автоматической мемоизации любой функции. Каждый раз, когда fib4() выполняется для нового аргумента, декоратор выполняет кэширование возвращаемого значения. При последующих вызовах fib4() для того же аргумента сохраненное значение извлекается из кэша и возвращается
```
from functools import lru_cache
@lru_cache(maxsize=None)
def fib4(n: int) -> int:
if n < 2: # базовый случай
return n
return fib4(n - 2) + fib4(n - 1) # рекурсивный случай
```