Динамическое программирование: подсчёт программ (задание 23 ЕГЭ)

В задании 23 ЕГЭ работает исполнитель с двумя командами: «прибавь 1» и «прибавь 2». Вопрос один: сколько различных программ переводят число a в число b? Лобовой перебор проваливается: уже на отрезке в двадцать единиц программ больше десяти тысяч, и каждую надо не только придумать, но и не посчитать дважды. Динамическое программирование переворачивает задачу: не перечисляем программы, а для каждой точки числовой прямой считаем, сколько программ в неё приводит. Один проход по отрезку — и ответ готов. Дальше: таблица, два кода на Python, запреты и обратные команды.

Одна клетка — одна точка: функция R(n)

Обозначим R(n) — количество программ, переводящих стартовое число в точку n. При старте в нуле база: R(0) = 1 — одна пустая программа в старте. Смотрим, откуда можно попасть в n: последняя команда — либо «прибавь 1» (программа была в n - 1), либо «прибавь 2» (была в n - 2), других вариантов нет. Значит, программы до n — это в точности программы до n - 1 с добавленной «+1» и до n - 2 с добавленной «+2». Отсюда переход: R(n) = R(n - 1) + R(n - 2). Оговорка у начала: если n - 2 отрицательно, слагаемого нет — туда из старта не добраться.

Договоримся, что именно считает таблица. Программа — последовательность команд, а не список точек: 1-1-2 и 1-2-1 — разные программы, хотя обе ведут из 0 в 4. Проверь метод на крошечном отрезке: выпиши все программы из 0 в 4. Их пять: 1111, 112, 121, 211 и 22, где единица — «прибавь 1», двойка — «прибавь 2». Запусти переход: R(0) = 1, R(1) = 1, R(2) = 2, R(3) = 3, R(4) = 5 — ровно пять, как в списке. Из 0 в 10 программ уже 89, из 0 в 20 — больше десяти тысяч: перечисление бессильно, подсчёт — нет.

Столбец значений: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 — числа Фибоначчи со сдвигом: при командах «+1» и «+2» верно R(n) = F(n + 1). Правило «каждое следующее — сумма двух предыдущих» у них общее. Отсюда следствие: ответ определяется длиной отрезка, а не положением на прямой. Программ из 2 в 7 столько же, сколько из 0 в 5, — восемь. Одна таблица даёт ответы для всех пар с тем же расстоянием между стартом и финишем.

Два способа считать: таблица и мемоизация

Первый способ — снизу вверх: массив заполняется слева направо, от базы к финишу: R = [0] * (B + 1) R[0] = 1 for n in range(1, B + 1): R[n] = R[n - 1] if n >= 2: R[n] += R[n - 2] print(R[B]) При B = 10 программа напечатает 89. Массив — та же черновая таблица: клетка n готова к моменту, когда понадобится. Проверка n >= 2 бережёт левую границу: у клетки 1 нет соседки через два шага. Стека у такого кода нет: один проход по отрезку, память пропорциональна его длине.

Второй способ — сверху вниз: рекурсия прямо по определению R(n), с кэшем от functools: from functools import lru_cache @lru_cache(maxsize=None) def R(n): if n == 0: return 1 s = R(n - 1) if n >= 2: s += R(n - 2) return s print(R(10)) Вызов R(10) раскручивается к базе и по дороге заполняет кэш: каждая клетка считается один раз. Без декоратора дерево вызовов раздваивалось бы на каждом шаге и пересчитывало одни и те же клетки миллионами порций. Направления разные: таблица растёт от базы к финишу, рекурсия спускается от финиша к базе, но клетки созревают в одном порядке. Ответ одинаков, разница только в стиле кода.

Запрещённая точка: ноль гасит пути

Вариант с ограничением: траектория не должна проходить через число K. Правило: в клетку K записываем ноль и дальше считаем как обычно. Ноль означает: ни одна программа не приходит в K и не продолжится из K — слагаемое R(K) дальше ничего не добавляет, и запрет разносится вправо сам. «Не проходит через K» запрещает K на всей траектории, включая конец. Финиш совпадает с K — ответ ноль программ, таблица покажет это сама. Не путай с формулировкой, где K — обязательная остановка: там работает умножение.

Сверим запрет с вычитанием. Сколько программ из 0 в 10 проходят через 4? До четвёрки ведёт R(4) = 5 программ, после неё отрезок длиной 6 с 13 продолжениями: каждый кусок первой половины продолжается каждым куском второй. Через четвёрку проходит 5 · 13 = 65 программ. Всего 89, значит, обходят 89 - 65 = 24 — ровно столько же, сколько дала таблица с нулём.

Обязательная точка: умножаем отрезки

Обязательная точка — зеркальное условие: программа обязана пройти через число C. Путь делится в C на два независимых отрезка: из старта в C и из C в финиш. Каждый путь первой половины сочетается с каждым путём второй — количества перемножаются: ответ равен (старт до C) · (C до финиш). Пример: из 0 в 10 через 5? Отрезок от 0 до 5 содержит 8 программ, от 5 до 10 — тоже 8, длина та же. Ответ 8 · 8 = 64. Обязательных точек две — отрезков три, перемножаются три числа.

Ловушка с вычитанием. Видя «проходит через C», некоторые вычитают из общего числа программ что-нибудь «по смыслу». Неверно: вычитание отвечает только на вопрос «мимо C», и то если обходящие уже честно посчитаны нулём в клетке. Связка такая: всего = через C + мимо C. Для 0 в 10 с точкой 5: 89 = 64 + 25, где 25 — результат таблицы с нулём в пятёрке. Произведение отвечает на «через», таблица с нулём — на «мимо», вычитание лишь связывает готовые ответы.

Обратное направление: вычти и раздели

Обратные команды меняют только направление заполнения. Пусть команды — «вычти 1» и «вычти 2», и перевести надо 10 в 2. База в старте: R(10) = 1, заполняем справа налево, от большего к меньшему: в клетку n приходим из n + 1 командой «минус 1» и из n + 2 командой «минус 2». Получаем R(9) = 1, R(8) = 2, R(7) = 3, R(6) = 5, R(5) = 8, R(4) = 13, R(3) = 21, R(2) = 34. Ответ — 34 программы: спуск с 10 до 2 — зеркало подъёма с 0 до 8. Код отличается одной строкой: R = {10: 1} for n in range(9, 1, -1): R[n] = R[n + 1] + R.get(n + 2, 0) print(R[2]) Цикл идёт с шагом минус один, метод get достаёт значения правее — они уже готовы.

С командой «раздели на 2» появляется слагаемое из несоседней клетки. Пусть команды — «вычти 1» и «раздели на 2», старт 14, финиш 2. Заполняем справа налево: R(14) = 1, клетки 13, 12, 11, 10, 9 и 8 получают по единице — удвоенное число каждой выходит за старт. В клетке 7 приходим из 8 вычитанием и из 14 делением: R(7) = R(8) + R(14) = 2. Дальше R(6) = R(7) + R(12) = 3, R(5) = R(6) + R(10) = 4, R(4) = R(5) + R(8) = 5, R(3) = R(4) + R(6) = 8, R(2) = R(3) + R(4) = 13. Ответ: 13 программ. Слагаемое приходит справа, из клетки 2n, уже заполненной, — направление критично. Делимое 2n всегда чётно — проверяй лишь, что 2n не правее старта.

Собери карту задания 23. «Сколько программ из A в B» — таблица от старта к финишу, ответ в клетке B. «Не проходит через K» — ноль в K и обычное заполнение. «Обязана пройти через C» — произведение количеств по отрезкам. Команды уменьшают число — заполнение от большего к меньшему. Ядро одно: клетка собирает приходы от предшественников, база равна единице, направление подстраивается под команды. Финальная проверка: программы из 0 в 6 таблицей и перебором должны дать одно число — 13.

Мини-словарь темы

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

ответ для клетки считается из готовых ответов предшественников

R(n)#

число программ, ведущих из старта в точку n

База#

R(0) = 1 — одна пустая программа

Переход#

R(n) = R(n - 1) + R(n - 2)

Запрещённая точка#

ноль в клетке гасит все программы через неё

Обязательная точка#

произведение количеств программ до и после неё

Мемоизация#

кэш значений при счёте сверху вниз

Подсказка: клавиши J — следующая тема, K — предыдущая, на телефоне: свайп влево/вправо — соседняя тема