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

Введение

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

Обычно этот подход используют в задачах с вопросами:

Сколько существует способов/последовательностей? - подсчет числа комбинаторных объектов
За какое минимальное/максимальное число шагов/денег можно что-то сделать? - оптимизация

Можно заметить, что при решении в лоб эти задачи бы имели экспоненциальную асимптотику ( $O(n2^n)$, $O(n!)$ и тд) полного перебора.

Динамическое программирование позволяет решать такие задачи за полином ( $O(n)$, $O(nm)$, $O(n^2)$ и тд)

Числа Фибоначчи

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

Мы знаем, что по определению $f[0] = f[1] = 1$, $f[n] = f[n - 1] + f[n - 2]$.

Введем следующую терминологию:

База динамики - это ответы на задачу для состояний, которые нельзя разбить на более простые. В этом примере, $f[0] = f[1] = 1$.
Переход - рекуррентная формула, по которой можно посчитать текущие состояние через предыдущие - $f[n] = f[n - 1] + f[n - 2]$.
Ответ на задачу - это состояние, где хранится ответ. В этом примере это $f[n]$.

Напишем код

f = [1, 1] + [0] * (n - 2)
for i in range(2, n):  # пересчитываем, начиная с i = 2, так как f[0] = f[1] = 1 - база динамики
    f[i] = f[i - 1] + f[i - 2]

print(f[-1])

План решения задач на ДП

Есть $n$ клеточек. Чтобы побывать в $i$-ой клетке, нужно заплатить $a[i]$ монет. Кузнечик начинает в первой клетке и хочет попасть в последнюю. Он умеет прыгать на одну или две клетки вперед. За какое минимальное число монет он сможет это сделать?

Сформулировать, что будет хранить каждое состояние.

Например, $dp[i]$ - минимальное число монет, чтобы дойти до клетки $i$.
Найти формулу перехода.

Например, $dp[i] = a[i] + min(dp[i - 1], dp[i - 2])$, где $a[i]$ - число штраф в монетах, чтобы пройти через клетку $i$.
Определить порядок пересчета.

Для нашего примера это $i = 1..n$. В задачах с двумерной динамикой (поговорим о них в следующие разы) это может быть не так тривиально.
Задать значения базы динамики.

Например, $dp[0] = a[0]$, $dp[1] = a[0] + a[1]$.
Понять, где лежит ответ.

Например, $dp[n]$.

Задача “Калькулятор”

Теперь мы рассмотрим данный подход на примере задачи “Калькулятор”.

Условие

Дано натуральное число $n \leq 10^6$. Имеется калькулятор с экраном, отображающим одно число, и тремя функциями:

Прибавить $1$ к числу на экране.

Умножить его на $2$.

Умножить его на $3$.

Изначально на его экране написано число $1$.

Требуется узнать, за какое минимальное число операций можно получить $n$.

Решение

Заведём массив $dp[n]$ такой, что $dp[i]$ - ответ на задачу для числа $i$.

Как нам посчитать $dp[n]$?

Нетрудно догадаться, что $dp[n] \leq dp[n - 1] + 1$, потому что мы всегда можем получить $n$, сначала получив $n - 1$, а затем прибавив $1$.

Если $n$ делится на $2$, то из тех же соображений $dp[n] \leq dp \left[ \dfrac{n}{2} \right] + 1$.

Аналогично: если $n$ делится на $3$, то $dp[n] \leq dp \left[ \dfrac{n}{3} \right] + 1$.

Таким образом $dp[n] = \min\left( dp[n - 1], dp \left[ \dfrac{n}{2} \right], dp \left[ \dfrac{n}{3} \right] \right) + 1$, где второе и третье число учитывается только если $n$ делится нацело.

Последний шаг: $dp[1] = 0$, потому что это число у нас уже есть с самого начала и нам не надо делать ничего.

Как же теперь написать код?

Исходя из описанных выше идей возникает желание написать рекурсивный алгоритм.

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

Поэтому мы пойдём другим путём: будем считать динамику с помощью цикла.

Реализация

n = int(input())
dp = [0] * (n + 1)
for i in range(2, n + 1):
    dp[i] = dp[i - 1] + 1
    if i % 3 == 0 and dp[i // 3] + 1 < dp[i]:
        dp[i] = dp[i // 3] + 1
    if i % 2 == 0 and dp[i // 2] + 1 < dp[i]:
        dp[i] = dp[i // 2] + 1
print(dp[n])

Асимптотика

Исходя из реализации очевидно, что асимптотика - $O(n)$.

Восстановление ответа

Пусть теперь нас просят вывести не количество, а оптимальную последовательность операций.

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

В конце пройдёмся по массиву предков, каждый раз переходя из текущего числа в его предка и добавляя соответствующую операцию в ответ, пока не дойдём до $1$.

Реализация

n = int(input())

dp = [0] * (n + 1)
p = [0] * (n + 1)
for i in range(2, n + 1):
    dp[i] = dp[i - 1] + 1
    p[i] = i - 1
    if i % 3 == 0 and dp[i // 3] + 1 < dp[i]:
        dp[i] = dp[i // 3] + 1
        p[i] = i // 3
    if i % 2 == 0 and dp[i // 2] + 1 < dp[i]:
        dp[i] = dp[i // 2] + 1
        p[i] = i // 2

ans = []
cur = n
while cur != 1:
    if p[cur] + 1 == cur:
        ans.append(1)
    elif p[cur] * 2 == cur:
        ans.append(2)
    else:
        ans.append(3)
    cur = p[cur]

print(*reversed(ans), sep='')

Асимптотика

Сначала - $O(n)$ на поиск ответа, потом - в худшем случае $O(n)$ на восстановление, итого - $O(n)$.