Что такое динамическое программирование на примере Фибоначчи

Что такое динамическое программирование? Классическая задача — числа Фибоначчи

Динамическое программирование — подход, при котором задачу разбивают на повторяющиеся подзадачи и сохраняют их решения, чтобы не вычислять одно и то же несколько раз. На числах Фибоначчи это позволяет улучшить наивную рекурсию с O(2ⁿ) до O(n).

Подробный ответ

Что такое динамическое программирование

Dynamic programming, или DP, применяют, когда задача состоит из перекрывающихся подзадач, а решение большой задачи можно построить из решений меньших. Главное отличие от обычной рекурсии — уже вычисленные результаты сохраняются и переиспользуются.

Наивная рекурсия Фибоначчи

def fibonacci(n: int) -> int:
    if n <= 1:
        return n

    return fibonacci(n - 1) + fibonacci(n - 2)

Такое решение многократно вычисляет одни и те же значения. Например, fibonacci(3) будет вычисляться в разных ветках рекурсии несколько раз. Временная сложность наивного варианта — примерно O(2ⁿ).

Memoization — top-down подход

Memoization сохраняет результаты рекурсивных вызовов в кэше.

from functools import lru_cache


@lru_cache
def fibonacci(n: int) -> int:
    if n <= 1:
        return n

    return fibonacci(n - 1) + fibonacci(n - 2)

Каждое значение от 0 до n вычисляется только один раз, поэтому временная сложность становится O(n).

Tabulation — bottom-up подход

Bottom-up подход начинает с базовых значений и последовательно строит решение до нужного результата.

def fibonacci(n: int) -> int:
    if n <= 1:
        return n

    previous = 0
    current = 1

    for _ in range(2, n + 1):
        previous, current = current, previous + current

    return current

Сложность

Подход	Время	Память
Наивная рекурсия	`O(2ⁿ)`	`O(n)`
Memoization	`O(n)`	`O(n)`
Bottom-up с двумя переменными	`O(n)`	`O(1)`

Как ответить на собеседовании

Динамическое программирование использует сохранение решений перекрывающихся подзадач. В задаче Фибоначчи наивная рекурсия повторно считает одинаковые значения и работает экспоненциально, а memoization или bottom-up табуляция дают O(n). Для одного значения Фибоначчи оптимально использовать итеративный вариант с двумя переменными и памятью O(1).