§ 45. Динамическое программирование

Определения и обозначения

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

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

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

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

Как это устроено

Сначала выясняют, можно ли разбить задачу на повторяющиеся подзадачи. Для этого ищут способ получить ответ для большого случая из ответов для меньших случаев. Например, число способов попасть на ступеньку зависит от способов попасть на две предыдущие. Метод особенно полезен, если одни и те же меньшие случаи возникают неоднократно: их ответы можно вычислить один раз и сохранить.

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

Рекуррентное соотношение выводят, перечисляя варианты, которыми можно получить текущее состояние. Если нужно посчитать количество способов, ответы для разных вариантов складывают, потому что каждый вариант даёт отдельные способы. Если требуется минимум или максимум, среди подходящих вариантов выбирают наименьшую или наибольшую стоимость. Так формула отражает именно условие задачи, а не просто удобный арифметический приём.

Для запуска вычислений задают начальные значения — ответы для самых простых подзадач. Они известны непосредственно из условия или очевидны по смыслу задачи; например, способ попасть на стартовую позицию часто ровно один. Если начальный ответ выбран неверно, ошибка перейдёт в состояния, рассчитанные из него. После этого таблицу заполняют от простых состояний к сложным, чтобы все нужные значения уже были готовы.

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

Элементы решения задачи методом динамического программирования

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

Разбор задач

Задача 1. Подъём по ступенькам. Нужно найти число способов подняться на n-ю ступеньку, если за один ход можно пройти одну или две ступени. Состоянием выберем номер ступеньки, а f(n) обозначим число способов попасть на неё. Последний ход на ступеньку n мог быть сделан с n − 1 или с n − 2.

1. Запишем зависимость: f(n) = f(n − 1) + f(n − 2), потому что способы из двух групп различаются последним ходом.
2. Зададим начало: f(0) = 1 — один способ остаться у основания, f(1) = 1 — один шаг на первую ступеньку.
3. Будем считать значения по возрастанию номера: каждый раз два нужных предыдущих ответа уже известны.

Ответ: число способов подняться на n-ю ступеньку равно f(n), полученному по этой формуле. Например, f(2) = 2, а f(3) = 3. Начальные значения здесь описывают условие, что подъём может начинаться с основания.

Задача 2. Минимальный путь в таблице. В клетках стоят числа; требуется пройти из левого верхнего угла в правый нижний, двигаясь только вправо или вниз, и получить наименьшую сумму чисел посещённых клеток. Пусть a[i,j] — число в клетке строки i и столбца j, а d[i,j] — минимальная стоимость пути до неё. Войти в клетку можно только сверху или слева, поэтому других вариантов перехода нет.

1. Для стартовой клетки положим d[1,1] = a[1,1], так как путь пока состоит только из неё.
2. Для остальных клеток используем d[i,j] = a[i,j] + min(d[i − 1,j], d[i,j − 1]), учитывая только существующего соседа на границе.
3. Заполняем таблицу слева направо и сверху вниз: к моменту расчёта клетки её верхнее и левое значения уже известны.

Ответ: искомая минимальная сумма находится в d[r,c], где r и c — число строк и столбцов таблицы. Число текущей клетки прибавляется к меньшей из стоимостей подхода к ней. Такой выбор верен, потому что любой допустимый путь обязан прийти сверху либо слева.

Задача 3. Рюкзак. Есть предметы с массами и ценностями; вместимость рюкзака ограничена, а каждый предмет разрешено взять не более одного раза. Нужно найти наибольшую суммарную ценность среди наборов, масса которых не превышает вместимость. Пусть dp[i,w] — наибольшая ценность при рассмотрении первых i предметов и вместимости w.

1. Если i-й предмет тяжелее w, взять его нельзя, поэтому dp[i,w] = dp[i − 1,w].
2. Если предмет помещается, сравним не брать его с вариантом взять: dp[i,w] = max(dp[i − 1,w], dp[i − 1,w − mᵢ] + vᵢ), где mᵢ и vᵢ — его масса и ценность.
3. Положим dp[0,w] = 0: без предметов ценность равна нулю. Заполняем строки по числу рассмотренных предметов, используя предыдущую строку, чтобы каждый предмет учитывался не более одного раза.

Ответ: максимальная ценность равна dp[N,W], где N — число предметов, а W — вместимость рюкзака. В каждом состоянии проверены оба допустимых решения по текущему предмету. Если требуется не только ценность, но и сам набор, можно дополнительно восстановить выбор по таблице.

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

Состояние может не учитывать параметр, от которого зависит ответ, например вместимость рюкзака в задаче о выборе предметов. Тогда одной ячейке таблицы придётся соответствовать нескольким разным подзадачам, и формула даст неверный результат. Ошибку допускают, когда выбирают состояние слишком поспешно; проверьте, можно ли по его параметрам однозначно вычислить следующий ответ.

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

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

Динамическое программирование не означает, что обязательно нужно писать рекурсивную функцию. Такое заблуждение возникает из-за того, что формулы связывают текущие ответы с предыдущими. На деле таблицу можно заполнить циклами; проверка простая — если вычисление идёт по порядку и ответы сохраняются, рекурсивные вызовы не обязательны.

Связь с другими темами

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

Что запомнить

• Сначала определяют, какой ответ хранит каждое состояние.
• Рекуррентное соотношение выводят из условий задачи, а не подбирают наугад.
• Начальные значения задают до вычисления остальных состояний.
• Таблицу заполняют так, чтобы необходимые предыдущие ответы уже были известны.
• Сохранение ответов позволяет не решать одну и ту же подзадачу многократно.
• Итог задачи нужно связать с конкретными ячейками или состояниями таблицы.