Основы динамического программирования
Динамическое программирование — способ решения задач, в котором большая задача разбивается на небольшие перекрывающиеся подзадачи, а результаты уже решённых подзадач сохраняются. Главная схема такова: описать состояние, задать переходы, заполнить таблицу и при необходимости восстановить не только значение ответа, но и сам набор действий.
Идея динамического программирования
Метод применяют, когда задача обладает двумя свойствами: перекрывающимися подзадачами и оптимальной структурой. Перекрытие означает, что одни и те же промежуточные случаи возникают много раз. Оптимальная структура означает, что оптимальное решение всей задачи содержит оптимальные решения соответствующих частей.
Состояние динамического программирования — это набор параметров, однозначно описывающий подзадачу. Обычно оно записывается как \(dp[i]\), \(dp[i][j]\) или \(dp[mask]\). В состоянии должны присутствовать все данные, от которых зависит будущий ответ, но не лишние данные.
Если решение задачи оптимально, то после любого допустимого первого шага оставшаяся часть решения также должна быть оптимальной для получившегося состояния. Поэтому ответ можно получить из ответов меньших подзадач.
Перед составлением таблицы полезно отдельно изучить рекуррентное соотношение: оно показывает, как ответ текущего состояния выражается через уже известные состояния. В отличие от обычной рекурсии, динамическое программирование сохраняет результаты и не вычисляет одну подзадачу повторно.
Состояние, база и переход
Алгоритм удобно строить в четыре шага. Сначала определить, что означает каждый элемент таблицы. Затем задать базовые состояния — самые маленькие случаи. После этого вывести переход из предыдущих состояний и выбрать порядок вычисления. Последним определить, где находится искомый ответ.
- Сформулируйте смысл \(dp\): например, «максимальная сумма на первых \(i\) позициях».
- Запишите диапазоны индексов и начальные значения.
- Рассмотрите последний шаг решения и получите переход.
- Заполните таблицу в порядке, при котором все зависимости уже известны.
В общей формуле \(P(s)\) — множество предшествующих состояний, \(w(p\to s)\) — вклад перехода, а \(\operatorname{opt}\) означает \(\max\) для задачи на максимум или \(\min\) для задачи на минимум. Для подсчёта количества способов вместо максимума или минимума используют сумму.
Неверная инициализация часто портит всю таблицу. Для максимума недостижимые состояния обычно получают очень маленькое значение, например \(-\infty\); для минимума — \(+\infty\). Нулём можно инициализировать только действительно достижимые состояния.
Способы вычисления и сложность
Есть два основных варианта. При мемоизированной рекурсии состояние вычисляется при первом обращении и сохраняется. При табличном методе таблица заполняется снизу вверх в заранее выбранном порядке. На экзаменационных задачах табличный метод часто проще проверять: видны база, переход и границы индексов.
| Вариант | Как работает | Плюс |
|---|---|---|
| Мемоизация | Рекурсия + сохранение результатов | Рассматриваются только нужные состояния |
| Табуляция | Последовательное заполнение таблицы | Просто оценить порядок вычислений |
| Сжатие памяти | Хранятся только необходимые предыдущие строки или элементы | Меньше памяти |
Если состояний \(S\), а из каждого состояния рассматривается не более \(T\) переходов, время обычно равно \(O(S\cdot T)\), а память — \(O(S)\). Для одномерных задач полезны одномерные таблицы, для задач с двумя параметрами — двумерные таблицы.
Что должно быть верно для корректного состояния \(dp[i]\)?
Разобранный пример: максимальная сумма без соседних элементов
Дан массив \(a_1,a_2,\ldots,a_n\). Требуется выбрать несколько элементов без выбора соседних и получить максимальную сумму. Нужно определить ответ для каждого префикса массива.
Пусть \(dp[i]\) — максимальная сумма, которую можно получить, рассматривая первые \(i\) элементов. Для элемента \(a_i\) есть два варианта: не брать его или взять, тогда \(a_{i-1}\) брать нельзя.
Рассмотрим массив \([3,2,7,10,12]\). Таблица значений: \(dp[0]=0\), \(dp[1]=3\), \(dp[2]=3\), \(dp[3]=10\), \(dp[4]=13\), \(dp[5]=22\). Ответ равен \(22\): выбраны элементы \(3\), \(7\) и \(12\).
При заполнении слева направо каждый новый элемент требует только два предыдущих значения, поэтому память можно сократить до \(O(1)\). Но для восстановления выбранных элементов одной пары чисел обычно недостаточно: понадобятся таблица или дополнительные указатели.
Восстановление самого решения
Значение оптимума и само решение — разные результаты. Чтобы восстановить ответ, сохраняют предка состояния: индекс, из которого выполнен лучший переход. В задаче о непересекающихся элементах можно идти от \(i=n\) назад. Если \(dp[i]=dp[i-1]\), элемент \(i\) не выбран; иначе выбран \(i\), после чего переходят к \(i-2\).
Если требуется вывести последовательность действий, храните не только \(dp\), но и parent[i], take[i] или информацию о выбранном переходе. Восстановление обычно начинается из конечного состояния и движется к базовому.
В задачах на пути, рюкзак и последовательности восстановление может использовать отдельную таблицу решений. Подробный алгоритм удобно рассматривать на странице восстановление решения в динамическом программировании. Для игр состояние часто означает позицию, а переходы — возможные ходы; тогда полезны страницы позиция в игре и выигрышная позиция.
Частые ошибки
Типичные ошибки: состояние не содержит важный параметр; перепутаны \(i-1\) и \(i-2\); база не соответствует смыслу таблицы; недостижимые состояния инициализированы нулём; таблица заполняется до вычисления зависимостей; найдено максимальное значение, но не восстановлен требуемый объект. После вывода перехода проверьте его на маленьких массивах вручную.
Не следует бездумно хранить всю историю. Если две ситуации имеют одинаковое состояние и одинаковые возможные продолжения, их нужно объединить. Если переходов слишком много, после освоения базового метода переходят к оптимизации динамического программирования.
Быстрая проверка
Проверьте понимание
Главное
- Динамическое программирование хранит ответы перекрывающихся подзадач.
- Сначала определяют смысл состояния, затем базу, переходы и порядок вычисления.
- Переход выбирает минимум, максимум или сумму в зависимости от типа задачи.
- Сложность оценивают по числу состояний и переходов из каждого состояния.
- Для вывода самих действий сохраняют предков или решения переходов.