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

Динамическое программирование (dynamic programming, ДП) решает задачу через подзадачи меньшего размера и считает каждую подзадачу один раз, запоминая ответы в таблице.

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

Зачем нужно

Рекурсивная формула часто сама просится в код: $F_n=F_{n-1}+F_{n-2}$. Но если подзадачи перекрываются, прямая Рекурсия пересчитывает одни и те же значения: fib(n − 2) вызывают и fib(n), и fib(n − 1). Число вызовов растёт экспоненциально. ДП заменяет повторный счёт чтением из таблицы — время становится полиномиальным.

Как работает

Не из лекции: схема

1. Состояние — что хранится в F[N].
2. Переход — формула через меньшие состояния (на доске — инвариант ДП).
3. База — граничные условия.
4. Порядок вычисления — так, чтобы нужное уже было посчитано.
5. Ответ — какое состояние отвечает на вопрос.

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

Три способа на Фибоначчи

$F_n=F_{n-1}+F_{n-2}$, $F_1=F_2=1$.

fib(n):  если n ≤ 2: return 1
         return fib(n − 1) + fib(n − 2)          // рекурсивный
 
table[1] = table[2] = 1                          // табличный
for i = 3 ... N: table[i] = table[i − 1] + table[i − 2]
 
a = b = 1                                        // линейный
for i = 3 ... N: c = a + b; a = b; b = c

	Память	Время	Простота	Хранение промежуточных данных
Рекурсивный	±	−	+	−
Табличный	−	±	±	+
Линейный	+	+	−	−

Не из лекции

Рекурсивный — $\Theta ({\phi }^N)$ времени (вызовов ровно $2F_N-1$), табличный — $O(N)$ времени и памяти, линейный — $O(N)$ времени и $O(1)$ памяти. Промежуточный вариант — мемоизация: та же рекурсия, но посчитанные значения запоминаются, и повторный вызов сразу возвращает ответ. Это ДП «сверху вниз», таблица — «снизу вверх».

Одномерная динамика

Задача	Переход	База
Кузнечик $+1,+2$: число способов	$F[N]=F[N-1]+F[N-2]$	$F[0]=F[1]=1$
Кузнечик $+1,+2,+3$	$F[N]=F[N-1]+F[N-2]+F[N-3]$	$F[0]=F[1]=1$, $F[2]=2$
Лесенка: минимум ударов	$F[N]=\min (F[N-1],F[N-2])+cost[N]$	$F[0]=0$, $F[1]=cost[1]$
Панда: максимум пельменей	$F[N]=\max (F[N-1],F[N-2])+cost[N]$	$F[0]=0$, $F[1]=cost[1]$
Монеты: минимум монет	$F[N]=1+{\min }_{i}F[N-c_i]$	$F[0]=0$

Двумерная динамика

Состояние — пара чисел, таблица двумерная.

• Сочетания: $C_n^k=C_{n-1}^k+C_{n-1}^{k-1}$, $C_n^0=C_n^n=1$.
• Разбиения на слагаемые: F[i][k] — число разбиений $i$ с максимальным слагаемым ровно $k$: $F[i][k]=F[i-k][1]+\dots +F[i-k][k]$; $F[i][k]=0$ при $i<k$, $1$ при $i=k$.

Одномерная попытка для разбиений $F[k]=1+F[k-1]+\dots +F[1]$ учитывает порядок слагаемых и не даёт ответ. Второе измерение («максимальное слагаемое») фиксирует порядок — слагаемые по невозрастанию.

Тонкости

• ДП — не любое «разбить на подзадачи». У сортировки слиянием и бинарного поиска подзадачи не повторяются: это «разделяй и властвуй». На лекции они названы примерами ДП, см. конспект.
• Рекурсия по формуле ДП без таблицы — тоже экспонента: на доске $C_n^k$ записано именно так.
• Граничных условий нужно столько, насколько далеко назад заглядывает формула.
• В задачах на число способов $F[0]=1$: пустой путь — один способ.
• ДП находит оптимум там, где Жадный алгоритм ошибается: он перебирает все варианты последнего шага, а не только лучший на вид.

Частые ошибки

• Писать рекурсию по формуле и не запоминать ответы.
• Забыть граничное условие или задать его неверно ($F[0]=0$ вместо 1 в подсчёте способов).
• Считать в неправильном порядке — обращаться к ещё не посчитанной ячейке.
• Выбрать состояние, которое не различает нужное: одномерные разбиения считают $1+3$ и $3+1$ дважды.