Динамическое программирование: как распознать и решать задачи

Когда задача — это DP

Динамическое программирование (DP) — это способ решать задачи, разбивая их на подзадачи и сохраняя их ответы. Оно подходит, если выполняются два условия:

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

Признаки в формулировке: «минимальная стоимость», «максимальная сумма», «сколько способов», «можно ли», а также ограничения вида «выбрать элементы так, чтобы…». Если перебор всех вариантов экспоненциален, а подзадач на самом деле немного, это почти наверняка DP.

Метод из трёх шагов

1. Состояние. Что описывает подзадачу? Обычно это один-два индекса: «первые i предметов», «префиксы длины i и j», «вместимость w». Сформулируйте словами: dp[i][w] — лучший результат для первых i предметов при вместимости w.
2. Переход. Как выразить состояние через меньшие? Перечислите выборы на последнем шаге (взять / не взять, совпали символы / нет) и возьмите лучший.
3. Базовый случай. Ответы для самых маленьких состояний: пустой префикс, нулевая вместимость.

После этого определите порядок вычисления (чтобы зависимости были готовы) и где лежит ответ.

Мемоизация и табуляция

Пример на числах Фибоначчи:

from functools import lru_cache

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

def fib_tab(n):
    if n < 2:
        return n
    prev, cur = 0, 1
    for _ in range(n - 1):
        prev, cur = cur, prev + cur
    return cur

Начинать удобно с мемоизации — она прямо следует из рекурсивной формулы. Табуляцию стоит выбрать, когда глубина рекурсии велика или нужна экономия памяти.

Задача о рюкзаке (0/1 knapsack)

Есть предметы с весом и ценностью и рюкзак вместимостью W. Каждый предмет можно взять не более одного раза. Нужно максимизировать ценность.

• Состояние: dp[w] — максимальная ценность при вместимости w с учётом уже рассмотренных предметов.
• Переход: для предмета (вес wt, ценность val) — dp[w] = max(dp[w], dp[w - wt] + val).
• База: dp[w] = 0 для всех w — без предметов ценность ноль.

def knapsack(weights, values, W):
    dp = [0] * (W + 1)
    for wt, val in zip(weights, values):
        for w in range(W, wt - 1, -1):  # идём с конца
            dp[w] = max(dp[w], dp[w - wt] + val)
    return dp[W]

Обход вместимости с конца важен: так каждый предмет используется только один раз. Если идти с начала, получится вариант с неограниченным количеством предметов. Сложность — O(n·W) по времени и O(W) по памяти.

Наибольшая общая подпоследовательность (LCS)

Даны строки A и B. Нужно найти длину самой длинной последовательности символов, которая встречается в обеих в том же порядке (не обязательно подряд).

• Состояние: dp[i][j] — длина LCS для первых i символов A и первых j символов B.
• Переход: если A[i-1] == B[j-1], то dp[i][j] = dp[i-1][j-1] + 1; иначе max(dp[i-1][j], dp[i][j-1]).
• База: dp[0][j] = dp[i][0] = 0.

def lcs(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[n][m]

Сложность — O(n·m). Саму подпоследовательность можно восстановить, пройдя по таблице от dp[n][m] назад. На этой же идее основаны утилиты сравнения файлов (diff) и расстояние редактирования.

Частые ошибки

• Нечёткое состояние. Если не можете описать dp[i] одним предложением, переход будет путаным.
• Неполный переход — забыт один из вариантов выбора.
• Неверный порядок обхода — значение читается до того, как посчитано.
• Сдвиг индексов между строкой и таблицей размера n + 1.
• Жадность вместо DP — локально лучший выбор не всегда даёт глобальный оптимум.