Как придумать динамику

Разобранные приёмы бесполезны, пока непонятно, какой из них применить. Эта статья — про то, как выбирать.

Порядок действий

1. Написать перебор. Не для сдачи, а для понимания: что перебирается и в каком порядке принимаются решения. Почти всякая динамика — это перебор, в котором одинаковые подзадачи посчитаны один раз.

2. Найти повторы. Посмотрите на рекурсивные вызовы: какие аргументы у них меняются, а какие можно выбросить. Оставшийся набор аргументов и есть состояние.

3. Проверить, достаточно ли состояния. Вопрос звучит так: если мне сообщат только состояние, смогу ли я досчитать ответ, не зная, как я в него попал? Если нет — чего-то не хватает, добавляйте.

4. Посчитать размер. Число состояний умножить на стоимость перехода. Не влезает в лимит — состояние надо менять, а не оптимизировать константу.

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

6. Сравнить с перебором на маленьких тестах. Стресс-тест уже почти написан — перебор из первого пункта.

Первый пункт пропускают чаще всего, и зря: без него состояние придумывается угадыванием.

Каталог: что подсказывает условие

в условии	состояние
последовательность, решение на каждом шаге	номер элемента, одномерная
«нельзя два одинаковых подряд»	номер + последний выбор
набрать сумму / вес / бюджет	номер + сколько потрачено (рюкзак)
две строки или два массива	пара префиксов (НОП)
склейка или разрезание подряд идущих	пара границ (подотрезки)
таблица, ходы вправо-вниз	пара координат (таблица)
двое ходят по очереди	позиция игры (исход)
«сколько чисел до $N$ обладают свойством»	позиция цифры (цифры)
$n \le 20$, речь о подмножествах	маска
дерево	вершина (динамика на дереве)
зависимости без циклов	вершина ациклического графа (ДАГ)

Каталог: что подсказывают ограничения

ограничение	во что целятся
$n \le 20$	$2^n$ — перебор подмножеств или маски
$n \le 40$	$2^{n/2}$ — встреча посередине
$n \le 500$	$n^3$ — подотрезки
$n \le 5000$	$n^2$ — пары индексов, квадратичная НВП
$n \le 10^5$, $W \le 10^3$	$nW$ — рюкзак или что-то похожее
$n \le 10^5$	$n \log n$ — динамика с бинарным поиском или структурой
$n \le 10^{18}$	цифры, матричное возведение в степень или формула

Таблица не догма, но выбор она сужает сильно. Полезно смотреть и на второе ограничение: если рядом с $n \le 100$ стоит $S \le 10^4$, их произведение $10^6$ — почти наверняка размер таблицы.

Подробнее про оценки — в статье «Оценка сложности».

Если состояние не придумывается

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

Поменяйте местами известное и искомое. Классический ход: вместо «какой длины ответ при таких затратах» считать «каких минимальных затрат стоит ответ такой длины». Так НВП ускоряется до $n \log n$, так же решаются задачи, где ответ мал, а параметр велик.

Смените направление. Не «сколькими способами дойти сюда», а «сколькими способами дойти отсюда до конца». Иногда одно выписывается, а другое нет.

Считайте не ответ, а количество или достижимость. Булева таблица «можно ли» часто проще числовой «сколько стоит», а задача сводится к перебору ответа поверх неё.

Зафиксируйте лишнее. Если мешает один параметр — переберите его снаружи. Динамика внутри станет проще, а общая сложность вырастет всего в число вариантов.

Чек-лист, когда ответ неверный

По убыванию частоты:

1. База. Проверьте $n = 0$ и $n = 1$ руками.
2. Порядок обсчёта. Выпишите индексы в переходе и убедитесь, что все они уже готовы. Для рюкзака — проверьте направление внутреннего цикла.
3. Недостижимые состояния. Помечены бесконечностью, а не нулём? Прибавление к бесконечности не переполняет тип?
4. Тип. Переполнение в подсчёте количеств наступает быстро: у лестницы ответ перестаёт влезать в int уже на 46 ступенях, в long long — на 92.
5. Ответ берётся не оттуда. У НВП это максимум по таблице, а не последняя ячейка. У задач «на префиксе» — наоборот.
6. Состояния не хватает. Проверьте вопросом из пункта 3 порядка действий. Если ответ зависит от того, как вы пришли, — состояние неполное.

Первые пять пунктов проверяются за пять минут. Шестой означает, что решение надо переделывать, — поэтому и стоит последним.

Что читать дальше

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

Ленивая запись, стек вызовов и цена рекурсии — в статье «Мемоизация».