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

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

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

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

Последовательности без 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)$ ее легко посчитать.