Одномерное ДП

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

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

Есть полоска $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].

Очень похоже на числа Фибоначчи, да?

1 dp[1] = 1
2 dp[2] = 1
3 dp[3] = 2
4 for (int i = 4; i <= N; i++) {
5     dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
6 }

Давайте изменим немного задачу: Теперь некоторые из клеток закрыты. То есть нам известно про конкретные клетки, что на них кузнечик прыгать не может. Тогда задача все еще решается так же, только нужно убедиться, что 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].

 1 if (can[1]) { 
 2     dp[1] = 1;
 3 }
 4 for (int i = 2; i <= N; i++) {
 5     if (can(i)) {
 6         for (int k = 1; k <= 3; k++) {
 7             if (i - k >= 1) {
 8                 dp[i] += dp[i - k];
 9             }
10         }
11     }
12 }

Лесенки

- Условие:**

Лесенкой называется набор кубиков, в котором каждый горизонтальный слой содержит меньше кубиков, чем слой под ним. Подсчитать количество различных лесенок, которые могут быть построены из 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 > 0$ в ячейках $dp[0][m]$ наш алгоритм будет работать и возвращать 0, так как $n < m$. Для всех $n > 0$ наша формула будет находить ответ через числа с меньшим n, а значит алгоритм корректен. Он заполняет табличку размера $N^2$, обрабатывая каждую клетку за $O(N)$ операций, итоговое время работы - $O(N^3)$.