Как найти состояние и переход: рецепт из пяти шагов

Коротко

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

Если ты умеешь получить состояние из наивной рекурсии и оценить цену по формуле «состояния × переход», листай до «Теперь сам».

Как думаешь, откуда берётся таблица

Со стороны динамика выглядит как фокус: откуда-то появляется двумерный массив, в нём считаются непонятные числа, и в правом нижнем углу оказывается ответ. Угадывать таблицу действительно бесполезно.

Но её и не угадывают. Таблица - это ПОСЛЕДНИЙ шаг, а первый - обычная рекурсия, которую можно написать не думая. Вопрос: что именно надо увидеть в этой рекурсии, чтобы таблица появилась сама?

На что это похоже

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

Механизм: пять шагов

ШАГ 1. НАПИСАТЬ РЕКУРСИЮ В ЛОБ - в ней и прячется ПЕРЕХОД
    «ответ для всей задачи» через «ответ для меньшей»,
    не думая о скорости. Можно даже не запускать

ШАГ 2. ВЫПИСАТЬ ПАРАМЕТРЫ = СОСТОЯНИЕ
    от чего реально зависит результат вызова?
    всё, что меняется между вызовами и влияет на ответ - параметр

ШАГ 3. НАЙТИ БАЗУ
    при каких параметрах ответ известен без рекурсии

ШАГ 4. ОЦЕНИТЬ ЦЕНУ
    число состояний × цена одного перехода
    не влезает - вернуться к шагу 2 и сжать состояние

ШАГ 5. ВЫБРАТЬ ПОРЯДОК
    мемоизация: порядок получается сам
    таблица: считать в порядке, при котором нужное уже готово

ЧТО БЕРУТ ЗА ПАРАМЕТРЫ - ТИПОВЫЕ ОТВЕТЫ

«сколько элементов уже рассмотрено»        один индекс
«сколько ресурса осталось»                 остаток места, денег, времени
«где я нахожусь»                           номер вершины, клетка
«что из чего»                              два индекса (две строки, две стопки)
«в каком режиме»                           маленький флаг: держу акцию или нет
«какое подмножество использовано»          маска - дорого, только при n <= 20

СЖАТИЕ СОСТОЯНИЯ - ГЛАВНЫЙ ПРИЁМ ОПТИМИЗАЦИИ

вопрос: влияет ли этот параметр на БУДУЩЕЕ?
    не влияет → выкинуть
    влияет только через «да/нет» → заменить флагом
    влияет только последними k значениями → хранить k, а не всё

Правило

Решение задачи на динамику - это четыре ответа: состояние, переход, база, порядок. Получают их из наивной рекурсии: параметрами состояния становится всё, что меняется между вызовами и влияет на результат. Цена считается сразу - ЧИСЛО СОСТОЯНИЙ умножить на цену ОДНОГО ПЕРЕХОДА, - и если она велика, состояние сжимают: выкидывают параметры, не влияющие на будущее, заменяют их флагами или хранят только последние значения. Лишний параметр умножает цену, недостающий делает ответ неверным, причём молча. Порядок вычисления либо получается сам (мемоизация), либо выбирается так, чтобы к моменту счёта клетки всё нужное было готово.

Разбор: пять шагов на задаче про размен монет

Задача: набрать сумму S минимальным числом монет из набора c₁ ... cₖ, монеты можно брать сколько угодно раз. В разделе 14 мы выяснили, что жадность здесь неверна (на монетах 1, 3, 4 и сумме 6 она даёт три монеты вместо двух). Пройдём рецепт.

ШАГ 1. РЕКУРСИЯ В ЛОБ
    чтобы набрать сумму s, возьмём какую-то монету c и наберём s − c
    f(s) = 1 + min( f(s − c) для всех монет c <= s )

ШАГ 2. СОСТОЯНИЕ
    от чего зависит ответ? только от ОСТАВШЕЙСЯ СУММЫ.
    не от того, какие монеты уже взяты, и не от их порядка
    ⇒ состояние - одно число s, состояний S + 1

ШАГ 3. БАЗА
    f(0) = 0: пустую сумму набираем нулём монет

ШАГ 4. ЦЕНА
    состояний S + 1, в каждом перебираем k монет ⇒ Θ(S·k)
    при S = 10000 и k = 5 это 50 тысяч операций - годится

ШАГ 5. ПОРЯДОК
    f(s) зависит от МЕНЬШИХ s ⇒ считаем по возрастанию суммы

Переход готов, таблица одномерная:

# S - нужная сумма, coins - список номиналов, например S = 6, coins = [1, 3, 4]
INF = 1000000000
dp = [INF] * (S + 1)       # dp[s] - минимум монет на сумму s
dp[0] = 0                  # база: пустую сумму набираем нулём монет

s = 1
while s <= S:
    for c in coins:
        if c <= s and dp[s - c] + 1 < dp[s]:
            dp[s] = dp[s - c] + 1
    s = s + 1
# dp[S] - ответ; если там осталось INF, сумму набрать нельзя

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

проверка на монетах 1, 3, 4:
dp[0]=0  dp[1]=1  dp[2]=2  dp[3]=1  dp[4]=1  dp[5]=2  dp[6]=2
                                                         ↑
                                    жадность даёт 3, динамика - 2 (3+3)

Разбор: как лишний параметр умножает цену

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

СОСТОЯНИЕ ПРАВИЛЬНОЕ:  dp[i]            n состояний, переход O(1)  ⇒  Θ(n)

СОСТОЯНИЕ С ЛИШНИМ ПАРАМЕТРОМ: dp[i][s] - «на первых i элементах набрали
сумму ровно s». Состояний n × (сумма всех) ⇒ при n = 1000 и суммах до 10⁶
это 10⁹ клеток. Ответ тот же, цена в миллион раз выше

А вот обратный случай, где параметр добавить НАДО: та же задача, но требуется выбрать ровно k элементов. Тогда dp[i][k] - и это не роскошь: без второго параметра ответ будет неверным, потому что оптимум без ограничения не годится как часть ответа с ограничением.

правило большого пальца:
    параметр нужен ⇔ без него РАЗНЫЕ подзадачи попадают в одну клетку
    проверяется вопросом: «две ситуации с одинаковыми параметрами -
    у них точно одинаковое будущее?»

Третий, самый приятный случай - параметр, который влияет на будущее, но лишь последними значениями. У Фибоначчи состояние формально n, но для шага нужны только два предыдущих ответа, поэтому таблица сворачивается в две переменные. Это и есть сжатие по памяти, которому посвящена третья глава раздела.

Что ломается без этого

Первое: начинать с таблицы. Таблицу не угадывают - её выводят из рекурсии, и попытка «придумать размерности» заканчивается либо неверным переходом, либо лишним измерением. Второе: взять состояние «по аналогии» с похожей задачей: у похожих задач состояния часто отличаются на один параметр, и именно он и решает. Третье: забыть базу. Рекурсия тогда уходит в минус - или, в табличной версии, читает мусор из неинициализированной клетки. Четвёртое: не посчитать цену ДО написания кода: Θ(n·C) при вместимости в миллион - это сотни миллионов клеток, и выяснять это лучше на бумаге, а не после написания кода. Пятое: взять за «бесконечность» ноль или −1 в задаче на минимум: сравнение dp[s−c] + 1 < dp[s] начнёт срабатывать не там, где надо. Шестое: считать состояния в произвольном порядке - про это отдельная глава, но правило простое: клетка считается только после всех, от которых зависит.

Зачем это в работе

Рецепт из пяти шагов - это то, что реально воспроизводят на собеседовании и в работе, потому что он не требует помнить конкретные задачи. Любая новая задача разбирается одинаково: написать рекурсию, выписать параметры, оценить цену. Больше половины практической пользы - в шаге 4: он отвечает на вопрос «а влезет ли» до того, как написана строчка кода. У Θ(n·C) для рюкзака буква C - это вместимость, и при вместимости в миллион строк задача «влезает по формуле» и не влезает по времени; такие вещи видно сразу. И ещё одно: шаг 2 - это тот самый навык, который отличает «я помню решение рюкзака» от «я умею решать задачи на динамику». Первое проверяется вопросом «а если предметов можно брать по многу раз?», и тут выясняется, у кого состояние выведено, а у кого выучено.

Теперь сам

Задача: робот стоит в левом верхнем углу таблицы n × m и может идти только вправо или вниз. Некоторые клетки заняты. Сколько у него путей в правый нижний угол? Пройди рецепт: состояние, переход, база, цена.

Ответ.

ШАГ 1. рекурсия: в клетку (i, j) можно прийти сверху или слева
       f(i, j) = f(i−1, j) + f(i, j−1)

ШАГ 2. состояние: клетка, то есть пара (i, j). Состояний n·m.
       (границы: f(i, j) = 0, если i или j вышли за таблицу -
        проще всего завести нулевую рамку, чтобы не писать проверок)
       Путь, которым робот пришёл, на будущее не влияет - значит в состояние
       его не берём

ШАГ 3. база: f(1, 1) = 1; занятая клетка - ноль путей

ШАГ 4. цена: n·m состояний × переход O(1) ⇒ Θ(n·m)

ШАГ 5. порядок: f(i, j) зависит от меньших i и j ⇒ по строкам сверху вниз,
       внутри строки слева направо

пример: 3 × 3, занята середина (2,2)

1 1 1
1 0 1
1 1 2      ответ: 2 пути

Теперь добавь условие: у робота есть t «прыжков», каждый позволяет пройти занятую клетку. Что изменится? Состояние станет тройкой (i, j, остаток прыжков), состояний n·m·(t+1), цена Θ(n·m·t). Это ровно тот случай из второго разбора, когда параметр добавить НАДО: без него две ситуации в одной клетке - «пришёл с двумя прыжками» и «пришёл без прыжков» - имеют разное будущее.

Главное

Решение задачи на динамику - четыре ответа: состояние, переход, база, порядок; получают их из наивной рекурсии, а не из догадки о таблице. Состояние - это минимум сведений о прошлом, нужный для будущего: всё, что меняется между вызовами и влияет на результат. Цена = число состояний × цена перехода, и считать её надо ДО написания кода. Параметр нужен тогда и только тогда, когда без него две ситуации с разным будущим попадают в одну клетку; лишний параметр умножает цену (у «без двух соседних» второй параметр превращает Θ(n) в Θ(n·сумма)), недостающий делает ответ неверным (тот же пример с условием «ровно k элементов»). У размена монет состояние - одно число, остаток суммы: ни список взятых монет, ни их порядок на будущее не влияют, отсюда Θ(S·k) и правильный ответ там, где жадность ошибается.