Находим N’е число Фибоначчи тремя способами за приемлемое время: основы динамического программирования

Задача: посчитать N-е число последовательности, в которой каждый элемент равен сумме двух предыдущих. Такая последовательность называется последовательностью Фибоначчи: 1, 1, 2, 3, 5, 8… Очень часто на разнообразных олимпиадах попадаются задачи вроде этой, которые, как думается на первый взгляд, можно решить с помощью простого перебора. Но если мы подсчитаем количество возможных вариантов, то сразу убедимся в неэффективности такого подхода: например, простая рекурсивная функция, приведенная ниже, будет потреблять существенные ресурсы уже на 30-ом числе Фибоначчи, тогда как на олимпиадах время решения часто ограничено 1-5 секундами. Давайте подумаем, почему так происходит. Например, для вычисления fibo(30) мы сначала вычисляем fibo(29) и fibo(28). Но при этом наша программа «забывает», что fibo(28) мы уже вычисляли при поиске fibo(29). Основная ошибка такого подхода «в лоб» в том, что одинаковые значения аргументов функции исчисляются многократно — а ведь это достаточно ресурсоемкие операции.