Динамическое программирование: основы

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

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

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

У метода есть два главных признака. Первый — задача разбивается на подзадачи. Второй — одни и те же подзадачи встречаются снова. Например, при вычислении чисел Фибоначчи значение F₃ понадобится и для F₄, и для F₅. Нет смысла считать его заново.

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

Четыре шага решения

Начинай не с кода, а с вопроса: «Что именно означает ответ для фрагмента задачи?» Это состояние. В задачах с массивом часто берут первые i элементов, а в задачах на сумму — текущую достигнутую сумму или количество предметов.

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

Удобная памятка выглядит так:

1. Состояние: dp[i] — ответ для фрагмента размера i
2. Переход: dp[i] = функция предыдущих состояний
3. База: значения для i = 0, 1 или других минимальных случаев
4. Ответ: нужный элемент таблицы, например dp[n]

Если состояние описано неточно, дальнейшая формула почти всегда приведёт к ошибке. Поэтому сначала проговори смысл dp[i] обычными словами.

Разобранный пример: лестница

Представь лестницу из n ступеней. За один ход можно подняться на одну или на две ступени. Сколько существует способов добраться до вершины? Это классический пример ДП.

Пусть dp[i] — число способов попасть на i-ю ступень. На последнюю ступень можно прийти с предыдущей ступени одним шагом или с предпоследней двумя шагами. Значит, складываем два варианта.

\( dp[i] = dp[i - 1] + dp[i - 2] \)
dp[0] = 1 — один способ остаться у основания
\( dp[1] = 1 \)
\( dp[2] = dp[1] + dp[0] = 2 \)
\( dp[3] = dp[2] + dp[1] = 3 \)
\( dp[4] = dp[3] + dp[2] = 5 \)

Почему dp[0] равно 1, а не 0? Пустой путь нужен как исходная точка для варианта с двумя шагами. Для четырёх ступеней получаем 5 способов: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1 и 2+2.

В программе можно хранить всю таблицу или только два последних значения: переход использует лишь dp[i − 1] и dp[i − 2]. Это уменьшает память, но полная таблица удобнее для восстановления самого пути.

Таблица, рекурсия и восстановление ответа

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

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

Подход	Как работает	Когда удобен
Снизу вверх	Заполняет состояния по порядку	Простой переход и известный размер задачи
Сверху вниз	Рекурсивно решает нужные состояния	Много недостижимых или ненужных состояний

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

Время работы часто равно количеству состояний, умноженному на число переходов. Если для каждого из n состояний проверяются два варианта, сложность обычно составляет O(n), а не O(2ⁿ).

Типичные ошибки и проверка

Первая ошибка — перепутать смысл состояния. Например, dp[i] может означать «количество способов попасть на i», а может — «лучший результат среди первых i элементов». Это разные задачи и разные переходы.

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

Третья ошибка — перепутать «минимум» и «максимум», особенно в задачах о стоимости пути. Четвёртая — выйти за границы массива при обращении к i − 1 или i − 2. Начинай цикл с первого индекса, для которого переход корректен.

Проверяй решение на маленьких случаях вручную: n = 0, n = 1, n = 2. Сравнивай таблицу с полным перебором, если размер настолько мал, что все варианты можно выписать.

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

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

Главный навык — не запоминать готовые формулы, а правильно отвечать на вопрос: «Что означает этот элемент таблицы?» После этого переход часто становится естественным. В задачах на пути, последовательности и выбор не бойся сначала сделать небольшую таблицу на бумаге.

Чтобы закрепить тему, зарегистрируйся и реши 5 заданий бесплатно в личном кабинете. Начни с лестницы, затем переходи к задачам на минимальную стоимость и восстановление ответа. Если готовишься к экзамену, полезные направления собраны на страницах ОГЭ и ЕГЭ.