Динамическое программирование: базовые шаблоны линейного и двумерного DP ТЕМА

О чём статья

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

Эта статья — про базовый каркас: одномерный (линейный) и двумерный DP. Это два самых частых формата на полосе сложности CF 1100–1700, и через них же проходят почти все более сложные техники — DP на дереве, DP с подмножествами состояний, DP с двумя указателями. Цель — довести шаблон до автоматизма, чтобы на следующих темах усложнение шло только в новых элементах состояния, а каркас уже не отвлекал.

---

Когда применять: сигналы в условии

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

• «Сколько способов / сколькими способами …». Подсчётные задачи почти всегда вписываются в DP: state — текущая позиция / параметр, переход — сумма по способам.
• «Минимальная / максимальная стоимость, при которой …». Оптимизационные DP — state описывает «что уже зафиксировано», переход — выбор очередного шага.
• «Можно ли получить … из …». Логические DP с булевым ответом: state — достижимая комбинация параметров.
• Маленький параметр, по которому идёт перебор. Если в условии есть параметр $k \le 100$, или массив длины $n \le 5000$, или сетка $n \cdot m \le 10^6$, и при этом задача на оптимизацию или подсчёт — DP выходит на первое место в списке кандидатов.
• «Каждый элемент берём не больше одного раза» / «два соседа не выбираются вместе» / «сумма $\le S$». Локальное ограничение, которое в greedy ломается на простом контрпримере, а в DP корректно учитывается через состояние.

Если ничего из этого нет, DP, скорее всего, не нужен. Если есть один сигнал — стоит попробовать. Если два-три — почти точно DP, остаётся определить размерность состояния.

---

Базовый шаблон

Идея в одну фразу

Завести функцию (или массив) $f$, в которой $f[s]$ — ответ на подзадачу с состоянием $s$. Заполнять $f$ в порядке, при котором каждое значение зависит только от уже посчитанных.

Псевдокод (линейный DP)

определить размерность состояния и его смысл
завести массив f нужной длины, заполнить «нейтральным» значением
проставить базу: f[начальные состояния] ← конкретные числа

для каждого состояния s в правильном порядке:
    f[s] ← объединение(f[s'], …) по всем s' → s переходам

вывести f[требуемое состояние]

Сложность шаблона: $O(\text{число состояний} \cdot \text{среднее количество переходов})$.

Четыре вопроса перед написанием

Любой DP-шаблон сводится к ответам на четыре вопроса. Их полезно явно проговорить перед тем, как написать первую строчку кода:

1. Что такое состояние? Какой набор параметров полностью описывает «текущую ситуацию» так, что ответ для неё не зависит от того, как мы в неё пришли. Это ключевой вопрос: правильно сформулированное состояние решает половину задачи.
2. Что хранится в $f[s]$? Число способов? Минимальная стоимость? Максимальная сумма? Булевое «достижимо»?
3. Каков переход? В состояние $s$ как мы могли прийти и из каких $s'$? Или: из $s$ в какие $s'$ мы можем уйти? Один из этих двух взглядов всегда удобнее.
4. Какова база? Какие состояния «начальные», и какое значение в них стоит до пересчёта.

Когда все четыре пункта проговорены — порядок обхода обычно становится очевидным: начинаем с базы, идём в направлении, при котором все «зависимости» уже посчитаны.

Почему шаблон работает

DP формально опирается на принцип оптимальности Беллмана: в оптимальном решении любая «префиксная» подзадача тоже решена оптимально. Если это не так — DP неприменим, и нужна другая техника (greedy, поток, и т.д.).

В подсчётных задачах аналог — линейность: общее число способов есть сумма способов по непересекающимся группам, на которые разбивается множество способов. Если способы пересекаются (один путь принадлежит двум группам одновременно) — наивный DP с суммой даёт двойной счёт. Это сразу красный флаг: либо сменить разбиение, либо использовать включения-исключения.

---

Задача-иллюстрация 1: «Лестница» (линейный DP, ~CF 1100)

Условие

Дана лестница из $n$ ступенек. Можно подниматься на 1 или 2 ступеньки за один шаг. Сколько различных способов взойти от ступеньки $0$ до ступеньки $n$?

Ограничения: $1 \le n \le 10^5$. Ответ может быть большим — выводить по модулю $10^9 + 7$.

Формат ввода: одно число $n$.

Формат вывода: одно число — количество способов.

Пример. $n = 4$. Способы: $1+1+1+1$, $1+1+2$, $1+2+1$, $2+1+1$, $2+2$. Итого $5$ способов.

Применение шаблона

Отвечаем на четыре вопроса:

1. Состояние: одно число $i$ — текущая ступенька, $0 \le i \le n$.
2. $f[i]$: количество способов добраться до ступеньки $i$.
3. Переход: в ступеньку $i$ можно прийти из $i - 1$ (шаг на 1) или из $i - 2$ (шаг на 2). Поэтому $f[i] = f[i - 1] + f[i - 2]$.
4. База: $f[0] = 1$ (мы уже стоим внизу, один «пустой» способ). $f[1] = 1$ (один способ: один шаг на 1).

Состояний $n + 1$, переходов на каждое — два. Итог — $O(n)$.

Разбор на примере

$n = 4$. База: $f[0] = 1, f[1] = 1$.

Сходится с подсчётом руками — 5 способов. ✓

Код решения

Что поменялось

Переход — двучленный, состояние одномерное. Это самая компактная форма DP. Сложность по памяти можно ужать с $O(n)$ до $O(1)$, если хранить только последние два значения (популярный приём «rolling array»):

prev, cur = 1, 1
for i in range(2, n + 1):
    prev, cur = cur, (prev + cur) % MOD
print(cur)

В олимпиадных задачах с $n \le 10^5$ обе формы укладываются в лимит. Но привычка сразу видеть, какие предыдущие значения нужны для перехода, окупается на задачах с $n \le 10^7$, где память важна.

---

Задача-иллюстрация 2: «Максимум суммы по пути в сетке» (двумерный DP, ~CF 1300)

Условие

Дана сетка $n \times m$ с целыми числами $a[i][j]$. Из левой верхней клетки $(0, 0)$ нужно дойти до правой нижней $(n-1, m-1)$, перемещаясь только вправо или вниз. Найти максимальную сумму чисел на пути.

Ограничения: $1 \le n, m \le 1000$, $|a[i][j]| \le 10^4$.

Пример. Сетка $3 \times 3$:

1 3 1
1 5 1
4 2 1

Оптимальный путь: $1 \to 3 \to 5 \to 2 \to 1$. Сумма = $12$.

Применение шаблона

1. Состояние: пара $(i, j)$ — текущая клетка, $0 \le i < n$, $0 \le j < m$.
2. $f[i][j]$: максимальная сумма на пути от $(0, 0)$ до $(i, j)$.
3. Переход: в клетку $(i, j)$ можно прийти сверху из $(i - 1, j)$ или слева из $(i, j - 1)$. Поэтому

$$f[i][j] = a[i][j] + \max(f[i-1][j],\ f[i][j-1]),$$

с поправкой на границы: если $i = 0$, остаётся только переход слева; если $j = 0$ — только сверху; в $(0, 0)$ значение равно $a[0][0]$. 4. База: $f[0][0] = a[0][0]$.

Состояний $n \cdot m$, переходов — $O(1)$. Итог — $O(n m)$.

Что меняется по сравнению с линейным DP

• Размерность состояния выросла на единицу. Теперь массив двумерный — f[n][m].
• Переход — два слагаемых вместо одного. В этом нет принципиальной новизны, но добавляются проверки границ — типичный источник off-by-one и IndexError.
• Порядок обхода: $f[i][j]$ зависит от $f[i-1][j]$ и $f[i][j-1]$ — оба меньше или равны $(i, j)$ по «лексикографически частичному порядку». Поэтому два вложенных цикла $i$ от $0$ до $n-1$ и $j$ от $0$ до $m-1$ гарантируют корректность: к моменту посчёта $f[i][j]$ оба зависимых значения уже посчитаны.

Разбор на примере

$n = m = 3$, сетка как выше.

База: $f[0][0] = 1$.

Первая строка ($i = 0$, переход только слева):

$f[0][1] = 1 + 3 = 4$, $f[0][2] = 4 + 1 = 5$.

Первый столбец ($j = 0$, переход только сверху):

$f[1][0] = 1 + 1 = 2$, $f[2][0] = 2 + 4 = 6$.

Внутренние клетки:

$f[1][1] = 5 + \max(4, 2) = 9$. $f[1][2] = 1 + \max(5, 9) = 10$. $f[2][1] = 2 + \max(9, 6) = 11$. $f[2][2] = 1 + \max(10, 11) = \mathbf{12}$. ✓

Код решения

Можно записать ещё компактнее, обработав границы через «отрицательную бесконечность» вне массива:

NEG_INF = float('-inf')
def get(i, j):
    if i < 0 or j < 0:
        return 0 if (i == -1 and j == 0) or (i == 0 and j == -1) else NEG_INF
    return f[i][j]

Но в учебном коде явная обработка первой строки и первого столбца читабельнее. На олимпиадах оба стиля встречаются; выбор — вопрос привычки.

Что поменялось vs линейный DP

Состояние стало двумерным; переход — два слагаемых; порядок обхода — два вложенных цикла. Принципиально нового ничего: всё та же дисциплина «состояние → переход → база → порядок».

Запомнить полезно: для двумерного DP порядок вложенности циклов определяется тем, как зависит состояние. В этой задаче — оба цикла идут «снизу вверх» (от $0$ к $n-1$ / $m-1$), потому что $f[i][j]$ зависит от меньших индексов. Если бы мы шли с правой нижней клетки и хотели дойти до левой верхней, циклы пришлось бы перевернуть.

---

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

1. Неверно сформулированное состояние. «Состояние = текущая клетка + что-то ещё, что я подразумеваю» — самая частая ошибка новичков. Если в формулировке проскакивает «при условии, что я перед этим сделал то-то» — это «то-то» должно быть в состоянии, иначе оно потеряется при переходе.
2. Пропущенная база. Массив инициализирован нулями, и $f[0]$ или $f[0][0]$ забыт. На задачах с подсчётом «сколько способов» это даёт ноль везде; на оптимизации — некорректные сравнения с нулём.
3. Неверный порядок обхода. Линейный DP — почти всегда $i$ от $0$ к $n-1$, проблем нет. В двумерном — пара вложенных циклов, и порядок вложенности должен соответствовать тому, какие индексы уже посчитаны к моменту текущей итерации. Если в переходе появляется $f[i+1][j]$ — нужен обратный обход.
4. Off-by-one на границах массива. «У меня $i$ от $1$ до $n$, и я обращаюсь к $f[i-1]$ — а в $i = 0$ ничего нет». Решение — либо явно обработать первую строку / первый столбец отдельно (как в коде выше), либо ввести «фиктивную» нулевую строку с нейтральным значением.
5. Забытый модуль в подсчётных задачах. На «лестнице» при $n = 100$ ответ — число Фибоначчи $F_{101}$, которое уже не помещается в int64. В Python переполнения нет, но без модуля число может стать огромным, и тесты ожидают ответ по модулю — несовпадение даёт WA. В C++ — переполнение long long при больших $n$ без модуля.
6. int вместо long long в C++ при максимизации сумм. В сетке $1000 \times 1000$ с $|a[i][j]| \le 10^4$ максимальная сумма пути $\approx 2 \cdot 10^7$ — помещается в int. Но в типовых модификациях ($a[i][j] \le 10^9$, $n \le 10^5$) уже нужна 64-битная арифметика.
7. Неинициализированная отрицательная бесконечность. В DP на минимум начальное значение должно быть «больше любого валидного». Часто пишут INF = 1e9 и начинают сравнивать с реальными суммами в $10^{10}$ — сравнение ломается. На минимуме безопаснее INF = 4 * 10^{18} (в long long) или float('inf') в Python.

---

Когда DP не подходит

Не каждое «оптимизировать что-то по подзадачам» — это DP. Несколько случаев, когда шаблон с виду подходит, а на деле нет:

• Greedy решает быстрее и проще. Если задача допускает «локальный оптимальный выбор», который доказывается exchange argument'ом — DP избыточен. Классика: задача о скобочных последовательностях (greedy через счётчик), задача о минимальном количестве монет в каноничной системе (greedy от старшей).
• Состояний слишком много. Если для покрытия задачи нужно состояние с двумя параметрами по $10^5$ — это $10^{10}$ состояний, никакой DP не уложится. Сигнал — «нужно искать другую структуру»: либо существенно более узкое состояние, либо переход к структуре данных (segment tree, Fenwick).
• Зависимости циклические. Если $f[i]$ зависит от $f[j]$, где $j > i$, а $f[j]$ — от $f[i]$, обычный DP не работает. Это область «решаем как уравнение»: в графах — поиск кратчайших путей с отрицательными рёбрами (Bellman-Ford), на деревьях — DP с двумя проходами.
• Нелинейная агрегация. Если ответ — не сумма / минимум / максимум по предыдущим состояниям, а, скажем, медиана или $k$-й элемент по убыванию — стандартный DP даёт неверные результаты. Это сигнал к переходу на другие техники (порядковые статистики на лету, treap, sqrt-декомпозиция).

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

---

Связанные техники

• DP с подмножествами состояний (bitmask DP) — когда параметр состояния — двоичная маска от $0$ до $2^k - 1$. Применяется, когда $k \le 20$ и нужно «помнить, какое подмножество элементов уже использовали». Естественное расширение линейного DP.
• DP на дереве — состояние индексировано вершиной дерева, переход — комбинация подответов всех детей. Каркас тот же (состояние / переход / база), но порядок обхода — DFS-ordering. Удобнее всего реализуется через обход в глубину с возвращаемыми значениями.
• Префиксные суммы — родственная техника для диапазонных запросов. Если в DP-задаче переход требует сумму по подсегменту, префиксные суммы дают эту сумму за $O(1)$ и ускоряют DP с $O(n^2)$ до $O(n)$.
• Бинпоиск по ответу — альтернатива, когда задача звучит как «найти минимальное / максимальное $X$, при котором …». Часто заменяет DP, если есть монотонность.

Каждая из этих техник идёт в следующих частях серии «Алгоритмические основы» — сначала по отдельности, потом в комбинации с DP.

---

Итого

• Техника: заполнение массива $f[s]$ — ответов на подзадачи — в порядке, при котором каждая зависимость уже посчитана.
• Сложность шаблона: $O(\text{число состояний} \cdot \text{среднее количество переходов})$.
• Сигналы в условии: «сколько способов», «минимальная / максимальная стоимость», «можно ли получить», маленькие параметры, локальные ограничения.
• Четыре вопроса перед написанием: что такое состояние, что хранится в $f$, каков переход, какова база. Если на любой нет ответа — DP пока писать рано.
• Типичные ловушки: неверное состояние, забытая база, неверный порядок обхода, off-by-one на границах, потерянный модуль на подсчётных задачах, переполнение в C++ при суммах.