Динам. программирование: старт перед экзаменом
Динам. программирование давно стало краеугольным камнем ЕГЭ по информатике. Метод позволяет решать задачи, которые кажутся громоздкими при прямом переборе. Школьник записывает переходы между состояниями и плавно строит ответ. В этом разделе мы вспомним базовую идею и развеем главный миф: техника доступна каждому, кто готов считать аккуратно.
Суть метода проста. Мы разбиваем сложную задачу на ряд пересекающихся подзадач. Для каждой подзадачи храним результат, чтобы не пересчитывать значения дважды. Нужен массив, таблица или словарь, где индексы описывают состояние, а значение — результат. Затем идём к более крупным состояниям, опираясь на уже посчитанные.
Важно заметить: динамика — это не всегда минимум или максимум. Часто спрашивают количество путей, количество способов разрезать строку, число наборов монет. Главное — понять, какие параметры уникально описывают текущий шаг.
Когда применяем метод и когда ищем другой путь
Не всякую задачу нужно решать динамикой. Если данные малы, прямой перебор порой быстрее. Однако есть явные признаки, что метод зайдёт: повторяющиеся подзадачи, наличие естественного порядка расчёта, умеренное число различных состояний.
Пример. Требуется посчитать количество слов длиной N из алфавита, где нет двух подряд одинаковых букв. Перебор даст экспоненту. Динамика даёт линейное время по длине слова и размеру алфавита.
Другой пример. Найти наибольшую возрастающую подпоследовательность в массиве длинной до 10³. Сложность O(n²) приемлема при n ≤ 1000. При n ≤ 300 можно даже сделать двойной цикл без динамики. Всегда оценивайте размеры входа.
Если признаков повторения нет или каждый переход зависит от всей истории, метод не сработает. Тогда лучше использовать жадный алгоритм, структуру данных или перебор с отсечениями.
Типовая задача ЕГЭ: количество маршрутов
Чаще всего встречается таблица из клеток 15 × 20. Нужно узнать число путей из левой верхней клетки в правую нижнюю, движемся только вправо и вниз. Решение строится за три шага.
- Инициализируем первую строку и первый столбец единицами. Есть только один способ двигаться вдоль края.
- Для каждой клетки (i, j) суммируем значения сверху и слева: ways[i][j] = ways[i-1][j] + ways[i][j-1].
- Ответ хранится в правом нижнем углу таблицы.
Задача тренирует внимательность. В условии могут запретить некоторые клетки. Тогда в этих точках заносим ноль и пересчитываем остальные значения так же. Метод остаётся тем же.
Чтобы проверить себя, нарисуйте маленькое поле 4 × 4. Расположите одну стену и получите количество путей вручную. После этого код пишется без ошибок.
Формулы перехода без лишней теории
Больше всего времени школьники тратят на поиск правильного перехода. Запомните простой рецепт. Сначала определяем минимальный набор параметров, которые однозначно описывают состояние. Затем задаём правило, как получить новое состояние из старых.
Возьмём размен суммы S монетами номиналов c₁…cₖ. Параметры: индекс монеты и оставшаяся сумма. Переход: dp[i][s] = dp[i-1][s] + dp[i][s-cᵢ]. То есть не берём текущую монету либо берём ещё одну такую же. Ошибку многие делают в границах: второй аргумент не должен уходить в отрицательный диапазон.
Другой пример касается последовательностей. В поиске наибольшей общей подпоследовательности параметрами служат позиции в первой и второй строке. Формула: если символы совпали, берём +1 к диагонали. Иначе — максимум из левой или верхней ячейки.
Каждый раз проверяйте валидность перехода на маленьких входных данных. Так вы поймаете логические ошибки до тестовой системы.
Оптимизация памяти и времени
Полная таблица не всегда помещается в оперативную память. Хорошая новость: часто нужен только предыдущий слой. Снова посмотрим на поле путей. Для вычисления строки j нужен только j и j-1. Значит, держим один массив длиной ширины поля.
Сумма разменов тоже оптимизируется. Мы двигаемся по номиналам и заполняем массив длины S. Сохраняем результат для каждой суммы, а затем переиспользуем его.
Иногда экономия времени более важна, чем память. Тогда параллельно считаем несколько переходов. В задачах ЕГЭ это редкость, но знать технику полезно.
Всегда измеряйте сложность: количество состояний умножить на стоимость перехода. Если число превышает 10⁷, стоит искать оптимизацию. Эксперты любят задачи, где аккуратное сокращение слоёв спасает от превышения лимита.
Как писать решения, чтобы эксперт поставил балл
Алгоритм решён — половина дела. Вторая половина — правильный вывод. Чтобы не потерять баллы, держим короткий чек-лист:
- Читаем вход до конца, даже если последняя строка пустая.
- Используем читаемые имена: ways, dp, prevRow. Переиспользуем массивы с комментарием.
- Выводим итог ровно в требуемом формате. Без лишних слов и символов.
- Добавляем проверку границ перед обращением к массиву.
- Пишем небольшие комментарии: «// переход динамики», «// инициализация».
Запомните: эксперт видит сотни работ. Чем понятнее код, тем быстрее он убедится в корректности. Если есть время, протестируйте решение на своих тестах. Маленький файл с угловыми случаями спасает от обидной ошибки в последний день.
Хотите больше практики и обратную связь? Запишитесь на курс подготовки к ЕГЭ в онлайн школе el-ed.ru и получите проверку каждого решения.
Частые ошибки и способы их избежать
Первая ошибка — забытая инициализация. Одно неверное нулевое значение рушит всю таблицу. Решение: заполняйте базовый слой сразу после создания массива.
Вторая ошибка — перегрузка памяти. Ученик держит трёхмерный массив, хотя хватает двух измерений. Перед кодированием выпишите размер таблицы на бумаге. Если число элементов превышает 10⁷, ищите способ сократить измерение.
Третья ошибка — путаница в направлении прохода. При подсчёте путей по полю нужно идти слева направо и сверху вниз. Изменили порядок — получите нули вместо суммы.
Четвёртая ошибка касается типов. Счёт путей часто выходит за 32-бит. Используйте long long в C++ или Python int без ограничений.
Последняя проблема — пропуск проверки частных случаев. Если условие разрешает нулевую длину строки, код должен вернуть корректный ответ и там.
План тренировки на оставшийся месяц
Месяц до экзамена — достаточный срок, если заниматься регулярно. Распланируйте время по неделям.
Первая неделя. Пройдите все типы «количество путей» и «размен суммы». Решите минимум 20 задач, чтобы рука привыкла.
Вторая неделя. Добавьте задачи «набор из подпоследовательностей» и «максимальная сумма». Разберите случай, когда надо вывести сам путь, а не только число.
Третья неделя. Тренируйте оптимизацию памяти. Перепишите старые решения, используя один-два массива. Сравните скорость.
Четвёртая неделя. Решайте смешанные варианты из прошлых лет. Засекайте время: на задачу максимум 15 минут. После проверки пишите разбор ошибки в отдельную тетрадь.
В день перед экзаменом не учите новое. Повторите формулы переходов и выспитесь. Спокойная голова приносит больше баллов, чем ещё один час ночных попыток.