Динамическое программирование в ЕГЭ по информатике: разбор заданий 16, 18, 23

Что за тема и для чего нужна

** изображение создано или обработано с помощью ИИ.

Динамическое программирование звучит как пароль от подвала олимпиадников, но на деле всё проще. Мне 27, я успел и сам гореть на таких задачах (кофе, дедлайн, глаза как у совы), и разбирать их со школьниками. Метод хорошо приручается, если не пытаться сразу писать код.

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

На экзамене чаще всего ломает не формула, а вопрос «что вообще хранить?». Тут я советую остановиться и не трогать клавиатуру. Нарисуйте маленький пример — прямо стыдно маленький: 3 клетки, 4 монеты, 5 символов. Если на нём видно повторение, динамика уже машет рукой.

«А если я не вижу повторение?» — нормально, я тоже часто не видел. Тогда ищите выбор: взять или не взять, пойти вправо или вниз, поставить символ или пропустить. Выбор почти всегда ведёт к состоянию.

Короткий тест. Если ответ для текущей позиции зависит от прошлых позиций — пахнет динамикой. Если варианты пересекаются — запах усиливается. Если ещё просят максимум, минимум, количество способов или достижимость — почти приехали.

Где динамика реально встречается в ЕГЭ-2026:

1. Задание 18 (Робот в таблице). Классическая 2D-динамика: максимум/минимум суммы монет при движении вправо/вниз, учёт стен.

1. Задание 23 (Исполнитель/программы). 1D-динамика подсчёта: сколько программ переводят число A в B, не проходя через запретные числа.

1. Задание 16 (Рекурсия). Мемоизация (кэширование состояний) для ускорения вычислений и избегания повторных вызовов.

1. Задание 27 (Эффективные алгоритмы). Иногда требует оптимизации перебора через хранение префиксов или частот.

Задачи на рюкзак и LCS в экзамене не проверяются. Но отлично тренируют навык «состояние → переход», который спасает в №18 и №23.

Состояние: что хранить, чтобы не утонуть

** изображение создано или обработано с помощью ИИ.

Состояние — это вопрос, на который отвечает ячейка dp. Не «какая-то таблица», а конкретный смысл. Например: dp[i] — лучший ответ для первых i элементов. Или dp[i][j] — число способов дойти до клетки (i, j). Чем яснее смысл, тем меньше шансов написать кашу.

Я всегда проговариваю состояние вслух. Да, иногда на экзамене это выглядит странно, зато работает. «dp[i] хранит минимальную стоимость добраться до i-й ступени». Если фраза звучит мутно, формула тоже поплывёт.

Не начинайте с размера массива. Начните со смысла, размер появится сам. Для строки длины n часто нужны индексы от 0 до n, для таблицы — две координаты, для рюкзака — предметы и вместимость.

Мини-диалог из практики. Ученик: «Я создал dp на миллион, но не знаю зачем». Я: «Поздравляю, ты купил склад без товара». Ученик: «А что делать?» Я: «Подпиши каждую ячейку человеческой фразой».

Очень помогает правило последнего шага. Спросите себя: как я мог попасть в это состояние? Для клетки на поле — обычно сверху или слева. Для суммы — добавить последнюю монету. Для подпоследовательности — взять текущий символ или пропустить.

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

Переходы и база: два винтика одной машины

** изображение создано или обработано с помощью ИИ.

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

Начинайте с маленьких случаев. Для количества способов обычно есть «один способ ничего не выбрать». Для минимума часто ставят большое число, а старт равен нулю.

Для максимума старт тоже зависит от смысла задачи. Важно не заучивать шаблон слепо. Например, dp[0] = 1 верно для многих задач на число способов, но в задаче на стоимость это может оказаться ошибкой. Смысл решает, а не красивая формула.

Я пользуюсь таким чек-листом. Что означает dp[i] или dp[i][j]? Какие состояния уже известны перед расчётом текущего? Из каких вариантов приходит ответ? Что делать с невозможными состояниями? Какой ответ надо вывести в конце?

Последний пункт часто забывают. Задача может просить не dp[n], а максимум по последней строке или количество путей до любой финишной клетки. Я однажды потерял балл именно так — сидел потом с лицом «ну почти же». «Почти» на экзамене не компилируется.

Проверяйте переход на маленьком примере руками. Возьмите три элемента и посчитайте таблицу. Если ручной ответ расходится с кодом, ошибка рядом. Не надо героически отлаживать 200 строк. Динамика уважает карандаш больше, чем суету.

Как узнать тип задачи за минуту

** изображение создано или обработано с помощью ИИ.

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

Когда в условии фигурирует лестница, последовательность дней или дорожка из точек, перед вами, скорее всего, одномерная динамика. Состояние привязано к позиции, а переходы строятся из нескольких предыдущих точек. Например, разрешено шагнуть на одну или две клетки вперёд.

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

Когда появляются предметы с весами и ограничение на суммарную массу, вы имеете дело с задачей о рюкзаке. Состояние фиксирует лучший результат для первых i предметов при вместимости w.

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

Если в задаче есть строка, ищите динамику по префиксам. Подпоследовательности, редактирование текста, сравнение символов — всё это требует двух индексов i и j. Поначалу такой подход кажется громоздким, но со временем становится рабочим инструментом.

Задачи на суммы опознаются по вопросам: «можно ли набрать заданное число?» или «сколькими способами это сделать?». В таких случаях массив dp отвечает за возможность или количество способов получить конкретную сумму s, а переход добавляет очередное число или монету.

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

Экзаменационные ловушки, на которых я сам спотыкался

** изображение создано или обработано с помощью ИИ.

Первая ловушка — индексы. Ноль или единица? В коде это кажется мелочью, пока ответ не уезжает в сторону. Я иногда добавляю фиктивный нулевой элемент, чтобы первые i элементов выглядели естественно, но этот приём требует чёткого понимания.

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

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

Четвёртая ловушка — ответ не там. Перед выводом перечитайте вопрос. «Максимальная сумма на последней строке» и «значение в правом нижнем углу» — это разные вещи.

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

Одна история: на пробнике ученик написал идеальный переход для маршрутов, но забыл занулить клетки с препятствиями. Робот бодро прошёл сквозь стены. Ученик сказал: «У меня робот мотивированный». Смешно, но баллы ушли. После этого мы ввели правило: сначала отмечаем запреты, потом считаем пути.

План решения: от текста к коду без истерики

** изображение создано или обработано с помощью ИИ.

Я использую один и тот же план. Он скучный, зато надёжный. Сначала переформулируйте задачу одним предложением.

Например: «Нужно найти максимум очков после n ходов». Так вы отсекаете сюжетный шум. Потом найдите выбор. Что делает герой задачи на каждом шаге? Берёт предмет, идёт в клетку, выбирает символ, платит монету. Выбор задаёт переход. Без выбора динамика рождается редко.

Следующий шаг — состояние. Запишите его словами, не формулой. «dp[i] — лучший результат после обработки первых i элементов». Уже после этого добавляйте индексы, массивы и циклы. Код должен обслуживать идею, а не командовать ею.

Дальше выпишите базу. Не ленитесь: одна строка базы экономит десять минут отладки. Затем определите порядок обхода. Каждое значение должно брать уже посчитанные ответы — это закон кухни: нельзя жарить котлету на будущей сковородке.

Перед кодом оцените сложность. Если n доходит до больших значений, квадратичный алгоритм может не пройти. Конкретные границы зависят от языка и лимитов, но порядок роста видеть надо. O(n), O(nm), O(nW) — это не украшения.

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

Мини-тренировка перед экзаменом

** изображение создано или обработано с помощью ИИ.

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

Вот набор упражнений для самопроверки:

1. Сначала набросайте состояние, потом переход, и только после этого смотрите решение или пишите код.

1. Сколько способов добраться до n-й ступеньки, если можно шагать на 1 или 2?

1. Найдите минимальную стоимость пути по таблице при движении только вправо и вниз.

1. Проверьте, можно ли набрать сумму S из заданных чисел.

1. Найдите максимальную стоимость предметов при ограниченной вместимости.

1. Посчитайте длину общей подпоследовательности двух строк.

Для каждой задачи ответьте на четыре вопроса. Что хранит dp? Где база? Откуда приходят переходы? Где лежит итог? Если отвечаете без дрожи на все, вы уже опасный человек — в хорошем смысле.

После решения объясните его резиновой уточке, другу или стене. Я серьёзно. Если объяснение разваливается, в коде есть тёмный угол. Если звучит ясно, шанс на верный ответ растёт.

Динамика не требует гениальности. Она требует аккуратности и привычки видеть подзадачи. На экзамене это особенно ценно: вы не спорите с паникой, а действуете по плану. А паника пусть сидит сбоку и держит черновик.