Представьте, что вы стоите у подножия высокой лестницы и хотите узнать, сколькими способами можно подняться на сотую ступеньку, если за один шаг можно преодолеть либо одну, либо две ступени. Можно ли сразу дать ответ? Конечно, нет — задача кажется необъятной.
Но что, если начать с малого: сначала посчитать способы для первой ступеньки, потом для второй, третьей… и так постепенно добраться до сотой? Именно в этом и заключается суть динамического программирования.
В задании 23 ЕГЭ по информатике проверяется умение анализировать работу алгоритма с ветвлениями и циклами. На практике это почти всегда сводится к подсчёту количества способов получить одно число из другого с помощью заданных команд. И здесь на сцену выходит динамическое программирование.
Что такое динамическое программирование
Слово «программирование» в этом термине может сбить с толку. На самом деле термин появился задолго до того, как написание компьютерных программ стало массовым явлением. В 1950 году американский математик Ричард Беллман придумал этот метод для оптимизации сложных математических процессов. Тогда слово «программирование» означало просто «планирование», «составление плана действий».
Суть динамического программирования проста: если перед вами стоит сложная задача, которую невозможно решить напрямую, разбейте её на несколько простых подзадач. Решите эти подзадачи, сохраните результаты и используйте их для получения финального ответа. Звучит логично, но есть важный нюанс: подзадачи должны быть устроены одинаково и решаться по единому алгоритму.
Например, вы не можете сразу сказать, сколько способов есть преобразовать число 1 в число 100, используя операции «прибавить 3» и «умножить на 2». Но вы можете пошагово посчитать количество способов для промежуточных чисел: для 2, для 4, для 5 и так далее. А потом, опираясь на эти данные, получить ответ для 100.
Рекуррентное соотношение и Фибоначчи
Прежде чем двигаться дальше, необходимо познакомиться с ключевым понятием — рекуррентным соотношением. Это формула, которая выражает решение задачи через решения её подзадач меньшего размера.
Рекуррентное соотношение — это сердце динамического программирования. Без него невозможно понять, как именно разбивать задачу на части. Умение составлять такие соотношения — ключевой навык для решения задач этого типа.
Представьте, что вы строите башню из кубиков. Чтобы узнать высоту башни из десяти кубиков, достаточно знать высоту башни из девяти кубиков и прибавить высоту одного кубика. Это и есть рекуррентное соотношение: H(10) = H(9) + h, где h — высота одного кубика.
В более интересных задачах рекуррентные соотношения устроены сложнее. Возьмём числа Фибоначчи: каждое число равно сумме двух предыдущих. Записать это можно так:
F(n) = F(n-1) + F(n-2)
Эта простая формула связывает большую задачу (найти F(n)) с меньшими задачами (найти F(n-1) и F(n-2)). Она работает для любого n, но требует знания базовых случаев — тех значений, которые известны заранее и не требуют вычислений. Для чисел Фибоначчи это F(0) = 0 и F(1) = 1.
Сделаем небольшое лирическое отступление. Уже во второй раз (прошлый — в этой статье) мы говорим про какие-то числа некоего Фибоначчи. Что это за итальянец такой и чем знамениты его числа?
Леонардо Пизанский, более известный как Фибоначчи, жил в XIII веке и считается одним из величайших математиков Средневековья. Свои знаменитые числа он описал в задаче о кроликах: сколько пар кроликов будет через год, если каждая пара ежемесячно порождает новую пару, а новорождённые кролики начинают размножаться со второго месяца жизни? Ответ как раз даёт последовательность 0, 1, 1, 2, 3, 5, 8, 13, 21… — каждое число является суммой двух предыдущих.
Казалось бы, абстрактная средневековая задачка про кроликов — зачем она современному программисту? Дело в том, что числа Фибоначчи всплывают в самых неожиданных местах. В теории алгоритмов они возникают при анализе худшего случая алгоритма Евклида для нахождения НОД — именно последовательные числа Фибоначчи заставляют его работать максимально долго.
Структура данных «куча Фибоначчи» названа так не случайно: размеры поддеревьев в ней подчиняются закономерностям этой последовательности. В алгоритмах поиска существует фибоначчиев поиск — альтернатива бинарному поиску, которая делит массив в отношении соседних чисел Фибоначчи.
За пределами чистого программирования эти числа тоже встречаются повсюду. В природе спирали семян подсолнуха и чешуек сосновых шишек следуют числам Фибоначчи. В трейдинге уровни коррекции Фибоначчи — стандартный инструмент технического анализа. В теории информации они связаны с оптимальным кодированием. Даже в музыке и архитектуре пропорции, основанные на золотом сечении (а оно тесно связано с числами Фибоначчи), считаются эстетически приятными.
А для нас сейчас они ценны тем, что представляют собой идеальный учебный пример — достаточно простой, чтобы разобраться в сути, но уже содержащий ту самую ловушку, в которую попадает наивная рекурсия, делая одну и ту же работу многократно. Об этом мы поговорим буквально в паре абзацев ниже.
Где применяется динамическое программирование
Динамическое программирование используется там, где прямое решение слишком громоздко или вообще невозможно. Вот несколько классических примеров.
Числа Фибоначчи. С ними мы уже знакомы: 0, 1, 1, 2, 3, 5 и так далее. Первые 6 чисел довольно просто вспомнить. А попробуйте сразу назвать 35-е число этого ряда. Не получается? Правильно, потому что для его вычисления нужно знать вообще все предыдущие числа. Вот здесь и пригодится динамическое программирование.
Задачи про роботов. Представьте робота на клетчатом поле, который может двигаться только вправо или вниз. Сколько разных путей у него есть, чтобы добраться из левого верхнего угла в правый нижний? Прямой перебор всех вариантов займёт вечность, а динамическое программирование решит задачу за секунды. Да-да, мы говорим про то самое задание 19 из ЕГЭ по информатике!
Преобразование чисел. А это уже как раз то, что встречается в задании 23 на экзамене. Есть число, есть набор операций (например, «прибавить 3» или «умножить на 2»), нужно найти, сколькими способами можно получить из одного числа другое.
Все эти задачи объединяет одно: для решения нужно опираться на результаты более простых вариантов той же задачи.
Разбиение задачи на подзадачи
Разбиение задачи на подзадачи работает только при соблюдении двух условий.
Первое: подзадачи должны иметь общую структуру. Если вы решаете задачу про числа Фибоначчи, то каждая подзадача выглядит одинаково: найти сумму двух предыдущих чисел. Это позволяет использовать один и тот же алгоритм для всех уровней.
Второе: должен быть способ сохранять и переиспользовать результаты. Представьте, что вы каждый раз заново вычисляете одно и то же число. Это бессмысленная трата времени. Вместо этого вы решаете подзадачу один раз, запоминаете ответ и потом просто достаёте его из памяти.
Давайте разберём на примере чисел Фибоначчи, как происходит разбиение:
Чтобы найти F(35), нужно знать F(34) и F(33). Чтобы найти F(34), нужно знать F(33) и F(32). И так далее, пока не дойдём до известных нам F(0) = 0 и F(1) = 1. Мы идём от большого к малому, пока не упрёмся в базовые случаи.
Два подхода: нисходящий и восходящий
Существуют два принципиально разных способа применять динамическое программирование. Чтобы понять разницу между ними, представьте, что вам нужно построить пирамиду.
Нисходящий подход (сверху вниз)
Представьте, что вы архитектор, который начинает проектирование с вершины пирамиды. Вы говорите: «Чтобы построить вершину, мне нужен предпоследний уровень. А чтобы построить его — нужен уровень ниже». И так вы спускаетесь мысленно до самого фундамента, а потом возвращаетесь наверх, собирая результаты.
В программировании это реализуется через рекурсию. Мы начинаем с большой задачи и разбиваем её на всё более мелкие. Например, чтобы найти F(35), вызываем функцию для F(34) и F(33). Те, в свою очередь, вызывают функции для ещё меньших чисел. И так до базовых случаев F(0) и F(1).
Но здесь возникает проблема. Представьте дерево вызовов: чтобы вычислить F(35), нужно вычислить F(34) и F(33). Для F(34) нужны F(33) и F(32). Заметили? F(33) вычисляется дважды! А F(32) — ещё больше раз. Без дополнительных мер количество вычислений растёт экспоненциально.
Чтобы избежать этой катастрофы, используется мемоизация — техника запоминания уже вычисленных результатов. Каждый раз, когда функция вычисляет значение, оно сохраняется в специальный словарь или кеш. При повторном вызове с теми же аргументами функция просто возвращает сохранённый результат вместо повторного вычисления.
Вот как это выглядит на Python:
Нисходящий подход имеет ряд заметных преимуществ. Код получается естественным и напрямую следует логике рекуррентного соотношения — мы буквально переводим математическую формулу в программу. Кроме того, вычисляются только те подзадачи, которые действительно нужны для получения ответа, а не все подряд. Для сложных задач такой подход обычно легче писать и понимать.
Однако есть в нём и ряд недостатков. Рекурсивные вызовы функций создают накладные расходы, которые при большом количестве вызовов могут стать ощутимыми. При очень глубокой рекурсии возникает риск переполнения стека — проблема, с которой восходящий подход не сталкивается в принципе. Наконец, мемоизация требует аккуратности: нужно правильно выбрать структуру для хранения результатов и не забыть проверять, вычислено ли уже значение.
Восходящий подход (снизу вверх)
Теперь представьте, что башню вы начинаете строить с фундамента и кладёте кирпичи (или другие строительные блоки) уровень за уровнем, пока не доберётесь до вершины. Вы точно знаете, с чего начать (базовые случаи), и методично продвигаетесь к цели.
В программировании это реализуется через итерацию (циклы). Мы начинаем с самых простых случаев и постепенно строим решение для более сложных. В случае с числами Фибоначчи это значит: сначала вычислить F(0) и F(1), потом F(2), потом F(3) и так далее до F(35).
Для хранения результатов используется табулирование — заполнение таблицы (массива) значениями в определённом порядке. В отличие от мемоизации, где значения сохраняются по мере необходимости, здесь таблица заполняется систематически, от начала до конца.
В Python решение той же задачи на поиск F(35) с табулированием выглядит таким образом:
Здесь список dp — это наша «таблица». Мы заполнили первые два элемента известными значениями (базовые случаи), а потом в цикле вычислили все остальные. Чтобы получить 35-е число Фибоначчи, просто обращаемся к элементу dp[35].
Восходящий подход лишён проблем, связанных с рекурсией. Здесь нет накладных расходов на вызовы функций и невозможно переполнение стека — мы просто итерируемся по списку чисел. На практике это часто даёт выигрыш в скорости. Кроме того, восходящий подход открывает возможности для оптимизации памяти: если для вычисления текущего значения нужны только несколько предыдущих, можно хранить именно их, а все остальные просто отбрасывать за ненадобностью.
С другой стороны, восходящий подход требует заранее продумать порядок вычисления подзадач — мы должны гарантировать, что к моменту решения задачи все необходимые подзадачи уже решены. Для чисел Фибоначчи это очевидно: идём от меньших индексов к большим. Но для некоторых задач определить правильный порядок обхода бывает нетривиально. Ещё один нюанс: мы вычисляем все подзадачи подряд, даже если некоторые из них не понадобятся для итогового ответа — хотя в большинстве случаев это не проблема.
Итак, какой же подход выбрать?
В простых задачах, которые встречаются в ЕГЭ по информатике, мы будем использовать нисходящий подход: код короче, логика понятнее, легко следовать рекуррентному соотношению. Для более сложных задач, где важна производительность или где рекурсия может быть слишком глубокой, лучше отдать предпочтение табулированию— восходящему подходу.
Применение динамического программирования
Теперь разберём конкретную задачу, похожую на то, что бывает в задании 23 на ЕГЭ.
Представим такую задачу:
«У исполнителя есть две возможные операции:
1. Прибавить 3
2. Умножить на 2
Найдите количество способов преобразовать число 1 в число 8, используя сочетания этих двух команд»
Давайте сначала рассмотрим ручное решение через оба подхода, а в конце выведем код только одного из них, который мы и будем применять в дальнейшем для 23 заданий ЕГЭ.
Восходящий подход
При восходящем подходе мы начинаем с самого базового случая (единицы) и постепенно двигаемся к цели — числу 8.
Начинаем с единицы: у нас есть всего две команды — +3 и *2, распишем результаты их работы.
Если к 1 прибавить 3, получим 4, а если умножить на 2 — 2. Первый шаг сделали, идём дальше. Теперь для каждого получившегося числа — 4 и 2 — также вычисляем результаты применения этих двух команд:
- 4 + 3 = 7
- 4 * 2 = 8 (бинго!)
- 2 + 3 = 5
- 2 * 2 = 4
Нашли уже один путь из 1 в 8 (через команды +3 и *2). Но пока останавливаться рано: продолжаем применять эти команды к оставшимся трём числам:
- 7 + 3 = 10 (перебор)
- 7 * 2 = 14 (снова перебор)
- 5 + 3 = 8 (то, что нужно)
- 5 * 2 = 10 (опять перебрали)
- 4 + 3 = 7 (здесь мы уже были)
- 4 * 2 = 8 (есть!)
Получили еще два пути из 1 в 8:
- Через команды *2, +3 и +3
- Через три команды *2
В итоге получается, что для того, чтобы получить из единицы восьмёрку, используя только команды «Прибавить 3» и «Умножить на 2» есть всего три способа. Отметим их на рисунке ниже.
Что же, восходящим подходом решили задачу. Теперь попробуем второй.
Нисходящий подход
При нисходящем подходе мы начинаем с конечной цели и спускаемся к базовым случаям. Представьте, что вы стоите на вершине горы и прокладываете все возможные тропинки вниз.
На вершине горы у нас восьмёрка, а добраться нужно к единице. В этом подходе нам придётся использовать «обратные операции»:
- Отнять 3
- Разделить на 2
Действительно, мы же теперь движемся «сверху вниз», так что и операции должны быть также инвертированы.
Восьмёрку можно получить обоими операциями: умножить 4 на 2 или прибавить к 5 число 4. Продемонстрируем это на рисунке.
Теперь перед нами стоят следующие задачи:
- Найти все способы получить из 4 число 1
- Найти все способы получить из 5 число 1
Рассмотрим число 5. Получить целое число, поделив 5 на 2 мы не можем. Значит, остаётся только одна команда – отнять 3, в результате которой получим число 2.
Чтобы получить исходное число 1, у нас есть только один путь: поделить число 2 на 2.
Готово, мы нашли один путь, чтобы получить из 8 число 1.
Теперь вернёмся к четвёрке. Здесь можем сразу отнять 3 и получим число 1. Но также нам здесь доступна команда «разделить на 2», в результате которой получаем число 2.
Ну а к числу 2, как мы уже знаем, можно применить команду «разделить на 2».
Вот и всё, у нас снова те самые три способа получить из числа 1 число 8.
Давайте теперь переведём все наши рассуждения в более формальный вид.
Обозначим за f(x) — количество способов добраться из числа x до числа 1, используя обратные операции:
- Отнять 3 (обратная к «прибавить 3»)
- Разделить на 2 (обратная к «умножить на 2», только для чётных чисел)
Теперь определим базовые случаи и рекуррентное соотношение:
- Если x = 1: f(1) = 1 (дошли до цели)
- Если x < 1: f(x) = 0 (перескочили, путь не подходит)
- Иначе: f(x) = f(x-3) + f(x/2) (с учётом условий применимости)
Почему формула рекуррентного соотношения выглядит именно так?
Вспомним, что f(x) — это количество способов добраться из x до единицы. Из числа x мы можем сделать один шаг двумя способами: либо отнять 3 и оказаться в числе x-3, либо разделить на 2 и оказаться в числе x/2.
После этого шага нам останется добраться из нового числа до единицы — а это по определению f(x-3) или f(x/2) соответственно. Поскольку эти два варианта первого шага не пересекаются (мы либо отнимаем, либо делим, но не оба сразу), общее количество способов равно их сумме. Именно так и появляется формула f(x) = f(x-3) + f(x/2).
С этим разобрались, теперь вычисляем значения начиная с f(8):
f(8) = f(8-3) + f(8/2) = f(5) + f(4)
Далее вычислим f(5):
f(5) = f(5-3) + f(5/2)
= f(2) + 0 (5 нечётное, делить нельзя)
= f(2)
B f(2):
f(2) = f(2-3) + f(2/2)
= f(-1) + f(1)
= 0 + 1
= 1
Значит, f(5) будет равно 1. Таким образом, есть только 1 способ добраться из 8 к 1, через число 5. Вот этот момент с «через число» запомните!
Возвращаемся к первому выражению и вычисляем f(4). То есть ищем способы прийти к единице по траектории, которая содержит число 4:
f(4) = f(4-3) + f(4/2)
= f(1) + f(2)
= 1 + 1 (f(2) уже вычисляли ранее)
= 2
Останется лишь сложить два результата:
f(8) = f(5) + f(4) = 1 + 2 = 3
Вот мы и получили эти три способа, но уже математическим путём.
Программное решение
Если мы решаем эту задачу математически, значит, есть способ перенести все наши вычисления в программу.
Мы всё так же будем использовать нисходящий подход в решении, но будет одно важно отличие: инвертировать операции мы не будем! Сначала давайте выведем код, а потом разберём его.
Функция у нас будет принимать два числа:
- х — число, из которого мы движемся
- y — число, к которому движемся (наша цель)
То есть в нашем случае x = 1, а y = 8.
Вернёмся к выведенным ранее базовым случаям и рекуррентному соотношению:
- Если x = y: возвращаем 1 (дошли до цели, значит, путь есть)
- Если x > y: возвращаем 0 (перескочили, путь не подходит)
- Иначе (если x всё еще меньше y): f(x) = f(x+3) + f(x*2)
В коде это всё можно записать так:
Вот и всё! Осталось лишь вызвать эту функцию с аргументами x=1 и y=8:
В итоге получаем все то же число 3.
А уже в следующей статье мы научимся применять эту функцию для решения 23 заданий ЕГЭ по информатике.