Динамическое программирование: база: разбор для ЕГЭ

Принцип динамического программирования: как перестать считать лишнее

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

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

Любая задача на ДП держится на трёх составляющих:

1. Состояние — параметр или набор параметров, который однозначно описывает текущую ситуацию (например, число на экране калькулятора или координаты клетки робота).

2. Базовый случай — начальная точка, для которой ответ очевиден без вычислений (например, чтобы попасть из числа 1 в число 1, существует ровно 1 способ).

3. Переход (рекуррентная формула) — строгое математическое правило, связывающее текущее состояние с предыдущими шагами.

Одномерное ДП: вычисление количества программ

Классический пример одномерной динамики в ЕГЭ — задача о подсчёте количества программ исполнителя (линия заданий № 23). Пусть исполнитель преобразует натуральное число с помощью двух команд: «прибавить 1» и «умножить на 2». Требуется узнать, сколько различных программ существует для получения числа 8 из исходного числа 1.

Определим массив K[N], где элемент с индексом i хранит количество способов добраться из стартовой единицы в число i. Базовое значение: K[1] = 1. Для всех остальных чисел переход зависит от того, какими командами мы могли в них оказаться:

K[i] = K[i - 1] (если i не делится на 2)
K[i] = K[i - 1] + K[i2] (если i делится на 2 без остатка)

Заполним массив шаг за шагом:

\( K[1] = 1 \)
K[2] = K[1] + K[1] = 1 + 1 = 2 (команды: 1+1 или 1·2)
K[3] = K[2] = 2 (только команда +1)
\( K[4] = K[3] + K[2] = 2 + 2 = 4 \)
\( K[5] = K[4] = 4 \)
\( K[6] = K[5] + K[3] = 4 + 2 = 6 \)
\( K[7] = K[6] = 6 \)
\( K[8] = K[7] + K[4] = 6 + 4 = 10 \)

Итого получаем ровно 10 уникальных программ. Чтобы отработать навык составления одномерных переходов на свежих прототипах, загляни в личный кабинет тренажёра Просто Урок.

Двумерная динамика: сетки, роботы и сбор наград

В задачах на таблицы (например, задача № 18 с роботом) состояние описывается двумя координатами — номером строки r и номером столбца c. Робот стартует в левом верхнем углу и может перемещаться только вправо или вниз, собирая монеты из каждой посещенной ячейки. Нам нужно найти максимальную сумму, которую он может собрать.

Пусть Cost[r][c] — стоимость монеты в ячейке, а DP[r][c] — максимальная сумма на пути из старта в клетку (r, c). В клетку (r, c) робот может прийти только сверху из (r - 1, c) или слева из (r, c - 1). Формула перехода выглядит так:

\( DP[r][c] = Cost[r][c] + max(DP[r - 1][c], DP[r][c - 1]) \)

Рассмотрим небольшое поле 3×3 с исходными значениями монет и результирующей таблицей ДП:

Исходное поле монет	Таблица накопленных сумм (DP)
1  |  4  |  2 3  |  1  |  5 2  |  6  |  1	1  |  5  |  7 4  |  6  |  12 6  |  12  |  13

Пошаговый разбор задачи с обязательными и запрещенными числами

Экзаменационные задания часто усложняют дополнительными ограничениями: траектория обязательно должна содержать число A и не должна проходить через число B. Разберём такой пример.

Условие: Исполнитель имеет команды «+1», «+2» и «·2». Сколько программ существует для перехода из 2 в 14, если траектория обязательно содержит 6 и не содержит 10?

Разобьем решение на два независимых этапа: путь из 2 в 6 и путь из 6 в 14. Общее количество путей будет равно произведению результатов этих двух этапов.

Этап 1: из 2 в 6
\( K[2] = 1 \)
K[3] = K[2] = 1 (команда +1)
K[4] = K[3] + K[2] + K[2] = 1 + 1 + 1 = 3 (команды +1, +2, ·2)
\( K[5] = K[4] + K[3] = 3 + 1 = 4 \)
\( K[6] = K[5] + K[4] + K[3] = 4 + 3 + 1 = 8 \)

Для второго этапа стартуем из точки 6 с базовым значением K[6] = 1. Запрещённую точку 10 исключаем — приравниваем K[10] = 0.

Этап 2: из 6 в 14
\( K[6] = 1 \)
\( K[7] = K[6] = 1 \)
K[8] = K[7] + K[6] = 1 + 1 = 2 (команда ·2 не даёт вклад, так как 8 / 2 = 4 < 6)
\( K[9] = K[8] + K[7] = 2 + 1 = 3 \)
K[10] = 0 (запрещённая вершина)
\( K[11] = K[10] + K[9] = 0 + 3 = 3 \)
\( K[12] = K[11] + K[10] + K[6] = 3 + 0 + 1 = 4 \)
\( K[13] = K[12] + K[11] = 4 + 3 = 7 \)
\( K[14] = K[13] + K[12] + K[7] = 7 + 4 + 1 = 12 \)

Итоговый ответ: K(2 → 6) · K(6 → 14) = 8 · 12 = 96

Реализация на Python: списки и рекурсия

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

Посмотрим на логику вычисления через функцию с ветвлением, которую легко написать за полминуты:

def f(current, target):
\(     if current > target or current == 10: \)
        return 0
\(     if current == target: \)
        return 1
\(     return f(current + 1, target) + f(current + 2, target) + f(current * 2, target) \)

print(f(2, 6) * f(6, 14)) # Выведет 96

В коде явно прописаны два базовых условия остановки: выход за пределы или попадание в запрещённую точку возвращает 0, а достижение целевого числа возвращает 1. Проверить работу своего скрипта на разных тестовых наборах можно бесплатно в системе практики Просто Урок.

Что запомнить: шпаргалка и следующий шаг

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

1. Определи состояние: одно число (одномерный массив) или пара координат (двумерная матрица).

2. Задай базу: всегда устанавливай значение 1 для стартовой позиции и 0 для запрещённых клеток.

3. Разбивай сложный маршрут: если есть обязательная точка, решай задачу как произведение независимых отрезков: N(A → B) · N(B → C).

4. Проверяй делимость: для операций деления и умножения всегда проверяй границы диапазона и целочисленный остаток.

Закрепи понимание на практике: прямо сейчас перейди в личный кабинет Просто Урок и реши 5 тренировочных задач по динамическому программированию без подсказок.