Модуль: 11.1a Динамическое программирование. Часть 1_ДП и рекурсия


Задача

2/11

Числа Фибоначчи: Мемоизация рекурсии (Python)

Теория Нажмите, чтобы прочитать/скрыть

Основная теория описана в задаче Числа Фибоначчи: Мемоизация рекурсии (C++)

Задача

Числа Фибоначчи, обозначаемые обычно F(n) образуют последовательность, называемую последовательностью Фибоначчи, такую, что каждое число является суммой двух предыдущих, начиная с 0 и 1. То есть,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), для n > 1.

По заданному n, вычислите F(n) (0 <= n <= 80).

(в коде программы длина одного отступа равна 4 пробелам!)

Примеры
Входные данные Выходные данные
1 2 1
2 3 2
3 4 3