Динамическое программирование на ЕГЭ по информатике — задания 18, 23 и 27 одним методом
Динамическое программирование на ЕГЭ по информатике без академизма: подзадача, база, переход, порядок. Три проверенных шаблона на Python для заданий 18, 23 и 27 и план на 5 дней.
Динамическое программирование на ЕГЭ по информатике прячется минимум за тремя заданиями — 18, 23 и 27 — и во всех трёх работает один приём: назвать подзадачу, задать базу и переход, заполнить таблицу в правильном порядке. Здесь без академизма: как понять динамическое программирование за один вечер, как увидеть его в условии, три шаблона на Python с проверенным кодом и план тренировки на 5 дней. Для тех, кто уже пишет циклы и списки, но при слове «динамика» ещё напрягается.
Как понять динамическое программирование: четыре слова
ДП — не олимпиадная тема, а способ считать. Вместо того чтобы искать ответ на всю задачу целиком, ты считаешь ответы на маленькие подзадачи и собираешь из них большой. Любое ДП описывается четырьмя словами.
- Подзадача — что именно лежит в ячейке таблицы. «Сколько программ приводят в число n», «максимальная сумма пути до клетки (i, j)». Если не можешь сказать это одной фразой — решение ещё не готово.
- База — ячейки, значения которых известны без вычислений. Старт:
dp[A] = 1,dp[0][0] = table[0][0]. - Переход — формула, выражающая ячейку через уже посчитанные:
dp[n] = dp[n-1] + dp[n//2]. - Порядок заполнения — такой, чтобы к моменту вычисления ячейки всё, на что она ссылается, уже стояло в таблице. Обычно — от меньших индексов к большим, по строкам сверху вниз и слева направо.
Переход — это единственное место, где нужно думать. Остальное — аккуратность. На экзамене ДП-задача превращается в 8–15 строк Python, и главная работа — правильно назвать подзадачу.
Перебор, рекурсия с мемоизацией и ДП-таблица
Три способа посчитать одно и то же — «сколько программ переводят 1 в n командами +1 и ×2».
Перебор — рекурсивно пробуем все программы: из числа x идём в x+1 и в 2x, дошли до n — плюс один. Работает, пока ответов сотни. На длинных диапазонах количество вызовов растёт взрывообразно, и программа не успевает.
Рекурсия с мемоизацией — идём «сверху вниз»: чтобы узнать ways(n), спрашиваем ways(n−1) и ways(n//2), а посчитанное запоминаем. Это буквально задание 16 с @lru_cache. Если ты его решаешь — ты уже умеешь ДП, просто не называл его так:
from functools import lru_cache
@lru_cache(maxsize=None)
def ways(n): # сколько программ ведут из 1 в n командами +1 и ×2
if n < 1:
return 0
if n == 1:
return 1 # база
res = ways(n - 1) # переход: последняя команда была +1
if n % 2 == 0:
res += ways(n // 2) # ...или ×2
return res
print(ways(6)) # 6
ДП-таблица — та же формула, но «снизу вверх»: заводим список, кладём базу, заполняем циклом:
dp = [0] * 7
dp[1] = 1
for n in range(2, 7):
dp[n] = dp[n - 1]
if n % 2 == 0:
dp[n] += dp[n // 2]
print(dp[1:]) # [1, 2, 2, 4, 4, 6]
Ответы совпадают, потому что рекуррентная формула одна. Разница в направлении: рекурсия идёт от вопроса к базе, таблица — от базы к вопросу.
| Подход | Направление | Когда хватает | Чем рискуешь |
|---|---|---|---|
| Перебор | все варианты подряд | маленькие n, десятки вариантов | взрывной рост времени |
Рекурсия + @lru_cache | сверху вниз | n примерно до тысячи | глубже — RecursionError, нужен sys.setrecursionlimit |
| ДП-таблица | снизу вверх | любые разумные n | нужно верно выбрать порядок заполнения |
Шаблоны ниже — табличные: их проще проверять руками и они не падают по глубине рекурсии. Но если формула сложная и в голове удобнее «спросить меньшее» — пиши рекурсию с lru_cache, ответ будет тот же.
Как увидеть ДП в условии
ДП не объявляет о себе. Условие говорит другими словами, и их надо узнавать.
| Фраза в условии | Подзадача | Размерность | Задание |
|---|---|---|---|
| «сколько существует программ», «количество способов получить» | dp[n] — число способов попасть в n | 1D | 23 |
| «максимальная (минимальная) сумма чисел на пути робота» | dp[i][j] — лучшая сумма до клетки (i, j) | 2D | 18 |
| «количество различных путей из A в B» | dp[i][j] — число путей до клетки | 2D | 18 |
| «наибольшая сумма пары при ограничении» (номера отличаются не меньше чем на K, сумма кратна 3) | лучший партнёр среди уже пройденных элементов | 1D, одно-три числа | 27 |
Общий признак у всех строк один: ответ для большого объекта складывается из ответов для меньших, и меньшие пересекаются. Одна клетка таблицы лежит на тысячах путей, одно число исполнителя встречается во множестве программ. Если пересечений нет — это обычный перебор или жадный выбор, ДП не нужно.
Шаблон 1. Одномерное ДП: количество программ исполнителя (задание 23)
Подзадача: dp[n] — сколько программ переводят A в n. База: dp[A] = 1 — пустая программа. Переход: последняя команда была либо +1 (пришли из n−1), либо ×2 (из n/2, если n чётное и n/2 не меньше A). Порядок — от A+1 до B.
Прежде чем писать код, заполни таблицу руками для A = 1, B = 6 — это твой контрольный пример:
| n | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| dp[n] | 1 | 2 | 2 | 4 | 4 | 6 |
| откуда | база | dp[1]+dp[1] | dp[2] | dp[3]+dp[2] | dp[4] | dp[5]+dp[3] |
Теперь шаблон. Обязательная и запрещённая точки — две самые частые надстройки, они встроены сразу:
def count(A, B, forbidden=()):
dp = [0] * (B + 1)
dp[A] = 1 # база: в A мы уже стоим — одна «пустая» программа
for n in range(A + 1, B + 1):
if n in forbidden: # запрещённая точка: сюда программ нет
continue
dp[n] = dp[n - 1] # пришли командой +1
if n % 2 == 0 and n // 2 >= A:
dp[n] += dp[n // 2] # пришли командой ×2
return dp[B]
print(count(1, 6)) # 6
print(count(2, 12)) # все программы из 2 в 12
print(count(2, 7) * count(7, 12)) # обязательно через 7
print(count(2, 12, forbidden={8})) # не проходя через 8
Вывод: 6, 10, 3, 5. Первое число совпало с ручной таблицей — значит, база и переход верны, и остальным ответам можно верить.
Две надстройки — это два разных механизма. Обязательная точка — произведение: все пути из A в X, умноженные на все пути из X в B. Запрещённая точка — обнуление ячейки: в неё программ нет, и дальше она ничего не передаёт. Комбинации («через X, но не через Y»), команды с вычитанием и прибавлением тройки разобраны в отдельной статье по заданию 23 — там же есть ловушки с чётностью и диапазонами.
Шаблон 2. Двумерное ДП: робот на таблице (задание 18)
Динамическое программирование в задании 18 — та же схема, только ячейка теперь имеет две координаты. Подзадача: dp[i][j] — лучшая сумма пути из (0, 0) в клетку (i, j). База: dp[0][0] = table[0][0]. Переход: в клетку приходят либо сверху, либо слева, значит dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + table[i][j]. Порядок — по строкам сверху вниз, внутри строки слева направо: к моменту (i, j) и «верхняя», и «левая» ячейки уже посчитаны.
Стены удобно хранить как −∞: тогда max сам их обойдёт, никаких отдельных веток. Первую строку и первый столбец не надо заполнять отдельными циклами — достаточно проверять, есть ли сосед сверху и слева:
table = [
[1, 4, 2, 5],
[3, 0, 6, 1],
[2, 7, 3, 4],
[5, 1, 2, 6],
]
walls = {(1, 1)} # сюда заходить нельзя
N, M = len(table), len(table[0])
NEG = float('-inf') # для min замени на float('inf') и max на min
dp = [[NEG] * M for _ in range(N)]
for i in range(N): # строка за строкой, слева направо
for j in range(M):
if (i, j) in walls:
continue # стена остаётся -inf: сквозь неё max не пройдёт
if i == 0 and j == 0:
dp[i][j] = table[i][j] # база: старт
continue
best = NEG
if i > 0:
best = max(best, dp[i - 1][j]) # пришли сверху
if j > 0:
best = max(best, dp[i][j - 1]) # пришли слева
dp[i][j] = best + table[i][j]
print(dp[N - 1][M - 1])
Вывод: 26. Меняешь NEG на float('inf') и max на min — получаешь минимальную сумму, здесь 20. Хочешь количество путей — база 1, вместо max складываешь соседей, стена равна 0: для этой таблицы выйдет 8. Одна структура, три ответа.
То же самое протягивается формулами в таблице: на второй лист копируешь числа, в первой строке и первом столбце — накопительные суммы, а в остальных ячейках одна формула вида =B2+MAX(A2;B1), растянутая на весь диапазон. Порядок заполнения Calc соблюдает сам, потому что каждая формула ссылается только на ячейки выше и левее. Как это делать быстро и где в Calc типичные грабли — в статье про электронные таблицы на ЕГЭ; подробный ручной разбор таблицы 4×4 и чтение из файла — в разборе задания 18.
Шаблон 3. Бегущий максимум для задания 27
Формат 27 менялся: в актуальных вариантах это кластерный анализ (подробно — в разборе задания 27), а несколько лет до этого — обработка длинной последовательности чисел из файла. Второй тип живёт в банке Полякова и в тренировочных вариантах, и именно на нём ДП-мышление тренируется лучше всего. Типовая задача: «выбрать два числа, номера которых отличаются не меньше чем на K, так, чтобы их сумма была максимальной». В файле десятки тысяч чисел и больше — перебор пар за O(n²) не успеет.
ДП-мысль: пока идём по массиву, для текущего элемента a[i] нужен лучший партнёр среди a[0..i-K]. Подзадача — «максимум префикса», база — «пусто», переход — префикс растёт на один элемент за шаг. Хранить весь массив префиксных максимумов не нужно, хватит одного числа:
K = 3
a = [5, 1, 9, 2, 8, 3, 7] # на экзамене: a = [int(x) for x in open('27.txt')]
best = float('-inf')
run_max = float('-inf') # лучший элемент среди тех, кто «уже далеко»
for i in range(K, len(a)):
run_max = max(run_max, a[i - K]) # элемент a[i-K] стал допустимым партнёром
best = max(best, run_max + a[i])
print(best)
Вывод: 16 — это 9 и 7, элементы с индексами 2 и 6 (нумерация с нуля), расстояние 4. Один проход, O(n), никаких вложенных циклов. Ключевой момент — сдвиг на K: в момент обработки a[i] в бегущий максимум попадает именно a[i-K], а не a[i-1], иначе ограничение нарушится.
Если добавляется условие «сумма кратна 3», бегущих максимумов становится три — по остатку от деления (K и a те же):
best = float('-inf')
run_max = [float('-inf')] * 3 # лучший «далёкий» элемент для каждого остатка
for i in range(K, len(a)):
x = a[i - K]
run_max[x % 3] = max(run_max[x % 3], x)
need = (3 - a[i] % 3) % 3 # какой остаток нужен партнёру
best = max(best, run_max[need] + a[i])
print(best)
Для того же массива получится 12 (9 + 3). Схема «состояние = лучшее из уже пройденного, обновляем за O(1)» — самый переносимый навык из всей статьи: он же ускоряет и кластерные задачи, где нужно не пересчитывать суммы заново на каждом шаге.
Три задания — одна таблица
| Задание | Размерность dp | База | Переход | Сложность | Минут на экзамене |
|---|---|---|---|---|---|
| 23 — количество программ | 1D, dp[n] | dp[A] = 1 | dp[n-1] + dp[n//2] (если чётно), запрет — обнуление | O(B) | 6–10 |
| 18 — робот, max/min суммы | 2D, dp[i][j] | dp[0][0] = table[0][0] | max(сверху, слева) + table[i][j], стена — −∞ | O(N·M) | 5–7 |
| 18 — количество путей | 2D, dp[i][j] | dp[0][0] = 1 | сверху + слева, стена — 0 | O(N·M) | 5–7 |
| 27 — пара с ограничением K | 1D, свёрнуто в 1–3 числа | −∞ | run_max = max(run_max, a[i-K]) | O(n) | 40+ на всё задание |
Заметь, как мало меняется от строки к строке: база и переход. Именно поэтому нет смысла учить три разных «метода решения» — учи одну схему и три пары «база + переход».
Типичные ошибки и отладка руками
Ошибки в ДП всегда одни и те же, и все они ловятся одним способом.
- Не та база.
dp[A] = 0вместо1в задании 23 — вся таблица нули.dp[0][0] = 0вместоtable[0][0]в задании 18 — ответ меньше на одну клетку. База отвечает на вопрос «а сколько способов ничего не делать?» — обычно ровно один. - Неверный порядок заполнения. Формула ссылается на ячейку, которая ещё не посчитана, и берёт оттуда ноль. В 2D это случается, когда ходишь по столбцам, а переход написан «сверху и слева» — проверь, что цикл по строкам внешний.
- Off-by-one.
range(A + 1, B)вместоrange(A + 1, B + 1)— последняя ячейка не считается. Список длинойBвместоB + 1—IndexError, и хорошо, если он есть, а не тихий сдвиг. - Забыл запрет или обязательную точку. Прочитал условие до слова «сколько», а «не проходя через 8» пропустил. Перечитывай условие после того, как написал переход, а не до.
- Условие чётности потерялось.
dp[n // 2]без проверкиn % 2 == 0— для нечётных n программа посчитает лишние программы, а Python не пожалуется.
Отладка одна: уменьши задачу до 5–6 ячеек и заполни таблицу руками, потом выведи dp целиком из программы (print(dp)) и сравни. Расхождение показывает пальцем на строку с ошибкой. Такая проверка занимает две минуты — на порядок дешевле потерянного балла. Другие промахи, которые стоят баллов на пустом месте, собраны в подборке типичных ошибок.
План тренировки на 5 дней
Пять вечеров по 40–60 минут — и три ДП-шаблона переходят в моторную память.
| День | Что делать | Результат |
|---|---|---|
| 1 | Задание 16: 5 задач через @lru_cache, потом каждую переписать таблицей | Чувствуешь «сверху вниз» и «снизу вверх» как одну формулу |
| 2 | Задание 23: 6–8 задач без ограничений, шаблон count() набирать не глядя | Шаблон печатается за минуту |
| 3 | Задание 23 с обязательной и запрещённой точками, 5–6 задач, каждую проверить на маленьком примере руками | Различаешь произведение и обнуление |
| 4 | Задание 18: max, min, количество путей, стены — по 2 задачи; одну решить в Calc | Двумерное ДП без подглядывания |
| 5 | Задание 27 в формате «пара чисел с ограничением»: 3 задачи через бегущий максимум, одну — с остатками | Пишешь O(n) вместо перебора |
На каждый день — свой контрольный пример на бумаге. Готовые задачи бери из открытого банка ФИПИ и сайта Полякова; в TuteMe задания 18 и 23 есть в базе отдельными типами, а к каждой ошибке идёт разбор с ходом решения — видно, где именно разошлись база или переход. Если ты работаешь по стратегии на 90+, эти пять дней логично поставить сразу после блока с рекурсией. Короткие Python-приёмы, которые ускоряют набор шаблонов — генераторы, enumerate, lru_cache, — собраны в подборке идиом.
Что делать дальше
Чек-лист перед тем, как считать ДП закрытым:
- Формулируешь подзадачу одной фразой для любой из трёх задач.
- Набираешь
count()для задания 23 и двойной цикл для 18 без подсказок, за минуту-две. - Знаешь, чем обязательная точка (произведение) отличается от запрещённой (обнуление).
- Помнишь про сдвиг на K в бегущем максимуме.
- Любой неправильный ответ проверяешь таблицей на 5–6 ячеек, а не перечитыванием кода десять раз.
Если хочешь тренировать это в тренажёре: в TuteMe есть встроенный редактор Python прямо в браузере, а адаптивный подбор заданий вернёт тебя к 18 и 23, как только увидит, что там начались ошибки.