АиСД L06 - Динамическое программирование

О чём лекция

Многие задачи сводятся к таким же задачам меньшего размера: число Фибоначчи — к двум предыдущим, путь кузнечика до клетки $N$ — к путям до $N-1$ и $N-2$. Если решать такие подзадачи рекурсией «в лоб», одни и те же значения пересчитываются экспоненциально много раз. Динамическое программирование считает каждую подзадачу один раз и складывает ответы в таблицу. Лекция показывает три способа считать Фибоначчи, серию задач на одномерную динамику, двумерную — на сочетаниях и разбиениях числа — и пример, где жадный алгоритм ошибается, а динамика нет.

Как читать

Доказательства и асимптотики в блоках «Не из лекции» дописаны к конспекту: на лекции их не было. Всё остальное — с доски.

Маршрут

1. Что такое ДП → Динамическое программирование
2. Числа Фибоначчи тремя способами → Рекурсия
3. Сравнение способов → Асимптотические оценки
4. Одномерная динамика: кузнечик, лесенка, панда
5. Двумерная динамика: число сочетаний
6. Сложная динамика: разбиения на слагаемые
7. Жадность против ДП → Жадный алгоритм

1. Определение

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

— @неизвестный автор

Примеры: MergeSort, Qsort, бинпоиск.

Это «разделяй и властвуй», а не ДП

Сортировка слиянием, Быстрая сортировка и Бинарный поиск действительно разбивают задачу на подзадачи, но подзадачи у них не повторяются: каждая половина массива сортируется один раз. Такой подход называют «разделяй и властвуй» (divide and conquer).

ДП нужно, когда подзадачи перекрываются — одна и та же встречается много раз, как $F_{n-2}$ в вычислении и $F_n$, и $F_{n-1}$. Тогда ответ выгодно запомнить. У сортировки слиянием запоминать нечего.

Не из лекции: из чего состоит решение динамикой

Все задачи лекции решаются по одной схеме:

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

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

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

$1,1,2,3,5,8,13,21,\dots$

Каждое число — сумма двух предыдущих.

Рекуррентная формула (инвариант ДП):

$F_n=F_{n-1}+F_{n-2}\forall n\ge 3$

Граничные условия: $F_1=1$, $F_2=1$.

1) Рекурсивный способ

функция fib(n)
    если n ≤ 2
        return 1
    иначе
        return fib(n − 1) + fib(n − 2)

Ответ: fib(n).

2) Табличный способ

table = [ ... ]
table[1] = table[2] = 1
for i = 3 ... N
    table[i] = table[i − 1] + table[i − 2]

Ответ: table[N].

3) Линейный способ

a = b = 1
c = 0
for i = 3 ... N
    c = a + b
    print(c)
    a = b
    b = c

c ← ответ.

Для следующего числа нужны только два предыдущих — их и хранят. На рисунке: A и B стоят на $f_1,f_2$, C = A + B даёт $f_3$, затем A = B, B = C — окно из двух чисел сдвигается вправо.

Не из лекции: граничный случай линейного способа

При $N=1$ и $N=2$ цикл не выполняется, и c остаётся 0, хотя $F_1=F_2=1$. Надёжнее отвечать b: после цикла это всегда $F_N$ при $N\ge 2$ (при $N=1$ — тоже 1).

Не из лекции: почему рекурсия здесь медленная

Вызов fib(n) вызывает fib(n − 1) и fib(n − 2), а fib(n − 1) снова вызывает fib(n − 2). Одни и те же значения пересчитываются заново.

Число вызовов. Пусть $C(n)$ — сколько вызовов делает fib(n). $C(1)=C(2)=1$, $C(n)=1+C(n-1)+C(n-2)$. Индукцией проверяется $C(n)=2F_n-1$: база $2\cdot 1-1=1$, переход $1+(2F_{n-1}-1)+(2F_{n-2}-1)=2F_n-1$. Проверено запуском: fib(30) = 832 040 делает 1 664 079 вызовов.

Сколько это. $F_n$ растёт как ${\phi }^n$, где $\phi =\frac{1+\sqrt{5}}{2}\approx 1,618$. Хватает и грубой оценки: $F_n=F_{n-1}+F_{n-2}\ge 2F_{n-2}$, значит, $F_n\ge 2^{(n-2)/2}$ — время рекурсии экспоненциальное.

Табличный и линейный способы считают каждое $F_i$ один раз: $O(N)$ времени. Память у таблицы $O(N)$, у линейного $O(1)$. У рекурсии память — глубина стека, $O(N)$.

3. Сравнение методов

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

Не из лекции: оценки за плюсами и минусами

	Время	Память
Рекурсивный	$\Theta ({\phi }^N)$ — экспонента	$O(N)$ на стек
Табличный	$O(N)$	$O(N)$ на таблицу
Линейный	$O(N)$	$O(1)$

«Хранение промежуточных данных» — плюс таблицы: после одного прогона известны все $F_1,\dots ,F_N$, и на много запросов можно отвечать сразу. Линейный способ помнит только последние два.

Рекурсию можно ускорить, не меняя её вида: запоминать уже посчитанные значения в таблице и не вызывать функцию повторно (мемоизация). Это ДП «сверху вниз», табличный способ — «снизу вверх».

4. Примеры

а) Кузнечик

Задача. Кузнечик прыгает на $+1$ или $+2$. Сколько способов добраться из 0 в $N$?

 ⌒⌒⌒⌒ ⌒ . . .     ⌒⌒ ▶
●───────────────────●────▶
0                   N

В клетку $N$ можно попасть только из $N-1$ (прыжок $+1$) или из $N-2$ (прыжок $+2$):

$F[N]=F[N-1]+F[N-2]$ $F[0]=1,F[1]=1$

Не из лекции: почему формула верна

Разделим все способы попасть в $N$ по последнему прыжку. Если он $+1$, до него кузнечик был в $N-1$ и попал туда любым из $F[N-1]$ способов. Если $+2$ — из $N-2$, $F[N-2]$ способов. Группы не пересекаются (последние прыжки разные) и покрывают всё — отсюда сумма.

$F[0]=1$: в 0 кузнечик уже стоит — один «пустой» путь. Без этого $F[2]$ вышло бы 1 вместо 2 (прыжки $1+1$ и $2$).

Это числа Фибоначчи со сдвигом: $F[N]=F_{N+1}$. Проверено: $F[5]=8$.

б) Кузнечик +1, +2, +3

$F[N]=F[N-1]+F[N-2]+F[N-3]$ $F[0]=F[1]=1,F[2]=2$

Нужны три граничных значения: формула заглядывает на три назад.

в) Лесенка

Задача: минимизировать сумму ударов плетью. На ступени $N$ — cost[N] ударов, шаг $+1$ или $+2$.

                 ▶
            2  ▄▄┃      ← ступень N
          7 ┃
        1 ┃
     3 ┃
   2 ┃
  ━━━┛

F[N] — накопительное значение: минимум ударов, чтобы встать на ступень $N$. На неё приходят с $N-1$ или $N-2$:

$F[N]=\min (F[N-1],F[N-2])+cost[N]$ $F[0]=0,F[1]=cost[1]$

cost[N] — сколько ударов на $N$-ой ступени.

Не из лекции: почему можно брать минимум

Оптимальный путь до $N$ приходит с $N-1$ или $N-2$, и его часть до предпоследней ступени — тоже оптимальный путь до неё: иначе её можно было бы заменить на более дешёвую и улучшить весь путь. Значит, $F[N]=\min (F[N-1],F[N-2])+cost[N]$.

Пример по рисунку (ступени снизу вверх, похоже, 2, 3, 1, 7, 2): $F=2,3,3,10,5$. Ответ 5: путь $0\to 1\to 3\to 5$ ($2+1+2$). Ступени с тремя и семью ударами перепрыгиваем.

Время $O(N)$, память $O(N)$, а если нужен только ответ — $O(1)$, как у линейного Фибоначчи.

г) Панда и пельмешки

Больше пельменей!!! Больших!

Та же лесенка, но теперь на ступенях пельмени и их нужно собрать как можно больше:

$F[N]=\max (F[N-1],F[N-2])+cost[N]$ $F[0]=0,F[1]=cost[1]$

Не из лекции

Если все cost положительные, задача вырождается: выгодно наступить на каждую ступень, и ответ — просто сумма. По рисунку $2+3+1+7+2=15$, и формула даёт то же. Интересной задача становится, когда бывают отрицательные значения — ступени, которые лучше перепрыгнуть.

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

Число сочетаний:

$C_n^k=\frac{n!}{k!(n-k)!},n!=1\cdot \dots \cdot n$

А) По формуле

$c(n,k)=n!/(k!\cdot (n-k)!)$

$n!$ — цикл, $O(n)$.

Б) Рекуррентно

$C_n^k=C_{n-1}^k+C_{n-1}^{k-1}$ $C_n^0=1,C_n^n=1$

функ. c(n, k)
    если k = 0 OR n = k
        return 1
    return c(n − 1, k) + c(n − 1, k − 1)

Не из лекции: зачем второй способ

Переполнение. Формула с факториалами считает огромные промежуточные числа: $21!>2^{63}$, и long long переполняется, хотя сам $C_{30}^{15}=155117520$ помещается даже в int. Рекуррентный способ только складывает, и промежуточные значения не больше ответа.

Почему формула верна. Выбираем $k$ предметов из $n$. Последний предмет либо не взят — тогда все $k$ выбраны из $n-1$ остальных ($C_{n-1}^k$), либо взят — тогда из остальных выбрано $k-1$ ($C_{n-1}^{k-1}$).

Почему «двумерная». Состояние — пара $(n,k)$, и таблица — двумерная: треугольник Паскаля. Но на доске записана рекурсия без таблицы, и она медленная по той же причине, что fib: вызовов $2C_n^k-1$. Проверено: $c(30,15)$ делает 310 235 039 вызовов. С таблицей table[i][j] = table[i−1][j] + table[i−1][j−1] по строкам $i=0\dots n$ — $O(nk)$ времени.

6. Сложная динамика

Разбиение на натуральные слагаемые. Сколькими способами представить число суммой натуральных чисел, если порядок не важен?

4 = 1 + 1 + 1 + 1
4 = 2 + 1 + 1 = 1 + 2 + 1 = 1 + 1 + 2
4 = 2 + 2
4 = 1 + 3
4 = 4

Строка 2 + 1 + 1 = 1 + 2 + 1 = 1 + 1 + 2 — это одно разбиение, записанное в разном порядке. Всего у 4 пять разбиений.

а) Одномерная попытка

F[k] — количество способов разбить число $k$:

$F[k]=1+F[k-1]+F[k-2]+\dots +F[1]$

Слагаемые подписаны как первое слагаемое разбиения: $+1$, $+2$, …, $+(k-1)$; единица — само $k$.

Учитываем порядок ⇒ не даёт ответ.

Не из лекции: что считает эта формула

Она считает упорядоченные суммы (композиции): $1+3$ и $3+1$ идут как разные. Из формулы $F[k]=2F[k-1]$, то есть $F[k]=2^{k-1}$. Для 4 выходит 8 вместо 5.

б) Двумерная

F[i][k] ← количество способов разбить $i$ на слагаемые, где максимальное слагаемое $=k$.

$F[i][k]=F[i-k][1]+F[i-k][2]+\dots +F[i-k][k]$

$F[i][k]=\{\begin{array}{ll}0,& i<k\\ 1,& i=k\end{array}$

Пример на доске: $5=\cancel{3}+2$, $i=5$, $k=3$. Убираем максимальное слагаемое 3, остаётся 2 — его разбиения с максимумом не больше 3.

Не из лекции: доказательство и ответ

Порядок перестаёт мешать, если записывать слагаемые по невозрастанию: каждое разбиение тогда записывается единственным образом.

Переход. Разбиение $i$ с максимумом ровно $k$ при $i>k$ — это $k$ плюс разбиение остатка $i-k$, у которого максимум $j\le k$. Наоборот, к любому такому разбиению остатка можно приписать $k$ — получится разбиение $i$ с максимумом $k$. Это взаимно однозначно, поэтому $F[i][k]={\sum }_{j=1}^{k}F[i-k][j]$.

База. $i<k$: максимум больше суммы — 0 способов. $i=k$: само число, один способ.

Ответ: разбиений числа $n$ всего ${\sum }_{k=1}^{n}F[n][k]$. Проверено запуском для $n=1\dots 10$: 1, 2, 3, 5, 7, 11, 15, 22, 30, 42.

Порядок и время. Строки по возрастанию $i$: $F[i][\cdot ]$ использует только меньшие $i-k$. Состояний $O(n^2)$, на каждое сумма из $O(n)$ слагаемых: $O(n^3)$. Если хранить префиксные суммы $S[i][k]=F[i][1]+\dots +F[i][k]$, переход занимает $O(1)$, и всё — $O(n^2)$.

7. Жадное программирование vs динамическое

Пример: номиналы монет, выдать клиенту сумму — меньше монет. 6 рублей, номиналы $\{15;4;3;1\}$.

Жадно:

1. сортируем по убыванию;
2. беру максимально, пока имеет смысл.

$6=4+1+1$

Динамика. Монеты $c_1,c_2,\dots ,c_k$. F[N] — количество монет:

$F[0]=0$ $F[N]=1+\min (F[N-c_1],F[N-c_2],\dots ,F[N-c_k])$

Не из лекции: в чём пример

На доске выписан только жадный ответ — три монеты. Динамика находит две: $6=3+3$. Проверено запуском: $F[6]=2$.

Жадный алгоритм берёт лучшее на текущем шаге (самую крупную монету) и никогда не пересматривает решение. Здесь первая же четвёрка портит ответ: остаток 2 набирается только единицами. Динамика перебирает все варианты последней монеты и берёт лучший — поэтому не ошибается.

Доказательство перехода. В оптимальном наборе для $N$ есть какая-то монета $c_i$, остальные — набор для $N-c_i$, и он тоже оптимален (иначе заменили бы его и улучшили весь). Перебрав все $c_i$, найдём лучший.

Детали. Минимум берётся только по $c_i\le N$; если сумму $N-c_i$ набрать нельзя, $F=\infty$. Время $O(N\cdot k)$.

Для обычных номиналов вроде $\{1,2,5,10\}$ жадность даёт оптимум, но это свойство конкретного набора, а не алгоритма. См. Жадный алгоритм.

Грабли

• Рекурсия без запоминания на перекрывающихся подзадачах — экспоненциальное время: fib(n), $c(n,k)$.
• Граничных условий столько, на сколько назад смотрит формула: у кузнечика $+1,+2,+3$ — три.
• $F[0]=1$ в задачах на число способов — пустой путь тоже способ.
• Линейный Фибоначчи с ответом c неверен при $N\le 2$.
• Одномерная динамика для разбиений считает упорядоченные суммы.
• Факториалы в формуле сочетаний переполняются задолго до ответа.
• Жадный выбор монет не всегда оптимален: $\{15,4,3,1\}$, сумма 6.
• MergeSort и бинпоиск — не ДП, а «разделяй и властвуй»: подзадачи не повторяются.

После этой лекции должно получаться

• объяснить, чем ДП отличается от простой рекурсии;
• посчитать $F_N$ тремя способами и сравнить их по времени и памяти;
• доказать, что рекурсивный fib экспоненциален;
• вывести формулу кузнечика через последний прыжок и объяснить $F[0]=1$;
• решить лесенку на минимум и на максимум;
• посчитать $C_n^k$ без переполнения;
• объяснить, почему разбиения нужно считать двумерной динамикой, и вывести формулу для F[i][k];
• показать набор монет, на котором жадность ошибается, и решить задачу динамикой.