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

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

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

Эта статья построена как путь: от «почему наивная рекурсия экспоненциальна» до оптимизаций переходов, которые убирают из асимптотики ещё один множитель. Предполагается, что вы знакомы с языком асимптотики и инвариантов из статьи Анализ алгоритмов и с рекурсивным мышлением из Рекурсии и разделяй-и-властвуй.

1. Откуда берётся ДП: перекрывающиеся подзадачи

Разделяй-и-властвуй разбивает задачу на подзадачи, которые не пересекаются: merge sort делит массив на две половины, и левая половина ничего не знает о правой. Каждая подзадача встречается ровно один раз, поэтому суммарная работа описывается рекуррентой Мастер-теоремы.

ДП начинается там, где подзадачи пересекаются. Классический пример — числа Фибоначчи:

def fib_naive(n: int) -> int:
    # Прямая трансляция определения. Корректно и катастрофически медленно.
    if n < 2:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

Дерево вызовов fib_naive(5) содержит fib(3) дважды, fib(2) трижды, fib(1) пять раз. Количество листьев растёт как φⁿ, где φ ≈ 1.618 — золотое сечение. Сложность O(φⁿ): fib_naive(50) считается около минуты, fib_naive(90) — дольше, чем существует Солнечная система. При этом различных подзадач всего n + 1 штука. Мы делаем экспоненциальную работу, чтобы вычислить линейное количество разных значений.

Оранжевым отмечены повторно вычисляемые поддеревья. Вся идея ДП умещается в одну фразу: сделаем так, чтобы каждое такое поддерево считалось один раз.

Два условия применимости

Чтобы задача решалась динамикой, нужны два свойства.

Оптимальная подструктура. Оптимальное решение задачи содержит внутри себя оптимальные решения подзадач. Формально: если кратчайший путь из A в C проходит через B, то его кусок от A до B — кратчайший путь из A в B. Доказывается «вырезанием и вставкой»: если бы существовал более короткий кусок, мы бы подставили его и улучшили целое, что противоречит оптимальности. Это тот же тип рассуждения, что и обменный аргумент из Жадных алгоритмов, только применяется к целому подрешению, а не к одному шагу.

Перекрывающиеся подзадачи. Общее число различных подзадач полиномиально, а рекурсия обращается к ним многократно. Если подзадачи не перекрываются — это разделяй-и-властвуй, и мемоизация только съест память впустую.

Свойство оптимальной подструктуры выполняется не всегда, и это не абстрактная придирка. Классический контрпример: самый длинный простой путь в графе. Если самый длинный простой путь из A в C идёт через B, его начальный кусок вовсе не обязан быть самым длинным простым путём из A в B — потому что «самый длинный» кусок мог бы занять вершины, нужные хвосту. Подзадачи не независимы, и наивная динамика даёт неверный ответ. Именно поэтому задача о длиннейшем пути NP-трудна, а о кратчайшем — решается за полином (см. NP-полнота).

2. Три формы одного и того же алгоритма

2.1. Мемоизация — «сверху вниз»

Минимальное вмешательство в наивный код: заводим кэш и проверяем его перед вычислением.

from functools import lru_cache

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

Время O(n), память O(n) на кэш плюс O(n) на стек рекурсии. Работает, потому что тело функции для каждого n выполняется полностью ровно один раз, а все последующие вызовы попадают в кэш.

Плюсы: код почти дословно повторяет математическое определение, поэтому его легко проверить на корректность; вычисляются только достижимые состояния — если из старта реально достижима лишь малая часть пространства состояний, top-down сэкономит и время, и память. Минусы: накладные расходы на вызовы и хеш-таблицу (в Python это 5–20× против цикла), риск RecursionError на глубине >1000 и невозможность применить свёртку памяти по слоям.

2.2. Табуляция — «снизу вверх»

Разворачиваем рекурсию в цикл, идущий в порядке, где все зависимости уже посчитаны.

def fib_table(n: int) -> int:
    if n < 2:
        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]

Время O(n), память O(n). Нет рекурсии, нет хеширования, данные лежат подряд — кэш процессора счастлив (подробно про это в Практической оптимизации).

2.3. Свёртка памяти

Раз dp[i] смотрит только на два предыдущих элемента, весь массив хранить незачем:

def fib_o1(n: int) -> int:
    prev, cur = 0, 1          # fib(0), fib(1)
    for _ in range(n):
        prev, cur = cur, prev + cur
    return prev

Время O(n), память O(1). Это общий приём: если переход смотрит назад на k слоёв, достаточно хранить k слоёв. Ниже мы применим его к рюкзаку и к расстоянию Левенштейна.

Для Фибоначчи есть и O(log n) через возведение матрицы [[1,1],[1,0]] в степень — но это уже не ДП, а быстрое возведение в степень поверх ассоциативной операции.

Что выбрать

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

3. Дисциплина проектирования: четыре вопроса

Это ядро статьи. Любая задача ДП решается ответом на четыре вопроса в этом порядке.

Формула сложность = (число состояний) × (стоимость одного перехода) — самый полезный инструмент в ДП. Она позволяет оценить решение до написания кода. Видите n ≤ 5000 и придумали состояние из двух индексов с O(1)-переходом? 25 · 10⁶ операций — проходит. Придумали O(n)-переход? 1.25 · 10¹¹ — не проходит, возвращайтесь к пункту 2.

Признак хорошего состояния

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

Типичная ошибка новичка: состояние dp[i] = «лучший ответ для префикса длины i», когда для перехода нужно ещё знать, чем этот префикс закончился. Лечится добавлением измерения: dp[i][j], где j — краткое описание «хвоста» (последний взятый элемент, остаток по модулю, флаг «мы уже использовали право на ошибку»).

4. Семейства задач: карта

Практически всё ДП, которое встретится в работе и на собеседовании, попадает в один из следующих классов. Классифицируйте задачу — и вы почти сразу знаете форму состояния.

5. Рюкзачное ДП: разбор до дна

Рюкзак — самое полезное семейство, потому что оно чаще всего встречается замаскированным: «распределить бюджет по кампаниям», «выбрать набор фич в релиз при лимите на человеко-дни», «набрать заказов в машину при ограничении по объёму».

5.1. Задача 0/1

Дано n предметов с весами w[i] и ценностями v[i], вместимость C. Каждый предмет можно взять не более одного раза. Максимизировать суммарную ценность.

Состояние: dp[i][c] — максимальная ценность, достижимая из первых i предметов при вместимости ровно не более c. Переход: для i-го предмета есть ровно два решения — взять или не взять.

dp[i][c] = max(
    dp[i-1][c],                          # не берём
    dp[i-1][c - w[i]] + v[i]   если c >= w[i]   # берём
)

База: dp[0][c] = 0 для всех c (из нуля предметов ценность нулевая). Порядок: по возрастанию i, внутри — любой.

def knapsack01(weights: list[int], values: list[int], cap: int) -> int:
    """Классическая 2D-версия. Время O(n·cap), память O(n·cap)."""
    n = len(weights)
    dp = [[0] * (cap + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        w, v = weights[i - 1], values[i - 1]
        for c in range(cap + 1):
            dp[i][c] = dp[i - 1][c]                       # вариант «не берём»
            if c >= w:
                dp[i][c] = max(dp[i][c], dp[i - 1][c - w] + v)   # вариант «берём»
    return dp[n][cap]

5.2. Свёртка в одномерный массив

Каждая строка зависит только от предыдущей — значит хватит одного массива. Но здесь прячется самая известная ловушка ДП: направление внутреннего цикла определяет семантику задачи.

def knapsack01_1d(weights: list[int], values: list[int], cap: int) -> int:
    """Время O(n·cap), память O(cap)."""
    dp = [0] * (cap + 1)
    for w, v in zip(weights, values):
        # СПРАВА НАЛЕВО: dp[c - w] ещё хранит значение прошлой строки,
        # поэтому предмет не может быть использован дважды.
        for c in range(cap, w - 1, -1):
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[cap]


def knapsack_unbounded(weights: list[int], values: list[int], cap: int) -> int:
    """Неограниченный рюкзак: каждый предмет доступен в любом количестве."""
    dp = [0] * (cap + 1)
    for w, v in zip(weights, values):
        # СЛЕВА НАПРАВО: dp[c - w] уже пересчитан с этим предметом,
        # значит предмет можно брать многократно. Это и есть нужная семантика.
        for c in range(w, cap + 1):
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[cap]

Разница — одна строка range. Если перепутать, код не упадёт и не выдаст исключение: он молча решит другую задачу. Это надо один раз понять и больше никогда не вспоминать наизусть: спрашивайте себя «dp[c-w] — это старое значение или новое?».

5.3. Ограниченный рюкзак и бинарная разбивка

Если предмет доступен в k экземплярах, наивно писать цикл по количеству — получится O(n·C·k). Правильный приём: разбить k на степени двойки 1, 2, 4, …, k - 2^m + 1 и свести к 0/1-рюкзаку. Любое число от 0 до k представимо суммой подмножества этих частей, а количество частей — O(log k).

def knapsack_bounded(items: list[tuple[int, int, int]], cap: int) -> int:
    """items: список (вес, ценность, количество). Время O(cap · Σ log k)."""
    dp = [0] * (cap + 1)
    for w, v, k in items:
        part = 1
        while k > 0:
            take = min(part, k)          # последняя пачка может быть неполной
            k -= take
            pw, pv = w * take, v * take
            for c in range(cap, pw - 1, -1):
                dp[c] = max(dp[c], dp[c - pw] + pv)
            part *= 2
    return dp[cap]

Существует и вариант за O(n·C) через монотонный дек по остаткам от деления на вес — см. раздел 9 и разбор на cp-algorithms.

5.4. Псевдополиномиальность — важнее, чем кажется

Сложность O(n·C) выглядит полиномиальной, но это обман. Размер входа — это число бит: вместимость C записывается log C битами, значит O(n·C) = O(n · 2^(log C)) — экспонента от длины входа. Такая сложность называется псевдополиномиальной.

Практические следствия:

• n = 100, C = 10⁴ — мгновенно. n = 100, C = 10⁹ — невозможно, хотя вход занял 20 байт.
• Если веса дробные (цены в рублях с копейками), домножьте на 100 и работайте в целых; если множители доводят C до миллиардов — ДП не подходит, нужны приближённые схемы (FPTAS для рюкзака) или солвер целочисленного программирования.
• Ровно на этой границе живёт NP-полнота: задача о рюкзаке NP-трудна, но имеет псевдополиномиальный алгоритм — то есть она слабо NP-трудна.

6. ДП на двух последовательностях: LCS и Левенштейн

Второе по практической важности семейство. На нём построены diff, git, поиск с опечатками, выравнивание ДНК и автодополнение.

6.1. Наибольшая общая подпоследовательность

Состояние: dp[i][j] — длина LCS префиксов a[:i] и b[:j]. Переход: если последние символы совпали, они гарантированно могут войти в ответ вместе (доказывается вырезанием-вставкой); иначе один из них точно не нужен.

dp[i][j] = dp[i-1][j-1] + 1                  если a[i-1] == b[j-1]
dp[i][j] = max(dp[i-1][j], dp[i][j-1])       иначе

def lcs(a: str, b: str) -> str:
    """Возвращает саму подпоследовательность. Время O(n·m), память O(n·m)."""
    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])

    # Восстановление: идём из правого нижнего угла назад по тем же правилам.
    res, i, j = [], n, m
    while i > 0 and j > 0:
        if a[i - 1] == b[j - 1]:
            res.append(a[i - 1])
            i, j = i - 1, j - 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return "".join(reversed(res))

Восстановление ответа — отдельный навык. Есть два способа: (а) хранить таблицу «откуда пришли» — просто, но +O(n·m) памяти; (б) идти назад по самой таблице dp, переигрывая условия перехода — памяти не требует, но код должен точно повторять логику прямого прохода. Второй способ предпочтительнее: одна таблица вместо двух и невозможность рассинхронизации.

Если нужна только длина, память сворачивается до двух строк — O(min(n, m)). Но восстановить ответ при этом уже нельзя. Компромисс — алгоритм Хиршберга (D. S. Hirschberg, 1975): делим вторую строку пополам, находим точку разреза первой через два прохода с O(m) памятью и рекурсивно решаем две половины. Итог: O(n·m) времени, O(min(n,m)) памяти и полное восстановление. Оригинальная статья занимает две страницы и стоит прочтения.

6.2. Расстояние Левенштейна со свёрткой памяти

def levenshtein(a: str, b: str) -> int:
    """Минимум операций вставки/удаления/замены. Время O(n·m), память O(min(n,m))."""
    if len(a) < len(b):
        a, b = b, a                        # держим короткую строку по столбцам
    prev = list(range(len(b) + 1))         # база: превратить префикс a в пустую b
    for i, ca in enumerate(a, start=1):
        cur = [i] + [0] * len(b)
        for j, cb in enumerate(b, start=1):
            cur[j] = min(
                prev[j] + 1,                          # удаление символа из a
                cur[j - 1] + 1,                       # вставка символа из b
                prev[j - 1] + (ca != cb),             # замена или совпадение
            )
        prev = cur
    return prev[len(b)]

Практическая деталь: при поиске «есть ли слово на расстоянии ≤ k» полную таблицу считать не нужно — достаточно диагональной полосы шириной 2k + 1, что даёт O(n·k). Если минимум по строке превысил k, можно выйти досрочно. Именно так работают fuzzy-поиск в Elasticsearch и git diff на больших файлах.

7. ДП по подмножествам и по деревьям

7.1. Битовая маска: коммивояжёр за O(2ⁿ · n²)

Когда n ≤ 20, состоянием может быть подмножество. dp[mask][last] — минимальная стоимость пути, который посетил ровно вершины из mask и закончился в last.

def tsp(dist: list[list[int]]) -> int:
    """Гамильтонов цикл минимального веса. Время O(2ⁿ·n²), память O(2ⁿ·n)."""
    n = len(dist)
    INF = float("inf")
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0                                   # стартуем в вершине 0
    for mask in range(1 << n):
        if not mask & 1:                           # вершина 0 всегда посещена
            continue
        for last in range(n):
            if dp[mask][last] == INF:
                continue
            for nxt in range(n):
                if mask >> nxt & 1:                # уже были — пропускаем
                    continue
                nmask = mask | (1 << nxt)
                cand = dp[mask][last] + dist[last][nxt]
                if cand < dp[nmask][nxt]:
                    dp[nmask][nxt] = cand
    full = (1 << n) - 1
    return min(dp[full][last] + dist[last][0] for last in range(n))

Перебор всех маршрутов — O(n!); при n = 20 это 2.4 · 10¹⁸. ДП даёт 2²⁰ · 400 ≈ 4 · 10⁸ — разница между «никогда» и «полминуты». Это алгоритм Хелда–Карпа (1962), и до сих пор асимптотически лучшего точного решения TSP не известно.

Итерация по маске снаружи корректна, потому что nmask > mask всегда (добавляем бит) — то есть номер маски задаёт топологический порядок на графе зависимостей.

Полезные битовые идиомы для этого класса задач:

mask & (mask - 1)          # снять младший установленный бит
mask & -mask               # выделить младший установленный бит
bin(mask).count("1")       # популяция битов (в C++ — __builtin_popcount)
sub = (sub - 1) & mask     # перебор всех подмасок mask за O(3ⁿ) суммарно

7.2. ДП на дереве: максимальное независимое множество

Состояние — вершина плюс её «локальное решение»: dp[v][0] — лучший ответ в поддереве v, если v не взята, dp[v][1] — если взята.

def max_weight_independent_set(children: list[list[int]], weight: list[int]) -> int:
    """Дерево задано списками детей, корень 0. Время O(n), память O(n).
    Итеративный обход, чтобы не упереться в лимит рекурсии на цепочке из 10^5 вершин."""
    n = len(weight)
    dp = [[0, 0] for _ in range(n)]

    order, stack = [], [0]
    while stack:                                    # получаем порядок обхода в глубину
        v = stack.pop()
        order.append(v)
        stack.extend(children[v])

    for v in reversed(order):                       # обратный порядок = дети раньше родителя
        dp[v][1] = weight[v]
        for c in children[v]:
            dp[v][0] += max(dp[c][0], dp[c][1])     # v не взята — ребёнок свободен
            dp[v][1] += dp[c][0]                    # v взята — ребёнок обязан быть не взят
    return max(dp[0][0], dp[0][1])

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

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

7.3. ДП как автомат состояний

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

def max_profit(prices: list[int], fee: int) -> int:
    """Торговля с комиссией и днём охлаждения. Время O(n), память O(1)."""
    NEG = float("-inf")
    free, hold, cool = 0, NEG, NEG          # три состояния автомата
    for p in prices:
        free, hold, cool = (
            max(free, cool),                # остаёмся свободны или отошли от охлаждения
            max(hold, free - p),            # держим или покупаем сегодня
            (hold + p - fee) if hold > NEG else NEG,   # продали сегодня
        )
    return max(free, cool, 0)

Такой взгляд снимает большинство «а как придумать состояние» вопросов: нарисуйте автомат допустимых режимов, и измерения dp появятся сами. Заодно вы получите визуальную проверку — если из состояния нет исходящего перехода, вы что-то забыли.

8. Как выбирать: LIS двумя способами

Одна и та же задача часто допускает несколько формулировок ДП с разной асимптотикой. Наибольшая возрастающая подпоследовательность (LIS) — лучший пример.

def lis_quadratic(a: list[int]) -> int:
    """dp[i] — длина LIS, заканчивающейся ровно в i. Время O(n²), память O(n)."""
    n = len(a)
    dp = [1] * n
    for i in range(n):
        for j in range(i):
            if a[j] < a[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp, default=0)


from bisect import bisect_left

def lis_nlogn(a: list[int]) -> int:
    """tails[k] — минимальный возможный последний элемент LIS длины k+1.
    Массив tails строго возрастает, поэтому позиция ищется бинарным поиском.
    Время O(n log n), память O(n)."""
    tails: list[int] = []
    for x in a:
        pos = bisect_left(tails, x)
        if pos == len(tails):
            tails.append(x)        # удлинили самую длинную последовательность
        else:
            tails[pos] = x         # улучшили окончание длины pos+1
    return len(tails)

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

Важная деталь: tails не является самой LIS — это вспомогательная структура. Чтобы восстановить последовательность, нужно параллельно хранить массив предшественников.

9. Оптимизация переходов: убираем ещё один множитель

Когда состояний столько, сколько нужно, а перехода O(n) не хватает по времени, начинается вторая половина ДП. Общая идея всегда одна: переход — это агрегат по множеству, которое меняется предсказуемо; значит агрегат можно поддерживать инкрементально.

9.1. Префиксные суммы и разреженные структуры

Если dp[i] = min(dp[j] + cost) по отрезку j ∈ [l, r], а cost не зависит от j — это запрос минимума на отрезке. Дерево отрезков или разреженная таблица дают O(log n) или O(1) на переход. Самый дешёвый частный случай — суммы: префиксный массив, O(1) на запрос.

9.2. Монотонный дек: скользящий минимум за O(1) амортизированно

Если окно [i-k, i-1] сдвигается монотонно, поддерживать минимум можно двусторонней очередью.

from collections import deque

def max_score_with_jump(a: list[int], k: int) -> int:
    """dp[i] = a[i] + max(dp[i-k..i-1]). Прыжки длиной не более k.
    Время O(n) вместо O(n·k), память O(k)."""
    n = len(a)
    dp = [0] * n
    dp[0] = a[0]
    dq = deque([0])                     # индексы, dp по ним убывает
    for i in range(1, n):
        while dq and dq[0] < i - k:     # хвост вышел за окно
            dq.popleft()
        dp[i] = dp[dq[0]] + a[i]
        while dq and dp[dq[-1]] <= dp[i]:   # элементы хуже текущего бесполезны навсегда
            dq.pop()
        dq.append(i)
    return dp[n - 1]

Тот же приём, что в статье Два указателя и скользящее окно, только применённый к массиву dp, а не к входным данным. Амортизация: каждый индекс входит в дек и выходит из него ровно один раз.

9.3. Convex Hull Trick

Если переход имеет вид dp[i] = min(dp[j] + b[j] · x[i]), то каждый j задаёт прямую y = b[j]·x + dp[j], а dp[i] — значение нижней огибающей в точке x[i]. Поддерживая выпуклую оболочку прямых, получаем O(log n) или даже O(1) на переход при монотонных наклонах. Типовая задача — разбиение массива на отрезки со стоимостью, квадратичной по длине. Разбор и код: cp-algorithms, Convex hull trick.

9.4. Divide & Conquer оптимизация

Условие: opt[i][j] — точка оптимума — монотонна по j. Тогда вместо перебора всех разбиений можно рекурсивно делить диапазон, получая O(n log n) вместо O(n²) на слой. Проверка монотонности обычно делается эмпирически (посчитать opt брутфорсом на малых тестах) или через неравенство четырёхугольника.

9.5. Оптимизация Кнута–Яо

Для интервального ДП вида dp[i][j] = min(dp[i][k] + dp[k][j]) + C[i][j], где стоимость C удовлетворяет неравенству четырёхугольника C[a][c] + C[b][d] ≤ C[a][d] + C[b][c] при a ≤ b ≤ c ≤ d, верно opt[i][j-1] ≤ opt[i][j] ≤ opt[i+1][j]. Ограничив перебор k этим диапазоном, получаем O(n²) вместо O(n³). Исторически это результат Кнута для оптимальных бинарных деревьев поиска, обобщённый Яо.

9.6. Сводка

Порядок действий на практике: сначала правильное состояние, потом корректный O(состояния × переход) код, и только потом оптимизация. Оптимизировать неверную динамику — самый быстрый способ потерять день.

10. Типичные ошибки

Состояние не марковское. Переход тайком зависит от истории. Симптом: код работает на примерах из условия и падает на случайных тестах. Лечение: выписать переход формулой и проверить, что в правой части встречаются только параметры состояния.

Перепутано направление внутреннего цикла при свёртке памяти. 0/1 превращается в неограниченный или наоборот. Лечение: всегда сверяйте свёрнутую версию с 2D-версией на случайных входах — это тест на пять строк, который ловит ошибку мгновенно.

Неверная база. Особенно опасно смешение «невозможно» и «ноль». В задаче о размене dp[0] = 0 (ноль монет на нулевую сумму), но dp[c] = INF для недостижимых c. Если вместо INF поставить 0, алгоритм радостно сообщит, что сумму 3 монетами {2} разменять можно. Проверяйте, что арифметика с INF не переполняется: в C++ INT_MAX + 1 — UB, используйте INF = 1e9 и явную проверку if dp[j] < INF.

Off-by-one в индексации. Строки индексируются с нуля, а dp — с единицы (потому что dp[0] = пустой префикс). Договоритесь один раз: «dp[i] относится к первым i элементам, то есть к a[i-1]» — и придерживайтесь этого во всём коде.

Мемоизация мутабельного состояния. @lru_cache на функции, принимающей список, упадёт (unhashable type), а на функции, принимающей объект с __hash__ по id, — молча вернёт мусор. Передавайте кортежи или примитивы.

Переполнение стека. Top-down на n = 10⁵ в Python даст RecursionError, в C++ — segfault. sys.setrecursionlimit увеличивает лимит интерпретатора, но не размер стека ОС. Правильное решение — переписать на табуляцию.

Считаем количество без взятия модуля. В задачах на подсчёт числа способов ответы растут экспоненциально. В Python это «просто медленно» (длинная арифметика), в C++ — тихое переполнение. Берите % MOD внутри цикла, а не в конце.

Экономия памяти вместо экономии времени. Люди героически сворачивают O(n²) память в O(n), когда узкое место — время. Профилируйте, а не угадывайте.

11. Где ДП живёт в продакшене

ДП — не спортивная дисциплина. Вот системы, внутри которых оно работает прямо сейчас.

git diff, svn, любой code review. Алгоритм Юджина Майерса (1986) — это ДП на редакционном графе с оптимизацией по диагоналям, O((n+m)·D), где D — размер различий. Оригинальная статья «An O(ND) Difference Algorithm and Its Variations» читается на удивление легко. Git использует его вариант по умолчанию, плюс эвристику histogram для более осмысленных диффов.

Биоинформатика. Needleman–Wunsch (глобальное выравнивание, 1970) и Smith–Waterman (локальное, 1981) — прямые родственники LCS с матрицей замен и штрафом за разрыв. Smith–Waterman даёт точный ответ, но O(n·m) на геномах непозволительно, поэтому в BLAST его заменяют эвристикой с засевом — классический размен точности на скорость.

Распознавание речи и NLP. Алгоритм Витерби ищет наиболее вероятную последовательность скрытых состояний в HMM: dp[t][s] = max(dp[t-1][s'] · P(s'→s)) · P(obs[t] | s). Это ДП по времени и состояниям. Он же используется в декодировании свёрточных кодов в сотовой связи и в POS-теггинге. Хорошее изложение — приложение A к Jurafsky & Martin, Speech and Language Processing.

Оптимизаторы SQL. Выбор порядка соединения таблиц — это ДП по подмножествам, ровно как TSP. Схема из статьи Селинджер и соавторов о System R (1979) до сих пор лежит в основе PostgreSQL: при числе таблиц до geqo_threshold (по умолчанию 12) планировщик перебирает подмножества динамикой, выше — переключается на генетический алгоритм. Оригинальная статья.

Вёрстка текста. Алгоритм Кнута–Пласса в TeX разбивает абзац на строки, минимизируя суммарную «неприятность», — ДП по позициям разрыва с восстановлением ответа. Именно поэтому абзацы в TeX выглядят лучше, чем в жадных верстальщиках. Breaking Paragraphs into Lines, 1981.

Обучение с подкреплением и управление. Уравнение Беллмана — это буквально ДП, и сам термин «динамическое программирование» придумал Ричард Беллман в 1950-х (по его признанию, название выбиралось так, чтобы звучало солидно для министерства обороны и не выдавало, что речь про математику). Value iteration и policy iteration — прямые потомки. The Theory of Dynamic Programming, RAND, 1954.

Финансы и планирование. Оптимальное исполнение крупной заявки, задачи о замене оборудования, планирование производства — всё это рюкзачные и линейные динамики, часто с состоянием «текущий запас».

Обработка изображений. Seam carving — контентно-зависимое изменение размера — ищет минимальный по энергии «шов» через изображение динамикой по строкам, O(w·h).

12. Мини-итог

• ДП работает там и только там, где есть оптимальная подструктура и перекрывающиеся подзадачи. Проверяйте оба условия перед тем, как писать код.
• Проектирование идёт в порядке: состояние → переход → база → порядок вычисления. Формула сложность = состояния × переход даёт оценку до написания кода.
• Мемоизация ближе к формуле и считает только достижимое, табуляция быстрее и позволяет сворачивать память. Пишите первую, потом вторую, потом сравните их на случайных тестах.
• Направление внутреннего цикла при свёртке 2D → 1D — это не стиль, а семантика задачи.
• O(n·C) для рюкзака псевдополиномиальна; при больших числовых параметрах ДП перестаёт работать, и нужны приближённые схемы.
• Оптимизации переходов (дек, CHT, D&C, Кнут–Яо) снимают множитель, но применяются только после того, как корректная версия уже написана.
• Восстановление ответа — отдельная задача. Проще всего идти назад по готовой таблице, повторяя условия перехода.

Что почитать

• CLRS, 4-е издание, глава 14 «Dynamic Programming» — самое строгое изложение с доказательствами оптимальной подструктуры. MIT Press
• Steven Skiena, The Algorithm Design Manual, глава 10 — лучшая книга по интуиции «как придумать состояние». algorist.com
• MIT 6.006 / 6.046, лекции Эрика Демейна по ДП — знаменитый разбор «пять шагов ДП». MIT OpenCourseWare
• cp-algorithms — практические разборы оптимизаций: D&C optimization, Knuth optimization
• USACO Guide, Introduction to DP — задачи по возрастанию сложности с разборами. usaco.guide
• Bellman, R. Dynamic Programming, 1957 — первоисточник, до сих пор читаемый.

Что дальше

Мы несколько раз упирались в то, что граф подзадач должен быть ациклическим, а порядок вычисления — топологическим. Дальше мы разберём эти понятия напрямую и научимся обходить графы: Обходы графов: BFS, DFS, топологическая сортировка, компоненты. После этого станет очевидно, почему Беллман–Форд — это динамика по числу рёбер, а Дейкстра — жадный алгоритм поверх той же оптимальной подструктуры; об этом — Кратчайшие пути.