Динамическое программирование для начинающих: Python с примерами кода

Динамическое программирование — это эффективный метод решения задач, который часто применяется в разработке и на технических собеседованиях. Подход предлагает оптимальное решение для сложных проблем и позволяет существенно сократить время выполнения программы по сравнению с наивным перебором. В этой статье разберём, что такое динамическое программирование, как оно устроено и как реализовать его на Python — с рабочим кодом, а не только описанием.

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

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

Динамическое программирование (ДП) — способ решения задачи через разбиение на более простые подзадачи, при котором результат каждой подзадачи вычисляется один раз и переиспользуется, а не пересчитывается заново. В основе метода — два признака, по которым можно понять, что задача решается динамикой.

• Перекрывающиеся подзадачи (overlapping subproblems). Одна и та же меньшая задача встречается многократно при решении большой — например, fib(3) вызывается несколько раз при наивном вычислении fib(6).
• Оптимальная подструктура (optimal substructure). Оптимальное решение всей задачи можно построить из оптимальных решений её подзадач — локально верный выбор ведёт к глобально верному результату.

Если оба признака выполняются, есть смысл применить один из двух подходов: мемоизацию (сохранение результатов «по требованию», сверху вниз) или табуляцию (последовательное заполнение таблицы результатов, снизу вверх). Дальше разберём оба подхода на одном и том же примере — числах Фибоначчи, — а затем применим табуляцию к более практичной задаче о рюкзаке.

Наивная рекурсия: с чего всё начинается

Прежде чем оптимизировать, стоит увидеть, что именно мы оптимизируем. Наивная рекурсивная реализация чисел Фибоначчи выглядит естественно, но на практике работает медленно:

def fib_recursive(n):
    if n <= 1:
        return n
    return fib_recursive(n - 1) + fib_recursive(n - 2)

print(fib_recursive(10))  # 55

Проблема в том, что функция пересчитывает одни и те же значения множество раз: fib_recursive(5) внутри себя вызывает fib_recursive(3) несколько раз, хотя результат у него всегда один и тот же. Из-за этого сложность по времени растёт экспоненциально — O(2ⁿ), и уже при n≈35 такой код заметно подвисает.

Мемоизация: динамическое программирование сверху вниз

Мемоизация сохраняет результат каждой подзадачи при первом вычислении и переиспользует его при повторных вызовах — структура рекурсии остаётся той же, но повторной работы больше нет. В Python для этого не обязательно писать свой кеш вручную — есть готовый декоратор lru_cache из модуля functools:

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

print(fib_memo(50))  # 12586269025

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

Табуляция: динамическое программирование снизу вверх

Табуляция решает ту же задачу без рекурсии: таблица результатов строится последовательно, от простых базовых случаев к искомому значению.

def fib_tabulation(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

print(fib_tabulation(50))  # 12586269025

Здесь уже нет рекурсии и риска переполнить стек вызовов на больших n. Сложность по времени — O(n), по памяти тоже O(n) для массива dp, но её легко сократить до O(1): для чисел Фибоначчи достаточно хранить только два последних значения, а не всю таблицу.

Классический пример: задача о рюкзаке

Числа Фибоначчи хорошо показывают механику метода, но на собеседованиях и в реальных задачах — логистике, распределении бюджета, упаковке контейнеров — чаще встречается более практичный пример: задача о рюкзаке (0/1 knapsack). Есть рюкзак ограниченной вместимости и набор предметов с весом и ценностью — нужно набрать предметы так, чтобы суммарная ценность была максимальной, а суммарный вес не превышал вместимость.

Вместимость рюкзака — 5 кг. Решение табуляцией строит таблицу «первые i предметов × вместимость w» и на каждом шаге выбирает, брать текущий предмет или нет:

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(
                    dp[i - 1][w],
                    values[i - 1] + dp[i - 1][w - weights[i - 1]],
                )
            else:
                dp[i][w] = dp[i - 1][w]

    return dp[n][capacity]

weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5
print(knapsack(weights, values, capacity))  # 7

Ответ — 7: выгоднее взять предметы 1 и 2 (вес 2+3=5 кг, ценность 3+4=7), чем один тяжёлый предмет 4 (вес 5 кг, ценность 6). Без табуляции для полного перебора пришлось бы проверить 2⁴=16 комбинаций — при росте числа предметов перебор быстро становится неподъёмным, а динамическое программирование решает задачу за n×capacity шагов.

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

Помимо учебных примеров, динамическое программирование регулярно используется в реальных системах.

• Поиск кратчайшего пути и маршрутизация. Алгоритмы вроде Беллмана — Форда для логистики и навигации опираются на ту же идею переиспользования уже посчитанных путей.
• Редакционное расстояние (edit distance). Проверка орфографии, сравнение версий файлов и биоинформатика используют ДП для подсчёта минимального числа правок между двумя строками.
• Компиляторы и парсеры. Синтаксический разбор выражений и генерация кода нередко опираются на табуляцию промежуточных результатов разбора.
• Финансовое моделирование. Расчёт оптимального портфеля или расписания платежей — тоже задача с перекрывающимися подзадачами.

Метод применим не только к текстовым задачам на Python. Например, метод простых итераций C++ может быть ускорен с помощью динамики за счёт сохранения промежуточных итогов и их повторного использования — это уменьшает число избыточных вычислений и ускоряет сходимость алгоритма. Проверка на простое число C++ тоже поддаётся оптимизации: один из распространённых приёмов здесь — «решето Эратосфена», которое заранее табулирует все простые числа до заданной границы вместо проверки каждого числа по отдельности.

Типичные ошибки при изучении динамического программирования

• Сразу писать табуляцию, минуя наивное решение. Без понятной рекурсивной версии сложно увидеть, какие именно подзадачи повторяются и что нужно сохранять в таблице.
• Забыть про базовые случаи. Ошибка в условии остановки рекурсии (как if n <= 1 в примере с Фибоначчи) либо даёт неверный ответ, либо уходит в бесконечную рекурсию.
• Путать перекрывающиеся подзадачи с независимыми. Если подзадачи не повторяются, обычная рекурсия или жадный алгоритм могут быть быстрее и проще, чем динамическое программирование.
• Не считать память. Табуляция часто съедает O(n²) памяти на двумерную таблицу там, где на самом деле достаточно хранить одну-две предыдущие строки.
• Останавливаться на мемоизации, не пробуя табуляцию. Рекурсия с кешем проще для чтения, но на больших входных данных может упереться в лимит глубины рекурсии Python — у табуляции такого ограничения нет.

Практические задачи для тренировки

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

• Числа Фибоначчи — разобранный выше базовый пример на мемоизацию и табуляцию.
• Задача о рюкзаке (0/1 knapsack) — максимизация ценности при ограничении по весу, разобрана выше.
• Наименьшее количество монет (coin change) — минимальное число монет заданных номиналов для размена суммы.
• Наибольшая возрастающая подпоследовательность (LIS) — поиск самой длинной подпоследовательности чисел, идущей по возрастанию.
• Редакционное расстояние (edit distance) — минимальное число вставок, удалений и замен для превращения одной строки в другую.
• Подъём по лестнице (climbing stairs) — сколько есть способов подняться на n-ю ступеньку, если за шаг можно пройти 1 или 2 ступени.

Веб-услуги и разработка в YuSMP Group — рабочая альтернатива, если нужно не просто разобраться в алгоритме, а оптимизировать реальный медленный участок продакшен-кода. Проекты, которые мы создали, показывают, как такие оптимизации отражаются на реальных продуктах. Свяжитесь с нами любым удобным способом, чтобы получить бесплатную консультацию от ведущих экспертов компании.

Больше статей ищите в блоге студии веб-разработки YuSMP Group.

Частые вопросы

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

Это способ решать сложную задачу быстрее: она разбивается на одинаковые подзадачи, и результат каждой считается один раз, а не пересчитывается заново при каждом обращении.

Чем мемоизация отличается от табуляции?

Мемоизация — это рекурсия с кешем: результаты подзадач сохраняются «по требованию», сверху вниз. Табуляция строит таблицу результатов заранее, последовательно снизу вверх, без рекурсии и риска переполнить стек вызовов.

В чём разница между наивной рекурсией и динамическим программированием?

Наивная рекурсия пересчитывает одни и те же подзадачи заново при каждом вызове, из-за чего сложность растёт экспоненциально. Динамическое программирование сохраняет уже посчитанные результаты, снижая сложность до линейной или полиномиальной.

Какие задачи чаще всего решают динамическим программированием?

Классические примеры — числа Фибоначчи, задача о рюкзаке, поиск кратчайшего пути, редакционное расстояние между строками и наибольшая возрастающая подпоследовательность. Метод также применяется в логистике, финансовом моделировании и компиляторах.

Подходит ли Python для динамического программирования или лучше C++?

Для обучения и большинства прикладных задач Python вполне подходит — особенно с декоратором lru_cache для мемоизации. Для задач с жёсткими ограничениями по времени выполнения, например в соревновательном программировании, быстрее будет C++, но сама логика алгоритма одинакова на любом языке.

С чего начать изучение динамического программирования новичку?

Начните с наивного рекурсивного решения простой задачи вроде чисел Фибоначчи, затем добавьте мемоизацию через lru_cache и только потом перепишите решение в табуляцию. Такой порядок помогает увидеть, какую именно повторную работу устраняет метод.

Всегда ли динамическое программирование уменьшает сложность алгоритма?

Нет, оно помогает только тогда, когда у задачи есть перекрывающиеся подзадачи и оптимальная подструктура. Если подзадачи не повторяются, динамическое программирование не даёт выигрыша и только усложняет код по сравнению с обычной рекурсией или жадным алгоритмом.