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

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

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

Главная идея: если один и тот же результат нужен несколько раз, достаточно найти его один раз и запомнить.

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

Из чего состоит решение

Для построения решения нужно определить четыре вещи:

1. Состояние — что именно мы будем вычислять и сохранять.

2. Начальные значения — ответы для самых простых случаев, которые можно указать сразу.

3. Переходы — правило, по которому ответ для одного состояния вычисляется через ответы для других.

4. Порядок вычислений — последовательность, в которой нужные для переходов ответы уже будут известны.

Пример: числа Фибоначчи

Рассмотрим последовательность, в которой первые два числа равны 0 и 1, а каждое следующее равно сумме двух предыдущих:

Обозначим число с номером $n$ через $F(n)$. Нумерацию начнём с нуля. Тогда:

Для всех $n\geq 2$ выполняется:

Например, чтобы найти $F(5)$, достаточно знать $F(4)$ и $F(3)$и так далее:

Заполним таблицу по порядку:

Здесь состояние — число $F(n)$, начальные значения — 0 и 1, переход — сложение двух предыдущих значений. Вычисления выполняем по возрастанию номера.

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

Подсчёт программ исполнителя

Теперь применим тот же принцип к задаче ЕГЭ. Пусть исполнитель умеет прибавлять 2 и прибавлять 5. Требуется найти количество программ, которые преобразуют число 1 в число 21.

Обозначим через $D(n)$ количество программ, которые преобразуют число 1 в число $n$.

В число 1 можно попасть одним способом — не выполнить ни одной команды. Поэтому:

Для чисел меньше 1 количество способов равно нулю: обе команды увеличивают число.

Рассмотрим последнее действие программы. Чтобы получить число $n$, перед последней командой на экране должно находиться либо $n-2$, либо $n-5$. Значит, для чисел больше начального:

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

Заполним таблицу слева направо. Под каждым числом запишем количество способов его получить:

Например, в число 8 можно попасть из 6 или 3: получаем $1+1=2$ способа. В число 21 — из 19 или 16: получаем $16+7=23$ программы.

Как учитывать другие команды и ограничения

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

Если команда прибавляет 1, учитываем способы попасть в $n-1$. Если умножает на 3, учитываем $n/3$, но только когда $n$ делится на 3. Если возводит в квадрат, учитываем $\sqrt{n}$, но только когда корень является целым допустимым числом.

Разные команды считаем отдельно, даже если они дают одинаковый результат. Например, из 2 можно получить 4 как прибавлением 2, так и возведением в квадрат. Это две разные программы.

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

Если программа не должна проходить через число $k$, количество способов в этой точке приравниваем к нулю:

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

Если программа обязательно должна пройти через число $k$, отдельно считаем программы от начального числа до $k$ и от $k$ до конечного числа. Затем перемножаем результаты:

Каждую программу первой части можно продолжить любой программой второй части. Такое разбиение применяем в задачах, где число строго изменяется в одном направлении и повторно попасть в $k$ невозможно.

Реализация через список

Вернёмся к задаче с командами «Прибавить 2» и «Прибавить 5». Таблицу можно хранить в списке: индекс элемента будет обозначать число на экране, а значение элемента — количество способов получить это число.

d = [0] * 22
d[1] = 1
for i in range(2, 22):
    if i - 2 >= 1: d[i] += d[i - 2]
    if i - 5 >= 1: d[i] += d[i - 5]
print(d[21])

Список d содержит 22 элемента с индексами от 0 до 21. В d[1] записываем 1 — начальное количество способов. Затем последовательно заполняем элементы от d[2] до d[21]. Для каждого числа добавляем количества способов попасть в его допустимых предшественников. Проверки i - 2 >= 1 и i - 5 >= 1 исключают числа меньше начального и обращение по отрицательным индексам. В d[21] получаем 23.

Переход к рекурсивному решению

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

Рекурсия — это вызов функцией самой себя для решения более простой подзадачи.

Пусть $f(x,end)$ возвращает количество программ, которые преобразуют текущее число $x$ в конечное число $end$.

Если $x=end$, цель достигнута: возвращаем 1. Если $x>end$, цель превышена: возвращаем 0, поскольку обе команды только увеличивают число.

В остальных случаях первая команда программы может прибавить 2 или прибавить 5. Рассматриваем оба продолжения и складываем количества программ:

В таблице мы рассматривали, откуда можно прийти в текущее число. В рекурсивной функции рассматриваем, куда можно перейти из текущего числа.

Получаем следующее решение на Python:

def f(x, end):
    if x > end: return 0
    if x == end: return 1
    return f(x + 2, end) + f(x + 5, end)
print(f(1, 21))

Функция f(x, end) сначала проверяет условия остановки. При x > end возвращает 0, при x == end — 1. В остальных случаях вызов f(x + 2, end) считает программы, начинающиеся с прибавления 2, а f(x + 5, end) — с прибавления 5. Сумма этих результатов даёт общее количество программ. Вызов f(1, 21) возвращает 23.

При этом обычная рекурсия может несколько раз вычислять ответ для одного и того же состояния.

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

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