Пример 1. Последовательность Фибоначчи

Ты уже встречался с числами Фибоначчи:

1, 1, 2, 3, 5, 8, 13, ...

Каждое число равно сумме двух предыдущих.

Можно решать задачу рекурсивно, но это долго. Гораздо быстрее воспользоваться динамикой — просто запоминать уже найденные значения.

Вот динамическое решение на Python:

def fibonacci(n):
    # создаём список для хранения значений
    fibo = [0] * (n + 1)
    fibo[0] = 0
    fibo[1] = 1

    # идём от 2 до n и считаем по формуле
    for i in range(2, n + 1):
        fibo[i] = fibo[i - 1] + fibo[i - 2]

    return fibo[n]

# Проверим
print(fibonacci(10))  # 👉 55

Сложность алгоритма: O(n) — линейная. Это гораздо быстрее, чем пересчитывать всё заново!