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

Двумерное динамическое программирование

Как решать задачи с двумя изменяющимися параметрами

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

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

Двумерное динамическое программирование«Динамическое» означает постепенное построение ответа, а «двумерное» — наличие двух индексов состояния.

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

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

Общая схема

\[dp[i][j] = F\bigl(dp[i-1][j],\ dp[i][j-1],\ dp[i-1][j-1],\ a_{i,j}\bigr)\]

Функция \(F\) зависит от конкретной задачи: она может выбирать минимум или максимум, складывать количество способов либо проверять возможность перехода. Важно заполнить таблицу в таком порядке, чтобы все значения, нужные для \(dp[i][j]\), уже были известны.

№

Пример: пути по сетке

Пусть из клетки можно идти только вправо или вниз. Если \(dp[i][j]\) — число способов попасть в клетку \((i,j)\), то для внутренней клетки \(dp[i][j]=dp[i-1][j]+dp[i][j-1]\). В первой строке и первом столбце обычно записывают единицы, если препятствий нет. Ответ находится в правой нижней клетке.

Не путайте размерность и размер таблицы

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

Проверьте себя

Что обычно означает \(dp[i][j]\) в двумерном динамическом программировании?

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

Главное

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