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

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

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

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