Рекурсия — красивая штука, пока ваш код не зависает на минуту при n = 40. Знакомо? Тогда добро пожаловать в мир динамического программирования (ДП) — подхода, который превращает экспоненциальный кошмар в линейную прогулку.
В этой статье разберём, что такое ДП, почему оно быстрее рекурсии и как применять его к типичным задачам — от чисел Фибоначчи до задач ЕГЭ по информатике.
Что такое динамическое программирование?
Динамическое программирование — это способ решения сложных задач, при котором мы сохраняем в памяти результаты уже решённых подзадач и используем их повторно, вместо того чтобы считать одно и то же снова и снова.
Впервые этот подход предложил американский математик Ричард Беллман для задач оптимизации. Сегодня ДП — один из ключевых инструментов в алгоритмике, олимпиадном программировании и на собеседованиях.
Два обязательных условия для применения ДП:
- Задачу можно разбить на подзадачи того же типа.
- Каждая подзадача решается независимо от других.
Классический пример: числа Фибоначчи
Последовательность Фибоначчи знакома всем: 0, 1, 1, 2, 3, 5, 8, 13… Каждое число — сумма двух предыдущих:
F(0) = 0, F(1) = 1
F(n) = F(n-1) + F(n-2) при n > 1
Рекурсивный подход (медленный)
Проблема очевидна: для вычисления F(5) функция вызывается 15 раз, при этом F(2) считается трижды, F(3) — дважды. При n = 40 количество вызовов взрывается до миллиардов. Сложность — O(2ⁿ).
Подход через ДП (быстрый)
Идея проста: заведём массив и заполним его снизу вверх, от известных значений к неизвестным:
Теперь каждое значение вычисляется ровно один раз. Сложность — O(N), то есть линейная. Программа мгновенно выдаёт результат даже для очень больших N.
Расплата за скорость — дополнительная память под массив. Но это честная сделка: меняем память на время.
Задача из ЕГЭ: хитрая рекуррентная формула
Рассмотрим типичную задачу, которую любят давать на экзамене.
Условие. Функция задана соотношениями:
F(n) = n при n ≤ 3
F(n) = F(n-1) + 2·F(n/2) при чётных n > 3
F(n) = F(n-1) + F(n-3) при нечётных n > 3
Нужно определить, для скольких значений n из отрезка [1; 1000] значение F(n) оканчивается на цифру 5.
Почему рекурсия не спасёт
Можно попробовать написать рекурсивную функцию:
Но при больших n это работает недопустимо долго — сложность экспоненциальная.
Решение через ДП
Выделяем массив из 1001 элемента и заполняем его итеративно:
Теперь считаем, сколько значений оканчиваются на 5:
Программа выдаёт ответ за доли секунды.
Альтернативная запись через генератор списка — более «питонистый» вариант:
print(sum(1 for n in range(4, N + 1) if F[n] % 10 == 5))
Задача посложнее: подсчёт программ исполнителя
Условие. Исполнитель преобразует число на экране. У него три команды:
- Прибавить 1
- Прибавить 3
- Умножить на 2
Сколько существует программ, которые преобразуют число 1 в число 10 000? В ответе нужны последние 6 цифр.
Анализ
Обозначим через F(n) количество программ, переводящих 1 в n. Число n могло получиться:
- из n - 1 командой «Прибавить 1»;
- из n - 3 командой «Прибавить 3»;
- из n / 2 командой «Умножить на 2» (только для чётных n).
Получаем рекуррентность:
F(1) = 1
F(n) = F(n-1) + F(n-3) при нечётном n > 1
F(n) = F(n-1) + F(n-3) + F(n/2) при чётном n > 1
Решение
Зачем берём остаток от деления?
При больших N значение F(n) становится астрономическим — десятичная запись F(10 000) содержит более 1600 цифр. Работа с такими числами сильно тормозит Python. Но нам нужны только последние 6 цифр, и можно доказать, что при сложении последние 6 цифр суммы зависят только от последних 6 цифр слагаемых. Поэтому мы берём остаток % 1_000_000 на каждом шаге — и программа работает мгновенно.
Альтернативный подход: заполнение «вперёд»
Вместо того чтобы смотреть, откуда могло прийти значение, можно рассуждать куда оно передаётся:
Здесь мы увеличили массив вдвое, чтобы избежать проверок на выход за границы. Оба подхода дают одинаковый результат.
Шпаргалка: когда применять ДП
Динамическое программирование стоит попробовать, если:
- задача разбивается на подзадачи того же типа;
- подзадачи перекрываются (одни и те же значения нужны многократно);
- есть рекуррентная формула, связывающая текущее значение с предыдущими;
- рекурсивное решение слишком медленное.
Общий рецепт:
- Определите, что именно считает F(n).
- Запишите рекуррентное соотношение.
- Определите базовые случаи.
- Заведите массив и заполните его от базовых случаев к нужному значению.
- Если числа слишком большие — храните только нужную часть (остаток от деления).
Итог
Динамическое программирование — это не магия, а дисциплина: вместо того чтобы каждый раз пересчитывать одно и то же, мы запоминаем результат и переиспользуем его. Алгоритм превращается из экспоненциального в линейный, а программа — из зависающей в мгновенную.
Освоив этот приём, вы сможете решать задачи ЕГЭ по информатике быстрее и увереннее, а заодно получите мощный инструмент для реальных задач — от оптимизации маршрутов до анализа данных.
Если статья была полезна — ставьте лайк и подписывайтесь. В следующих материалах разберём другие приёмы динамического программирования: задачу о рюкзаке, наибольшую общую подпоследовательность и многое другое.
Телеграмм канал https://t.me/binaryinforma