Стратегия победы: DP — от очевидного шаблона к ёмкому состоянию СТРАТЕГИЯ

О чём эта статья

«Стратегия победы» — серия про траекторию тренировки, а не про одну задачу. Берём одну технику и разбираем, как она растёт от базового шаблона до полноценного применения в составных задачах.

Динамическое программирование — отличный материал для такого разбора. На полосе CF 1200 решается линейный DP с состоянием в одно число. На 1600 — двумерный DP с парой параметров. На 2000+ — DP с экспоненциальным состоянием (битовая маска подмножества) или DP на дереве. Каркас «состояние → переход → база → порядок обхода» во всех трёх случаях один и тот же; растёт только размерность состояния.

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

---

Ядро техники

DP — это заполнение массива $f[s]$ ответами на подзадачи в порядке, при котором каждое значение зависит только от уже посчитанных. Если есть отдельная статья-«тема» по линейному и двумерному DP — она в серии «Алгоритмические основы». Здесь мы фокусируемся на прогрессии состояния между ступенями.

Базовый шаблон (псевдокод)

определить состояние s и его размерность
завести массив f, заполнить нейтральным значением
проставить базу: f[начальные состояния] = …

для каждого состояния s в порядке возрастания зависимостей:
    f[s] = объединение(f[s'] + переход(s' → s)) по всем s' → s

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

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

Что мы будем усложнять по мере роста

• Ступень 1 → ступень 2. Состояние из одного параметра становится двумерным. Появляется второй индекс — обычно «оставшийся ресурс» (вес, длина, бюджет).
• Ступень 2 → ступень 3. Один из параметров переходит из «маленького числа» в подмножество (битовая маска). Размер состояния перестаёт быть полиномиальным от $n$ — он становится $\sim n \cdot 2^n$. Это допустимо, только когда $n$ маленькое (обычно $n \le 20$).

Это и есть смысл серии: не «3 разные задачи», а осознанный путь между ними с явной логикой усложнения.

---

Ступень 1 — CF ~1200 (базовый шаблон)

Условие: «Максимальная сумма независимых элементов»

Дан массив из $n$ положительных целых чисел $a_1, a_2, \ldots, a_n$. Нужно выбрать подмножество элементов так, чтобы:

1. Никакие два выбранных элемента не были соседними по индексу.
2. Сумма выбранных элементов была максимальной.

Вывести максимальную сумму.

Ограничения: $1 \le n \le 10^5$, $1 \le a_i \le 10^4$.

Пример. $n = 5$, $a = [3, 2, 7, 10, 12]$. Лучшие выборы: $\{a_1, a_3, a_5\} = 3 + 7 + 12 = 22$ или $\{a_2, a_4\} = 2 + 10 = 12$ или $\{a_3, a_5\} = 7 + 12 = 19$. Максимум — $22$.

Как применяется базовый шаблон

Состояние — индекс $i$, описывающий «префикс массива до $a_i$ включительно». В $f[i]$ хранится максимальная сумма независимых элементов в этом префиксе.

Переход: для $a_i$ есть два варианта.

• Не берём $a_i$. Тогда лучший ответ для префикса до $i$ — тот же, что для префикса до $i - 1$.
• Берём $a_i$. Тогда $a_{i-1}$ брать нельзя, лучший ответ — $a_i$ плюс максимум для префикса до $i - 2$.

Получаем рекуррентность

$$f[i] = \max(f[i - 1],\ f[i - 2] + a_i).$$

База: $f[0] = 0$ (пустой префикс), $f[1] = a_1$ (можно либо взять, либо нет, $a_1 \ge 0$, выгоднее взять).

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

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

$a = [3, 2, 7, 10, 12]$, индексация с 1. База: $f[0] = 0$, $f[1] = 3$.

Совпадает с подсчётом руками. ✓

Код решения

Сложность: $O(n)$ по времени, $O(1)$ по памяти (rolling array).

Что закрыли

На ступени 1 состояние — одно число, переход — два слагаемых, база — два значения. Это чистый каркас одномерного DP, в котором ничего не отвлекает.

На следующем шаге появится второй индекс, описывающий «оставшийся ресурс».

---

Ступень 2 — CF ~1600 (двумерное состояние с ресурсом)

Условие: «Рюкзак 0/1»

Есть $n$ предметов, каждый предмет $i$ имеет вес $w_i$ и стоимость $v_i$. Есть рюкзак вместимости $W$. Каждый предмет можно либо взять (один раз), либо не взять. Найти максимальную суммарную стоимость, при которой суммарный вес не превышает $W$.

Ограничения: $1 \le n \le 1000$, $1 \le W \le 10^5$, $1 \le w_i, v_i \le 1000$.

Пример. $n = 3$, $W = 5$, предметы: $(w, v) = (3, 6), (2, 4), (4, 5)$. Варианты: предметы $\{1\}$ — вес 3, стоимость 6. $\{2\}$ — 2, 4. $\{3\}$ — 4, 5. $\{1, 2\}$ — 5, 10. $\{2, 3\}$ — 6 ($> 5$, нельзя). Максимум — $10$.

Чем эта задача сложнее ступени 1

В «Максимальной независимой сумме» состояние — только индекс $i$, потому что у нас не было ресурсного ограничения. В рюкзаке появляется бюджет веса $W$. Если описывать состояние одним $i$, то значение $f[i]$ должно вместить «лучшая стоимость для всех возможных оставшихся весов» — это уже не число, а функция от веса.

Поэтому состояние расширяется: «$i$ предметов рассмотрено, остаточный бюджет $W'$». Теперь $f[i][W']$ — число, и переход остаётся понятным.

Что меняется в шаблоне

• Состояние: было $(i)$, стало $(i, w)$, где $w \in [0, W]$ — суммарный вес уже взятых предметов.
• Переход: для предмета $i$ два варианта. Не брать — $f[i][w] = f[i-1][w]$. Брать (если $w_i \le w$) — $f[i][w] = \max(f[i][w], f[i-1][w - w_i] + v_i)$.
• База: $f[0][w] = 0$ для всех $w$ — без предметов стоимость 0.
• Доказательство корректности: оптимальный выбор для первых $i$ предметов либо включает предмет $i$, либо нет. В обоих случаях префиксная подзадача решается оптимально (принцип Беллмана).

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

$n = 3$, $W = 5$, предметы $(3,6), (2,4), (4,5)$.

Ответ — $f[3][5] = 10$. ✓

Например, $f[2][5]$ считается так: не берём предмет 2 — $f[1][5] = 6$; берём — $f[1][5-2] + 4 = f[1][3] + 4 = 6 + 4 = 10$. Максимум — $10$.

Код решения

Сложность: $O(n \cdot W)$ по времени, $O(W)$ по памяти — после оптимизации с одним массивом и обратным проходом по $w$.

Что закрыли

На ступени 2 состояние из одного индекса превратилось в пару «индекс + ресурс». Размер таблицы $f$ — $O(n \cdot W)$, переход — $O(1)$. Появилась первая нетривиальная ловушка: порядок прохода по $w$ внутри массива. При прямом проходе ($w$ от $0$ до $W$) предмет $i$ может быть учтён несколько раз — это уже неограниченный рюкзак, не 0/1.

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

---

Ступень 3 — CF ~2000+ (битовая маска подмножества)

Условие: «Минимальный гамильтонов путь»

Дан полный неориентированный граф из $n$ вершин с весами рёбер $d[i][j]$. Нужно начать с произвольной вершины и пройти через все $n$ вершин ровно по одному разу, минимизируя суммарный вес пройденных рёбер.

Ограничения: $1 \le n \le 18$, $1 \le d[i][j] \le 10^6$, $d[i][j] = d[j][i]$.

Пример. $n = 4$ с матрицей:

0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0

Возможный маршрут $1 \to 2 \to 4 \to 3$ имеет вес $10 + 25 + 30 = 65$. Маршрут $1 \to 3 \to 4 \to 2$ — $15 + 30 + 25 = 70$. Минимальный — $65$ (проверяется перебором всех $4!/2 = 12$ направленных маршрутов на 4-х вершинах при фиксированном направлении обхода).

Двойное гражданство. Эта задача одинаково честно попадает и в семью DP, и в семью «кратчайший путь во взвешенном графе» (Дейкстра / BFS на расширенном состоянии). Если построить граф $G^*$ из $n \cdot 2^n$ вершин-состояний $(\text{mask}, u)$ и проводить рёбра $(\text{mask}, u) \to (\text{mask} \cup \{v\}, v)$ с весом $d[u][v]$ для каждого $v \notin \text{mask}$, то задача — это поиск кратчайшего пути из любой стартовой вершины $\{s\}$, $s$, до любой вершины $((1 \ll n) - 1, *)$. Дейкстра на $G^*$ даёт ответ за $O((n \cdot 2^n) \log (n \cdot 2^n) + n^2 \cdot 2^n)$, что чуть хуже DP, но идейно — та же самая работа. Мы остаёмся в DP-рамке (форвард-обновление по mask), потому что граф $G^*$ — DAG (множество посещённых вершин монотонно растёт), и для DAG’а DP по топологическому порядку даёт чистый $O(n^2 \cdot 2^n)$ без логарифмического оверхеда. Подробнее о структурной близости BFS / Дейкстры и DP — в «Что закрыли» ниже.

Чем эта задача сложнее ступени 2

В рюкзаке состояние было «$i$ предметов рассмотрено, $w$ ресурс». Каждый предмет либо берём, либо нет — порядок не важен.

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

«Какое подмножество посещено» — это $2^n$ вариантов. При $n \le 18$ это $\le 2^{18} = 262\,144$ масок, что приемлемо. Состояние — $(\text{маска}, u)$, где $u$ — последняя посещённая вершина.

Что меняется в шаблоне

• Состояние: $(\text{mask}, u)$, $\text{mask} \in [0, 2^n)$ — битовая маска посещённых вершин, $u \in [0, n)$ — текущая вершина (последняя в маршруте).
• $f[\text{mask}][u]$: минимальный вес маршрута, посетившего ровно множество вершин из mask, заканчивающегося в $u$.
• Переход (forward DP): из состояния $(\text{mask}, u)$ переходим в $(\text{mask} | (1 \ll v), v)$ через ребро $u \to v$ для каждой не посещённой вершины $v$ (бит $v$ в mask равен $0$). Стоимость перехода — $d[u][v]$.
• База: $f[1 \ll s][s] = 0$ для всех $s \in [0, n)$ — стартуем с любой одной вершины.
• Ответ: $\min_u f[(1 \ll n) - 1][u]$ — посетили все вершины.

Сложность: состояний $n \cdot 2^n$, на каждом — $O(n)$ переходов. Итог — $O(n^2 \cdot 2^n)$.

При $n = 18$ это $\sim 8.5 \cdot 10^7$ операций — около 1 секунды в C++, $\sim 5$ секунд в Python (требуется аккуратный код).

Код решения

Сложность: $O(n^2 \cdot 2^n)$ по времени, $O(n \cdot 2^n)$ по памяти.

При больших $n$ (близких к 18) на Python без хитростей будет TL. В C++ та же логика проходит за $\sim 1$ секунду. Если на CF задача требует $n \le 20$ — придётся оптимизировать (например, перейти к битовой компоновке f[mask][u] в массив целых, использовать numpy или применить рассуждения о симметрии).

Что закрыли

На ступени 3 параметр перестал быть числом — он стал подмножеством. Это качественный скачок:

• Размер таблицы $f$ — экспоненциальный по $n$ ($O(n \cdot 2^n)$).
• Переход — линейный по $n$ (перебор следующей вершины).
• Сложность — $O(n^2 \cdot 2^n)$, что разумно только при $n \le 20$.

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

А ещё — про родство с BFS / Дейкстрой

Гамильтонов путь намеренно стоит в этой статье последним: на нём становится видна структурная близость DP и алгоритмов кратчайшего пути на графе, и эту близость стоит проговорить отдельно.

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

DP в нашей задаче работает чисто и без очередей именно потому, что граф состояний $(\text{mask}, u) \to (\text{mask} \cup \{v\}, v)$ — это DAG: mask монотонно растёт, цикла быть не может. На DAG’е достаточно идти в порядке возрастания mask — это автоматический топологический обход. Если бы циклы были (как у Дейкстры в общем графе), пришлось бы переключаться на priority queue.

Практически это значит:

• Сильный «графщик» решает эту задачу через Дейкстру на $G^*$ — пишет на 10 строк длиннее, получает лишний $\log$ в сложности, но не задумывается о порядке mask.
• Сильный «дп-шник» сразу видит DAG и пишет цикл по mask — короче и чуть быстрее.
• На олимпиаде — оба варианта проходят, обе классификации уважают одну и ту же задачу. Спор «это DP или граф?» бессмысленный: это и то, и другое.

То же самое работает в обратную сторону: задачи на «кратчайший путь с собиранием ключей» / «BFS по сетке с дополнительным состоянием инвентаря» (см. серию «Стратегия победы — графы») — это полноценные DP по (клетка, mask_ключей), просто решённые через FIFO-очередь, потому что веса единичные и удобнее не ломать голову над порядком обхода.

Вывод для тренировки. Если на разборе чувствуешь, что «вроде DP, но как-то странно» — попробуй переформулировать задачу как поиск кратчайшего пути на графе состояний; если структура ляжет — техника та же, просто другой словарь. И наоборот, на «графовой» задаче с маленьким состоянием стоит проверять, не ложится ли она в чистый DP по DAG’у — это часто даёт более простую реализацию.

---

Что нужно держать в голове при переходе между ступенями

Эта таблица — карта местности на тренировке. Видя в условии «маленькое $n$ ($\le 20$) + комбинаторика выбора», участник должен сразу подумать о bitmask. Видя «параметр $W \le 10^5$ + два варианта на каждом шаге» — о двумерном DP. Видя только индекс и линейный массив — о rolling 1D.

---

Типичные ловушки на каждой ступени

• Ступень 1. Забыть базу $f[0]$ или поставить её неверно (например, $f[0] = a_0$ вместо $0$, путая «префикс длины 0» с «первый элемент»). Симптом — ответ сдвинут.
• Ступень 2. Прямой проход по $w$ внутри предмета вместо обратного. Это превращает 0/1 рюкзак в неограниченный, ответы получаются завышенными. Запомнить намертво: обратный проход по $w$ для 0/1, прямой — для unbounded.
• Ступень 3. Включить вершину $u$ в маску дважды в переходе: в текущем состоянии $u$ уже посещена, а в коде переход не проверяет, что бит $v$ в mask равен $0$. Симптом — ответ занижен (маршрут «проходит через $u$ дважды» по сниженной стоимости).
• Везде: перепутать порядок вложенности циклов (особенно на ступени 3 — внешний должен идти по mask от 0 до $2^n - 1$, потому что f[mask | (1 << v)] зависит от f[mask]).

---

План тренировки

1. Решить ступень 1 самостоятельно, без подсмотра кода. Цель — понять, что состояние = индекс, переход = два слагаемых.
2. Решить 5 задач полосы CF 1100–1300 на тег dp — линейный DP в разных формулировках (подсчёт способов, минимум/максимум, булевая достижимость). На этой полосе освоить мускульную память «один индекс → один цикл → одно сравнение».
3. Перейти к ступени 2. Решить рюкзак 0/1, потом — задачу с тегом dp + knapsack на CF полосы 1500–1700. Если застреваем на «прямой/обратный проход» — значит ловушка не отработана, делаем ещё 2–3 задачи на 0/1.
4. Решить 5 задач полосы CF 1500–1700 на dp. Здесь же — двумерные DP без рюкзака (LCS, edit distance, DP на сетке с ограничениями).
5. Ступень 3 — bitmask DP. Начать с TSP / гамильтонова пути / минимального покрытия подмножеств. Полоса 1900–2100. Реальные «продукционные» задачи с маской — около 5–8 разных формулировок (TSP, ассайнмент, покрытие, перестановки), их полезно прорешать все.
6. Когда все три ступени крепко в руке — переходить к DP на дереве и DP с компонентами связности (это уже отдельная статья серии).

---

Итого

• Тема: одно семейство DP, в котором сложность растёт через расширение состояния.
• Траектория: $O(n)$ → $O(n \cdot W)$ → $O(n \cdot 2^n)$, с усложнением параметра от индекса к ресурсу к подмножеству.
• Ключевое умение: не запоминать рекуррентности конкретных задач, а видеть, какое состояние нужно под текущую формулировку. Когда чувствуешь параметр сразу — задача решается за 5 минут после прочтения условия.