Одномерная динамика

Самый частый вид динамики: состояние — номер элемента или позиции, ответ — одно число на позицию.

Кузнечик

Кузнечик прыгает по клеткам от 0 к $n$, за прыжок продвигается на 1, 2, ..., $k$ клеток. Сколько маршрутов?

То же, что лестница, только слагаемых $k$:

vector<long long> d(n + 1, 0);
d[0] = 1;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= k && j <= i; j++)
        d[i] += d[i - j];

Проверено: для $k$ от 1 до 4 и $n$ от 0 до 18 совпадает с перебором. Для $n = 30$, $k = 3$ ответ 53 798 080.

Условие j <= i — не украшение. Без него будет обращение к d[-1], а это неопределённое поведение: программа может выдать мусор, а может тихо работать до тех пор, пока её не запустят на сервере с другой компоновкой памяти.

Сложность $O(nk)$. При больших $k$ внутренний цикл убирается префиксными суммами: сумма $k$ подряд идущих значений считается за $O(1)$.

Два направления перехода

Один и тот же переход записывается двумя способами, и путать их не стоит.

Назад («притянуть»): стоя в состоянии $i$, смотрим, откуда в него можно было попасть.

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= k && j <= i; j++)
        d[i] += d[i - j];               // забираем у предков

Вперёд («толкнуть»): стоя в готовом состоянии $i$, раздаём его значение тем, куда из него можно уйти.

for (int i = 0; i <= n; i++)
    for (int j = 1; j <= k && i + j <= n; j++)
        d[i + j] += d[i];               // отдаём потомкам

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

• назад удобнее, когда легко перечислить, откуда пришли (типично для «сколькими способами дойти»);
• вперёд удобнее, когда легко перечислить, куда уйдём, а обратные переходы описываются коряво. Так бывает в задачах про монеты, ходы фигур, состояния автомата.

Важное отличие на практике: при переходе вперёд значение $d[i]$ должно быть окончательным в момент, когда мы его раздаём. Если из $i$ можно попасть в $i$ же (переход нулевой длины), схема ломается — а при переходе назад такой переход просто зациклит формулу, и это заметно сразу.

Когда одного числа мало

Добавим к лестнице условие: нельзя два раза подряд шагать на две ступени.

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

$d[i][0]$ — способов дойти до $i$, если последний шаг был коротким; $d[i][1]$ — если длинным.

d[0][0] = 1;                            // старт считаем «коротким» шагом
for (int i = 1; i <= n; i++) {
    d[i][0] = d[i - 1][0] + d[i - 1][1];        // короткий шаг разрешён всегда
    if (i >= 2) d[i][1] = d[i - 2][0];          // длинный — только после короткого
}
// ответ: d[n][0] + d[n][1]

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

Обратная сторона правила тоже верна и полезнее: если признак не влияет на будущее, держать его в состоянии нельзя — таблица распухнет, а решение не станет вернее.

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

задача	состояние	переход
число способов дойти	$d[i]$ — способов до $i$	сумма по допустимым шагам
минимальная стоимость пути	$d[i]$ — минимум до $i$	минимум по шагам плюс цена
максимальная сумма без двух соседей	$d[i]$ — максимум на префиксе	$\max(d[i-1],\ d[i-2] + a_i)$
минимум монет на сумму	$d[s]$ — монет на сумму $s$	$\min$ по номиналам
можно ли набрать сумму	$d[s]$ — булев	«или» по номиналам

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

Родственники, которые не выглядят динамикой

Отрезок с максимальной суммой — это одномерная динамика: $d[i]$ — лучшая сумма отрезка, кончающегося в $i$, переход $d[i] = \max(a_i,\ d[i-1] + a_i)$. Алгоритм Кадане обычно рассказывают отдельно, но ничего нового в нём нет.

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