Задания № 18, 22 · ЕГЭ

Состояние динамического программирования

Как описать подзадачу так, чтобы динамическое программирование работало правильно

2 мин чтенияСложность: Обновлено 29 сентября 2026

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

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

Состояние динамического программирования — это минимальный набор параметров подзадачи, по которому однозначно определяется её значение и возможные дальнейшие действия. Обычно состояние записывают как индекс или набор индексов таблицы: \(dp[i]\), \(dp[i][j]\) и так далее.

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

\[dp[s] = \text{ответ для подзадачи, описанной состоянием } s\]

№

Пример: рюкзак

Пусть нужно выбрать предметы с ограничением по массе. Состояние \(dp[i][w]\) может означать максимальную стоимость, которую можно получить, используя первые \(i\) предметов при вместимости \(w\). Здесь \(i\) и \(w\) полностью описывают подзадачу: предыдущий порядок выбора предметов уже не важен. Если добавить в состояние ещё и список выбранных предметов, таблица станет избыточной — для значения достаточно \(i\) и \(w\).

Проверь себя

Какое состояние подходит для поиска максимальной суммы на пути из верхнего левого угла таблицы в клетку \((i,j)\), если двигаться можно только вправо и вниз?

Не путайте состояние и переход

Состояние описывает, для какой подзадачи ищется ответ. Переход описывает, как получить этот ответ из уже известных состояний. Например, \(dp[i][j]\) — состояние, а выбор максимума из соседних клеток — часть перехода динамического программирования. Само состояние обычно формулируют до записи перехода, опираясь на рекуррентное соотношение.

Хорошая проверка состояния: можно ли по его параметрам однозначно восстановить границы подзадачи, а затем перечислить все варианты последнего действия? Если нет, параметров не хватает. Если несколько записей описывают одну и ту же подзадачу, состояние содержит лишние данные. Введение в общий метод дано в статье основы динамического программирования.

Главное за минуту

Главное

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