Динамическое программирование

Представьте, что вы стоите у подножия высокой лестницы и хотите узнать, сколькими способами можно подняться на сотую ступеньку, если за один шаг можно преодолеть либо одну, либо две ступени. Можно ли сразу дать ответ? Конечно, нет — задача кажется необъятной.

Но что, если начать с малого: сначала посчитать способы для первой ступеньки, потом для второй, третьей… и так постепенно добраться до сотой? Именно в этом и заключается суть динамического программирования.

В задании 13 ЕГЭ по информатике проверяется умение анализировать работу алгоритма с ветвлениями и циклами. На практике это почти всегда сводится к подсчёту количества способов получить одно число из другого с помощью заданных команд. И здесь на сцену выходит динамическое программирование.

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

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

Что такое динамическое программирование

Слово «программирование» в этом термине может сбить с толку. Здесь оно означает не написание программы на Python, а планирование последовательности решений.

Метод развивал американский математик Ричард Беллман в начале 1950-х годов, когда работал в исследовательской корпорации RAND. Учёных интересовали задачи, в которых нужно принять целую цепочку связанных решений, а не сделать один удачный ход.

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

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

Суть динамического программирования проста: если перед вами стоит сложная задача, которую невозможно решить напрямую, разбейте её на несколько простых подзадач. Решите эти подзадачи, сохраните результаты и используйте их для получения финального ответа. Звучит логично, но есть важный нюанс: подзадачи должны быть устроены одинаково и решаться по единому алгоритму.

Например, вы не можете сразу сказать, сколько способов есть преобразовать число 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.

Сделаем небольшое лирическое отступление. Мы уже несколько раз произнесли имя Фибоначчи, но пока знаем о нём лишь одну формулу. Откуда взялась эта последовательность и почему она стала классическим примером в программировании?

Фибоначчи — это прозвище Леонардо Пизанского, итальянского математика, жившего на рубеже XII–XIII веков. В юности он учился в Северной Африке и познакомился там с удобной позиционной системой записи чисел.

В 1202 году Леонардо написал «Книгу абака» — Liber Abaci. Несмотря на название, книга была не только о счётной доске (она называется «абак» и схожа с нашими счётами, а описывали её работу мы вот в этой статье): эта книга объясняла европейским читателям индийско-арабские цифры и показывала, как применять их в торговле, обмене валют и практических расчётах.

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

В первый месяц есть одна пара. Затем всё ещё одна, потом две, три, пять, восемь. Чтобы узнать число пар в новом месяце, нужно сложить число взрослых пар, уже живших месяц назад, и молодых пар, появившихся месяцем раньше.

Так возникает последовательность 1, 1, 2, 3, 5, 8, 13, 21… В современной записи часто добавляют нулевой элемент и получают 0, 1, 1, 2, 3, 5, 8… Обе записи описывают одну закономерность; различается лишь точка, с которой начинается нумерация.

Важно и то, что Леонардо не был первым человеком, заметившим такую последовательность: похожие правила встречались у индийских математиков задолго до него. Но именно «Книга абака» сделала задачу известной в Европе, поэтому за рядом закрепилось имя Фибоначчи.

Числа Фибоначчи появляются в алгоритмах, комбинаторике и моделях роста. В природе с ними связывают расположение листьев и спиралей семян, хотя здесь важно не превращать красивую закономерность в миф: живые формы лишь приближённо следуют математическим моделям.

Для программиста эта последовательность особенно удобна. Формула проста, но наивная рекурсия многократно вычисляет одни и те же значения. Например, F(33) понадобится и для F(35), и внутри вычисления F(34). Именно здесь становится заметна польза памяти.

Поэтому Фибоначчи для нас — не декоративная историческая вставка, а уменьшенная модель задания 13. Вместо месяцев будут числа на экране, вместо рождения новых пар — команды исполнителя, а вместо F(n) — количество траекторий до цели.

Где применяется динамическое программирование

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

Числа Фибоначчи. С ними мы уже знакомы: 0, 1, 1, 2, 3, 5 и так далее. Первые 6 чисел довольно просто вспомнить. А попробуйте сразу назвать 35-е число этого ряда. Не получается? Правильно, потому что для его вычисления нужно знать вообще все предыдущие числа. Вот здесь и пригодится динамическое программирование.

Задачи про роботов. Представьте робота на клетчатом поле, который может двигаться только вправо или вниз (что-то напоминает, правда?). Сколько разных путей у него есть, чтобы добраться из левого верхнего угла в правый нижний? Прямой перебор всех вариантов займёт вечность, а динамическое программирование решит задачу за секунды. Такие задачи встречаются в информатике постоянно: меняются только правила переходов и ограничения на клетки.

Преобразование чисел. А это уже как раз то, что встречается в задании 13 на экзамене. Есть число, есть набор операций (например, «прибавить 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) — ещё больше раз. Без дополнительных мер количество вычислений растёт экспоненциально.

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

Название происходит от латинского memoria — «память». Функция словно оставляет себе записку: «F(20) уже найдено, вот ответ». Когда то же значение понадобится снова, она читает записку, а не повторяет весь расчёт.

Вот как это выглядит на Python:

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(35))

>>> 9227465

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

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

Восходящий подход (снизу вверх)

Теперь представьте, что башню вы начинаете строить с фундамента и кладёте кирпичи (или другие строительные блоки) уровень за уровнем, пока не доберётесь до вершины. Вы точно знаете, с чего начать (базовые случаи), и методично продвигаетесь к цели.

В программировании это реализуется через итерацию (циклы). Мы начинаем с самых простых случаев и постепенно строим решение для более сложных. В случае с числами Фибоначчи это значит: сначала вычислить F(0) и F(1), потом F(2), потом F(3) и так далее до F(35).

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

В Python решение той же задачи на поиск F(35) с табулированием выглядит таким образом:

def fibonacci(n):
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

print(fibonacci(35))
>>>9227465

Здесь список dp — это наша «таблица». Мы заполнили первые два элемента известными значениями (базовые случаи), а потом в цикле вычислили все остальные. Чтобы получить 35-е число Фибоначчи, просто обращаемся к элементу dp[35].

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

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

Итак, какой же подход выбрать?

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

Применение динамического программирования

Теперь разберём абстрактную задачу, похожую на то, что бывает в задании 13 на ЕГЭ.

Представим такую задачу:

«У исполнителя есть две возможные операции:
1. Прибавить 3
2. Умножить на 2

Найдите количество способов преобразовать число 1 в число 8, используя сочетания этих двух команд»

Давайте сначала рассмотрим ручное решение через оба подхода, а в конце выведем код только одного из них, который мы и будем применять в дальнейшем для 13 заданий ЕГЭ.

Восходящий подход

При восходящем подходе мы начинаем с самого базового случая (единицы) и постепенно двигаемся к цели — числу 8.

Начинаем с единицы: у нас есть всего две команды — +3 и ×2, распишем результаты их работы.

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

1. 4 + 3 = 7
2. 4 × 2 = 8 (бинго!)
3. 2 + 3 = 5
4. 2 × 2 = 4

Нашли уже один путь из 1 в 8 (через команды +3 и ×2). Но пока останавливаться рано: продолжаем применять эти команды к оставшимся трём числам:

1. 7 + 3 = 10 (перебор)
2. 7 × 2 = 14 (снова перебор)
3. 5 + 3 = 8 (то, что нужно)
4. 5 × 2 = 10 (опять перебрали)
5. 4 + 3 = 7 (здесь мы уже были)
6. 4 × 2 = 8 (есть!)

Получили ещё два пути из 1 в 8:

1. Через команды ×2, + 3 и +3
2. Через три команды ×2

В итоге получается, что для того, чтобы получить из единицы восьмёрку, используя только команды «Прибавить 3» и «Умножить на 2», существует всего три способа. Отметим их на рисунке ниже.

Что же, восходящим подходом решили задачу. Теперь попробуем второй.

Нисходящий подход

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

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

1. Отнять 3
2. Разделить на 2

Действительно, мы же теперь движемся «сверху вниз», так что и операции должны быть также инвертированы.

Восьмёрку можно получить обоими операциями: умножить 4 на 2 или прибавить 3 к числу 5. Продемонстрируем это на рисунке.

Теперь перед нами стоят следующие задачи:

1. Найти все способы добраться от 4 до 1
2. Найти все способы добраться от 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)

Вычислим 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

Вот мы и получили те же самые три способа, но уже математическим путём.

Программное решение

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

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

Функция у нас будет принимать два числа:

1. х — число, из которого мы движемся
2. y — число, к которому движемся (наша цель)

То есть в нашем случае x = 1, а y = 8.

Вернёмся к выведенным ранее базовым случаям и рекуррентному соотношению:

• Если x = y: возвращаем 1 (дошли до цели, значит, путь есть)
• Если x > y: возвращаем 0 (перескочили, путь не подходит)
• Иначе (если x всё ещё меньше y): f(x) = f(x+3) + f(x*2)

В коде это всё можно записать так:

def f(x, y):
    if x == y:
        return 1

    if x > y:
        return 0

    if x < y:
        return f(x + 3, y) + f(x * 2, y)

Вот и всё! Осталось лишь вызвать эту функцию с аргументами x=1 и y=8:

def f(x, y):
    if x == y:
        return 1
    if x > y:
        return 0
    return f(x + 3, y) + f(x * 2, y)

print(f(1, 8))
>>>3

В итоге получаем всё то же число 3.

Итоги

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

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

Числа Фибоначчи показали главную проблему наивной рекурсии: одинаковые состояния возникают в разных ветвях. Кеширование устраняет повторные вычисления и делает рекурсивную запись пригодной для практики.

В задании 13 вершинами нашего мысленного графа становятся числа, а рёбрами — команды исполнителя. Если дошли до цели, возвращаем 1; если перескочили её, возвращаем 0; иначе складываем ответы всех допустимых продолжений.

В следующей статье рассмотрим алгоритм решения реальных 13 заданий ЕГЭ по информатике, а заодно разделим их по типам.