Числа Фибоначчи строятся по простому правилу: каждое новое число равно сумме двух предыдущих. Дано число n. Верни n-е число Фибоначчи, где fib(0) = 0, fib(1) = 1, а дальше работает формула fib(n) = fib(n-1) + fib(n-2). Постарайся не пересчитывать одни и те же значения много раз.

def fib(n: int) -> int: