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

> Считаем количество программ исполнителя командами «прибавь 1» и «прибавь 2»: таблица R(n) снизу вверх, рекурсия с мемоизацией, запрещённая и обязательная точки и обратные команды — весь метод задания 23 ЕГЭ.

**Информатика, 11 класс.** Урок бесплатного онлайн-самоучителя «ШкольныйГид». Обновлено: 2026-10-01.

Страница урока: https://shkolniygid.ru/informatika/11-klass/dinamicheskoe-programmirovanie-11/

В задании 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 — больше десяти тысяч: перечисление бессильно, подсчёт — нет.


| n | R(n) | Откуда собираем |
| --- | --- | --- |
| 0 | 1 | база: пустая программа |
| 1 | 1 | только R(0), слагаемого R(-1) нет |
| 2 | 2 | R(1) + R(0) = 1 + 1 |
| 3 | 3 | R(2) + R(1) = 2 + 1 |
| 4 | 5 | R(3) + R(2) = 3 + 2 |
| 5 | 8 | R(4) + R(3) = 5 + 3 |
| 6 | 13 | R(5) + R(4) = 8 + 5 |
| 7 | 21 | R(6) + R(5) = 13 + 8 |
| 8 | 34 | R(7) + R(6) = 21 + 13 |
| 9 | 55 | R(8) + R(7) = 34 + 21 |
| 10 | 89 | R(9) + R(8) = 55 + 34 |

*Полный расчёт R(0..10) для команд «прибавь 1» и «прибавь 2» со старта 0*


*[Интерактив: Заполнение таблицы от 0 до 10 — доступен на странице урока]*


Столбец значений: 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) раскручивается к базе и по дороге заполняет кэш: каждая клетка считается один раз. Без декоратора дерево вызовов раздваивалось бы на каждом шаге и пересчитывало одни и те же клетки миллионами порций. Направления разные: таблица растёт от базы к финишу, рекурсия спускается от финиша к базе, но клетки созревают в одном порядке. Ответ одинаков, разница только в стиле кода.


> **Совет.** Проверяй себя на маленьких числах. Возьми a = 1 и b = 4 и выпиши программы руками: 111, 12 и 21 — всего три. Таблица со стартом 1 даёт R(1) = 1, R(2) = 1, R(3) = 2, R(4) = 3 — сошлось. Сверка занимает полминуты, а страхует от нуля в базе, потерянной границы и перепутанного направления. Прежде чем доверять большой таблице, прогони маленькую.


*[Интерактив: Верно или нет? — доступен на странице урока]*


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


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


**Прогон с запретом: из 0 в 10, нельзя через 4**

1. База: R(0) = 1. Клетка 4 под запретом — там будет ноль.
2. R(1) = 1, R(2) = R(1) + R(0) = 2, R(3) = R(2) + R(1) = 3.
3. R(4) = 0 — запрещённая точка, пути в неё погашены.
4. R(5) = 0 + 3 = 3; R(6) = 3 + 0 = 3; R(7) = 3 + 3 = 6; R(8) = 6 + 3 = 9.
5. R(9) = 9 + 6 = 15; R(10) = 15 + 9 = 24. Ответ: 24.

*Без запрета в клетке 10 стоит 89 — сравни.*


Сверим запрет с вычитанием. Сколько программ из 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 — результат таблицы с нулём в пятёрке. Произведение отвечает на «через», таблица с нулём — на «мимо», вычитание лишь связывает готовые ответы.


> **Ловушки задания 23.** Первая — направление заполнения: команды увеличивают число — заполняй слева направо, от старта к финишу; команды уменьшают — справа налево. Перепутал — клетка тянет ещё не готовые значения, и таблица рассыпается. Вторая — двойка и чётность: слагаемое с делением появляется только там, где делить можно. В прямых задачах с «умножить на 2» клетка n забирает R(n / 2) только при чётном n; в обратных с «раздели на 2» приходишь из клетки 2n, пока 2n не вышло за старт. Третья — двойной счёт путей: каждый путь в задаче с обязательной точкой учитывается произведением ровно один раз, точка разреза делит его однозначно; не смешивай ответы «через C» и «мимо C».


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


Обратные команды меняют только направление заполнения. Пусть команды — «вычти 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)
**Запрещённая точка** — ноль в клетке гасит все программы через неё
**Обязательная точка** — произведение количеств программ до и после неё
**Мемоизация** — кэш значений при счёте сверху вниз


## Частые вопросы

### Почему в базу записывают единицу, а не ноль?

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


### Какой способ лучше: таблица или рекурсия с мемоизацией?

Для ручного счёта — таблица: она и есть черновик. Для проверки кодом быстрее написать рекурсию с lru_cache: она дословно повторяет определение R(n). Ответ одинаков, разница только в стиле.


### Чем «не проходит через K» отличается от «проходит через K»?

«Не проходит» — ноль в клетке K и обычное заполнение: отвечаем на вопрос «мимо». «Проходит» — произведение количеств программ до K и после K. Связывает ответы вычитание: всего минус мимо равно через.


### Что меняется, если команды «вычесть 1» и «вычесть 2»?

Только направление заполнения: база в большем числе, клетки заполняются справа налево, каждая собирает приходы из n + 1 и n + 2. С командой «раздели на 2» появляется слагаемое из клетки 2n, пока 2n не правее старта.


## Проверь себя (вопросы и ответы)

#### Вопрос 1: Сколько различных программ переводят число 0 в число 5, если команды исполнителя — «прибавь 1» и «прибавь 2»?
- ☐ 5
- ☐ 6
- ✅ 8
- ☐ 13

*Пояснение: Таблица от нуля: R(0) = 1, R(1) = 1, R(2) = 2, R(3) = 3, R(4) = 5, R(5) = 8. В клетке 5 — восемь программ.*


#### Вопрос 2: Что верно про подсчёт программ через обязательную точку C?
- ✅ количество программ до C умножается на количество программ после C
- ✅ каждая программа через C учитывается в произведении ровно один раз
- ☐ количество программ через C находят вычитанием из общего числа
- ☐ точка C обязательно должна быть чётной

*Пояснение: Точка C делит каждую программу однозначно, поэтому количества отрезков перемножаются, и двойного счёта нет. Вычитание отвечает лишь на вопрос «мимо C», а чётность C роли не играет.*


#### Вопрос 3: Сколько программ переводят число 0 в число 10, если траектория не должна проходить через число 4? Впиши число.
**Ответ:** 24

*Пояснение: Ноль в клетке 4, дальше обычное заполнение: R(5) = 3, R(6) = 3, R(7) = 6, R(8) = 9, R(9) = 15, R(10) = 24. Проверка вычитанием: всего 89, через 4 проходит 5 · 13 = 65, обходят 89 - 65 = 24.*


#### Вопрос 4: Если команды исполнителя уменьшают число, таблицу заполняют от большего к меньшему.
- ✅ Правда
- ☐ Неправда

*Пояснение: Клетка собирает приходы из уже заполненных клеток: при вычитании предшественники стоят правее, поэтому заполнение идёт справа налево, от старта к финишу.*


#### Вопрос 5: Расставь шаги решения с запрещённой точкой по порядку.
**Правильный порядок:** вписать единицу в стартовую клетку → записать ноль в запрещённую точку K → заполнить клетки от старта к финишу, собирая приходы → взять число из клетки финиша — это ответ

*Пояснение: Сначала база, затем запреты, потом заполнение слева направо — и только в конце ответ из финишной клетки. Пропуск шага ломает всю таблицу.*


#### Вопрос 6: Сопоставь термин и его смысл.
- база — единица в стартовой клетке
- переход — сумма приходов из клеток-предшественников
- обязательная точка — произведение количеств программ по отрезкам
- мемоизация — кэш готовых значений при счёте сверху вниз

*Пояснение: Четыре опоры метода: база, переход, правило обязательной точки и способ счёта сверху вниз. На них держится любой вариант задания 23.*


#### Вопрос 7: Дополни правило подсчёта программ.
Количество программ в клетке n складывается из количеств программ в клетке **n - 1** и в клетке **n - 2**, а в клетку запрещённой точки записывают **ноль**.

*Пояснение: Команда «прибавь 1» приходит из n - 1, команда «прибавь 2» — из n - 2. Запрещённая точка получает ноль, и все пути через неё гаснут.*


## Тренажёр

На [странице тренажёра](https://shkolniygid.ru/informatika/11-klass/dinamicheskoe-programmirovanie-11/trenazher/) — 4 типов задач с бесконечными вариантами чисел, проверкой ответа и разбором каждого шага.