Skip to content

Latest commit

 

History

History
482 lines (327 loc) · 23.8 KB

dp-basics.md

File metadata and controls

482 lines (327 loc) · 23.8 KB
Raw

Динамическое программирование — базовые понятия

  • Общие принципы
  • Одномерная динамика: кузнечик
  • Двумерная динамика: черепашка
  • Восстановление ответа в динамике

Общие принципы

Рассмотрим такую задачу: найти N-е число Фибоначчи.

Числа Фибоначчи определяются так: $F_0 = 0, F_1 = 1, F_n = F_{n-2} + F_{n-1}$.

Эту задачу можно решить рекурсивно:

def fibonacchi(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacchi(n - 2) + fibonacchi(n - 1)

print fibonacchi(20)

6765

Однако это будет работать очень долго. 20-е число посчитать еще можно будет, а 40-е число - нет. И не потому, что числа большие. А потому, что мы будем делать слишком много лишней работы. Число операций будет экспоненциально относительно $N$.

Почему? Потому что, чтобы посчитать N-е число, нам нужно будет независимо посчитать (N-1)-е число и (N-2)-е число, и это в минимум в два раза больше действий, чем нужно для (N-2). А значит, для подсчета N-го числа Фибоначчи необходимо 2 раза посчитать (N-2)-е число, и это занимает в два раза больше времени, а значит это хотя бы $2^\frac{N}{2}$ действий.

Это ну слишком долго, и главное, что это легко исправляется. Давайте просто не считать лишних действий - если мы один раз посчитали $F_k$, то давайте запомним, чему оно равно, и в следующий раз, когда оно нам понадобится, мы используем его сразу. Удобнее всего сохранить числа Фибоначчи прямо в массиве:

N = 20

fib = [None] * (N + 1) # создали массив из None от 0 до N включительно
fib[0] = 0 
fib[1] = 1 # заполнили изначальные позиции
for i in range(2, N + 1): # обходим массив по порядку слева направо
    fib[i] = fib[i - 2] + fib[i - 1] # формула считает новое число через предыдущие!

print fib[N] # ответ лежит на N-ом месте

6765

И этот способ легко работает для больших $N$, так как работает за $O(N)$ - всего один проход по массиву (правда здесь ответ мы будем считать по модулю $10^9$, потому что иначе числа получатся слишком слишком большими):

N = 200000

fib = [0] * (N + 1)
fib[1] = 1
for i in range(2, N + 1):
    fib[i] = (fib[i - 2] + fib[i - 1]) % (10 ** 9)

print fib[N]

175853125

Это и называется динамическим программированием (или динамикой, ДП). Основная идея состоит в том, чтобы

  • свести задачу для $N$ к задаче для чисел, меньших, чем $N$ (с помощью формулы)
  • хранить все ответы в массиве
  • заполнить начало массива вручную (для которых формула не работает)
  • обойти массив и заполнить ответы по формуле
  • вывести ответ откуда-то из этого массива

Чтобы решить задачу по динамике вы должны ответить на 5 вопросов:

  • Что лежит в массиве? (самый важный вопрос чаще всего)
  • Как инициализировать начало массива?
  • Как обходить массив? (чаще всего слева направо, но не всегда)
  • Какой формулой считать элементы массива?
  • Где в массиве лежит ответ?

Одномерная динамика: кузнечик

Рассмотрим такую задачу:

Есть полоска $1\times N$, кузнечик стоит на первой клетке, он может прыгать вперед на 1, 2, 3 клетки. Сколько есть способов добраться от начальной клетки до последней?

Как решать такие задачи? Нужно придумать рекуррентную формулу, как ответ для N зависит от ответа для меньших чисел.

Очень помогает посмотреть на маленькие числа (!! одна из самых важных идей для придумывания решений):

Пусть dp[x] - это количество способов добраться от 1 клетки до клетки номер x.

  • dp[1] = 1 способ (стоять на месте)
  • dp[2] = 1 способ ($1 \rightarrow 2$)
  • dp[3] = 2 способа ($1 \rightarrow 2 \rightarrow 3$ и $1 \rightarrow 3$)
  • dp[4] = 4 способа ($1 \rightarrow 2 \rightarrow 3 \rightarrow 4$ и $1 \rightarrow 3 \rightarrow 4$ и $1 \rightarrow 2 \rightarrow 4$ и $1 \rightarrow 4$)
  • dp[5] = 7 способов ($1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5$ и $1 \rightarrow 3 \rightarrow 4 \rightarrow 5$ и $1 \rightarrow 2 \rightarrow 4 \rightarrow 5$ и $1 \rightarrow 4 \rightarrow 5$ и $1 \rightarrow 2 \rightarrow 3 \rightarrow 5$ и $1 \rightarrow 3 \rightarrow 5$ и $1 \rightarrow 2 \rightarrow 5$)

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

Какой последний прыжок кузнечика в его пути до N-й клетки? Один из трех вариантов:

  • $(N - 1) \rightarrow N$
  • $(N - 2) \rightarrow N$
  • $(N - 3) \rightarrow N$

То есть все пути до $N$ разбиваются на 3 группы. Причем мы знаем сколько путей в каждой группе. В первой из них ровно dp[N - 1] путей - столько путей идут до (N-1)-й клетки, и дальше идет еще один прыжок. Во второй и третьей группах поэтому тоже dp[N - 2] и dp[N-3] путей.

Так что формула получается такой: dp[N] = dp[N - 3] + dp[N - 2] + dp[N - 1].

Очень похоже на числа Фибоначчи, да? Можете посмотреть на числа, которые мы уже выписали, там все отлично подходит:

dp[4] = 4 = 1 + 1 + 2 = dp[1] + dp[2] + dp[3]

dp[5] = 7 = 1 + 2 + 4 = dp[2] + dp[3] + dp[4].

Так что программа пишется легко:

N = 20
dp = [0] * (N + 1)
dp[1] = 1
dp[2] = 1
dp[3] = 2
for i in range(4, N + 1):
    dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1]
print(dp)

[0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012]

Давайте изменим немного задачу: Теперь некоторые из клеток закрыты. То есть нам известно про конкретные клетки, что на них кузнечик прыгать не может. Тогда задача все еще решается так же, только нужно убедиться, что dp[x] = 0 для всех запрещенных x!

Также немного перепишем код, чтобы не писать отдельно случаи для 2 и 3, а также чтобы не писать в формуле сумму трех чисел (а представьте, что в задаче не 3, а 100). Будем инициализировать только dp[1]. А ко всем следующим значениям dp[i] будет прибавлять dp[i - k], где k = 1, 2, 3. Причем, если i - k < 1, то мы будем игнорировать такие клетки, и этим самым мы избавились от необходимости прописывать ответ для dp[2] и dp[3].

N = 20
BAD_CELLS = [2, 3, 6, 13]

dp = [0] * (N + 1)
is_bad = [0] * (N + 1)
for bad in BAD_CELLS:
    is_bad[bad] = 1
print(is_bad)

[0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]

if not is_bad[1]: 
    dp[1] = 1
for i in range(2, N + 1):
    if not is_bad[i]:
        for k in range(1, 4):
            if i - k >= 1:
                dp[i] += dp[i - k]
print(dp)

[0, 1, 0, 0, 1, 1, 0, 2, 3, 5, 10, 18, 33, 0, 51, 84, 135, 270, 489, 894, 1653]

Двумерная динамика: черепашка

Теперь рассмотрим такую задачу:

На каждой клетке двумерной таблички написано, сколько там лежит монет. Черепашка стоит в клетке 1x1 (верхней левой), и может двигаться только на одну клетку вниз, или на одну клетку вправо. Нужно найти максимальное число монет, которое может набрать черепашка по пути к нижней правой клетке NxM.

Первое, что приходит в голову - это просто идти черепашкой в ту клетку из соседних, где лежит больше монет. К сожалению, эта жадная стратегия не всегда работает. Например, на такой доске жадная черепашка пошла бы по следу из единичек, хотя гораздо выгоднее пойти сначала по нулям, а потом найти там большие горстки монет (40, 70, 100):

COINS = [
    [0,   1,   1,   1,   1,   1],
    [0,   0,   0,   0,   0,   1],
    [0,   40,  70,  0,   0,   1],
    [100, 0,   0,   0,   0,   1]
]
N = 4
M = 6

Тут нас снова спасает динамика. Давайте сводить задачу к предыдущей! Задачей назовем "сколько максимально монет можно набрать на пути от $0\times0$ до $i\times j$" (заменим 1-нумерацию на 0-нумерацию). Будем хранить это в двумерном массиве dp в клетке dp[i][j].

Сразу понятны некоторые свойства этого массива:

  • Он размера NxM
  • dp[0][0] = COINS[0][0]
  • ответ на всю задачу лежит в dp[N - 1][M - 1]

Но гораздо важнее придумать формулу для подсчета dp[i][j] через предыдущие. Легко посчитать первую строку и первый столбец:

  • dp[0][k] = dp[0][k - 1] + COINS[0][k]
  • dp[k][0] = dp[k - 1][0] + COINS[k][0]

Так как до этих клеток есть ровно один путь.

Но что делать, если есть много путей до клетки dp[i][j]? Снова разобьем их на на несколько групп в зависимости от последнего хода (! важный трюк, запомните). Последний ход был:

  • либо из [i][j - 1]
  • либо из [i - 1][j]

Поэтому формула для максимального числа монет такая: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + COINS[i][j].

Ну все, достаточно пройтись правильно по двумерному массиву (построчно сверху вних, а в каждой строке слева направо) и заполнить этот массив.

dp = [[None] * M for i in range(N)]

for i in range(N):
    for j in range(M):
        if i == 0 and j == 0:
            dp[0][0] = COINS[0][0]
        elif i == 0:
            dp[0][j] = dp[0][j - 1] + COINS[0][j]
        elif j == 0:
            dp[i][0] = dp[i - 1][0] + COINS[i][0]
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + COINS[i][j]
    print(dp[i])

[0, 1, 2, 3, 4, 5]
[0, 1, 2, 3, 4, 6]
[0, 41, 111, 111, 111, 112]
[100, 100, 111, 111, 111, 113]

В отличие от жадного алгоритма, динамическое программирование находит оптимальное решение - это, в данном случае, 113 монет.

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

В последней задаче было здорово найти, что в оптимальном пути черепашки набирается 113 монет, но интересно, что именно это за путь. Такую задачу называют восстановлением ответа в динамике.

Есть два способа, которыми можно это сделать.

  1. Хранить в массив prev откуда ты пришел в эту клетку.

Когда мы выбираем максимум из левой и верхней клетки, мы на самом деле решаем, какой последний ход будет в оптимальном пути до этой клетки - сверху или слева, и берем ответ для той клетки, сложнный с монетами в этой клетке. Давайте координаты клетки, откуда мы пришли, хранить в массиве prev. Или, в данном случае, можно хранить не координаты а просто 1, если пришли слева, и 0, если пришли сверху.

dp = [[None] * M for i in range(N)]
prev = [[None] * M for i in range(N)]

for i in range(N):
    for j in range(M):
        if i == 0 and j == 0:
            dp[0][0] = COINS[0][0]
            prev[0][0] = -1 # это самое начало, предыдущей клетки нет
        elif i == 0:
            dp[0][j] = dp[0][j - 1] + COINS[0][j]
            prev[0][j] = 0 # слева пришли
        elif j == 0:
            dp[i][0] = dp[i - 1][0] + COINS[i][0]
            prev[i][0] = 1 # сверху пришли
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + COINS[i][j]
            if dp[i - 1][j] > dp[i][j - 1]:
                prev[i][j] = 1
            else:
                prev[i][j] = 0
    print(prev[i])

[-1, 0, 0, 0, 0, 0]
[1, 1, 1, 1, 1, 1]
[1, 1, 0, 0, 0, 0]
[1, 0, 1, 0, 0, 1]

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

i, j = N - 1, M - 1
answer = []
answer_directions = []
while i > 0 or j > 0:
    if prev[i][j] == 1:
        i -= 1
        answer_directions.append('DOWN')
    else:
        j -= 1
        answer_directions.append('RIGHT')
    answer.append((i, j))
print answer[::-1] # reverse
print answer_directions[::-1] # reverse

[(0, 0), (0, 1), (1, 1), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5)]
['RIGHT', 'DOWN', 'DOWN', 'RIGHT', 'RIGHT', 'RIGHT', 'RIGHT', 'DOWN']
  1. Вместо хранения массива prev догадаться по массиву dp, откуда именно черепашка пришла в эту клетку.

В данном примере это довольно легко. Если мы уже посчитали весь массив dp, то теперь можно начиная с конца легко понять, пришла черепашка туда сверху или слева в оптимальном маршруте - она пришла из клетки с максимальным числом монет.

i, j = N - 1, M - 1
answer = []
answer_directions = []
while i > 0 or j > 0:
    if i != 0 and (j == 0 or dp[i - 1][j] > dp[i][j - 1]):
        i -= 1
        answer_directions.append('DOWN')
    else:
        j -= 1
        answer_directions.append('RIGHT')
    answer.append((i, j))
print answer[::-1] # reverse
print answer_directions[::-1] # reverse

[(0, 0), (0, 1), (1, 1), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5)]
['RIGHT', 'DOWN', 'DOWN', 'RIGHT', 'RIGHT', 'RIGHT', 'RIGHT', 'DOWN']

Задание

Решите как можно больше задач из простого контеста:

https://informatics.msk.ru/mod/statements/view.php?id=33233#1

А также решите как можно больше задач из сложного контеста:

https://informatics.msk.ru/mod/statements/view.php?id=35808#1

Разбор еще нескольких задач

Давайте разберем еще несколько задач.

Последовательности без 3 единиц подряд

Условие:

Определите количество последовательностей из нулей и единиц длины $N$, в которых никакие три единицы не стоят рядом.

Решение:

Давайте хранить в $dp[N]$ ровно число таких последовательностей длины $N$ (это первое, что должно приходить в голову).

Давайте посмотрим для начала для маленьких чисел:

  • $dp[0] = 1 (\text{пустая последовательность})$
  • $dp[1] = 2 (0, 1)$
  • $dp[2] = 4 (00, 01, 10, 11)$
  • $dp[3] = 7 (000, 001, 010, 011, 100, 101, 110)$
  • $dp[4] = 13 (0000, 0001, 0010, 0011, 0100, 0101, 0110, 1000, 1001, 1010, 1011, 1100, 1101)$

Сходу закономерность можно не увидеть. Нужно догадаться сгруппировать эти числа по том, сколько в конце единичек. Например, для dp[4]:

  • 0 единичек в конце: $0000, 0010, 0100, 0110, 1000, 1010, 1100$ - их ровно семь, как для $N=3$, потому что первые 3 числа могут быть любые (но без трех единиц подряд), а четвертое - 0
  • 1 единичка в конце: $0001, 0101, 1001, 1101$ - их ровно четыре, как для $N=2$, потому что первые 2 числа могут быть любые (но без 3 единиц подряд), а два последних - 01
  • 2 единички в конце: $0011, 1011$ - их ровно две, как для $N=1$, потому что первое число может быть любым (но без 3 единиц подряд), а три последних - 011

Так мы замечаем и доказываем формулу: $dp[N] = dp[N-1] + dp[N-2] + dp[N-3]$

Теперь за $O(N)$ ее легко посчитать.

Лесенки

Условие:

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

Решение:

Если считать, что $dp[N]$ - это число лесенок из $N$ кубиков, то никакой закономерности скорее всего найти не получится.

  • $dp[1] = 1$
■
  • $dp[2] = 1$
■ ■
  • $dp[3] = 2$
■
■ ■
■ ■ ■
  • $dp[4] = 2$
■
■ ■ ■
■ ■ ■ ■
  • $dp[5] = 3$
■ ■
■ ■ ■
■
■ ■ ■
■ ■ ■ ■ ■
  • $dp[6] = 4$
■
■ ■
■ ■ ■
■ ■
■ ■ ■ ■
■
■ ■ ■
■ ■ ■ ■ ■ ■

По числам построить закономерность сложно, и по самим лесенкам тоже. Не видно какого-то рассуждения вида "ко всем лесенкам размера N-1 можно положить на любой слой еще один кубик", иногда ведь и нельзя.

Тут нам помогает введение дополнительного параметра. Нас просят решить одномерную задачу (для $N$), а мы решим двумерную задачу для $n$ и $m$. Давайте зафиксируем размер самого нижнего слоя и назовем его размер $m$.

То есть $dp[n][m] = $"число лесенок, состоящих из $N$ кубиков, таких, что самый нижний слой состоит из $M$ кубиков".

Как это связано с нашей задачей? Ответ на нашу задачу равен $dp[N][1] + dp[N][2] + \ldots + dp[N][N]$.

Какая есть формула для такой постановки задачи? Размер нижнего слоя у нас зафиксирован и равен $m$, осталость $n-m$ кубиков на верхних слоях. Логично перебрать размер второго снизу слоя, который может быть любым от $1$ до $m-1$: $dp[n][m] = dp[n-m][1] + dp[n-m][2] + \ldots + dp[n-m][m-1]$

Это все пир условии, что $n \geq m$. Иначе $dp[n][m] = 0$.

Теперь осталось понять как инициализировать этот массив и аккуратно по нему пройтись. Давайте инициализируем его ровно для случая $n=0, m=0$:

$dp[0][0]$ = 1

Пройдемся по массиву сначала для всех m при n = 1, потому для всех m при всех n = 2 и так далее - то есть по строчкам обычными двумя циклами $for$.

Для $m &gt; 0$ в ячейках $dp[0][m]$ наш алгоритм будет работать и возвращать 0, так как $n &lt; m$.

Для всех $n &gt; 0$ наша формула будет находить ответ через числа с меньшим n, а значит алгоритм корректен.

Он заполняет табличку размера $N^2$, обрабатывая каждую клетку за $O(N)$ операций, итоговое время работы - $O(N^3)$.