Динамика по подотрезкам

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

#Кузнечик

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

Попытаемся придумать рекуррентную формулу — то есть вывести, как ответ для $n$ зависит от ответа для меньших чисел.

Пусть $f[k]$ равно количеству способов добраться от 1 клетки до клетки номер $k$ . Попытаемся руками посчитать несколько его первых значений:

$f[1] = 1$ способ (стоять на месте)
$f[2] = 1$ способ:

1 \rightarrow 2

$f[3] = 2$ способа:

\begin{aligned} 1 \rightarrow 2 \rightarrow 3 \\ 1 \rightarrow 3 \end{aligned}

$f[4] = 4$ способа:

\begin{aligned} 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \\ 1 \rightarrow 3 \rightarrow 4 \\ 1 \rightarrow 2 \rightarrow 4 \\ 1 \rightarrow 4 \end{aligned}

$f[5] = 7$ способов:

\begin{aligned} 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 \end{aligned}

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

Давайте подумаем, каким мог быть последний прыжок кузнечика в его пути до $n$ -й клетки? Один из трёх вариантов:

$(n - 1) \rightarrow n$
$(n - 2) \rightarrow n$
$(n - 3) \rightarrow n$

То есть все пути до $n$ разбиваются на 3 группы, и причём мы знаем сколько путей в каждой группе: в первой из них ровно $f[n-1]$ путей — столько путей идут до $(n-1)$ -й клетки, и дальше идет еще один прыжок; аналогично, во второй и третьей группах $f[n-2]$ и $f[n-3]$ путей соответственно.

Просуммировав число путей во всех трёх группах, получаем

f[n] = f[n-3] + f[n-2] + f[n-1]

Очень похоже на числа Фибоначчи, да? На самом деле, если бы кузнечик мог прыгать только на 1 или 2 клетки вперед, ответом было бы в точности $n$ -ое число Фибоначчи.

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

f[0] = 1
f[1] = 1
f[2] = 2
for (int i = 3; i < n; i++)
    f[i] = f[i - 3] + f[i - 2] + f[i - 1];

Примечание. Такая последовательность называется числами трибоначчи.

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

#Кузнечик с препятствиями

Немного изменим задачу: теперь некоторые из клеток закрыты, то есть нам известно про какие-то конкретные клетки, что на них кузнечик прыгать не может.

Тогда задача все еще решается такой же рекурсивной формулой, только нужно убедиться, что $f[k] = 0$ для всех запрещенных $k$ .

Так как нам нужно добавить в реализацию такую проверку, немного отрефакторим код, чтобы не рассматривать прыжок каждого размера по отдельности, а также будем инициализировать только $f_1$ :

// a -- булевый массив, свободна ли i-ая клетка

f[0] = a[0];

for (int i = 1; i < n; i++)
    for (int j = i; j > max(i - 3, 0); j--)
        // f[i] изначально заполнены нулями
        f[i] += f[j] * a[j];

Заметим, что такая реализация масштабируется на любую длину прыжка $k$ . Асимптотика будет $O(n k)$ .

#Число подпалиндромов

Палиндромом называется последовательность символов $a_i$ длины $n$ , для которой выполняется $a_i = a_{n-i}$ .

Требуется для данной строки размера $n$ определить, сколько её подстрок являются палиндромами.

Заведем динамику $f[l, r]$ , равную единице, если подстрока с $l$ по $r$ является палиндромом, и нулем в противном случае. Посчитав её, мы найдем все подстроки-палиндромы в исходной строке, и для ответа сможем просто просуммировать все ячейки этой динамики.

Определение палиндрома можно альтернативно сформулировать так: строка $s$ является палиндромом, если $s_0 = s_n$ и строка $s_{1\ldots n - 1}$ является палиндромом. Такое определение и будем использовать для пересчета динамики:

f[l, r] = (s_l = s_r) \land f[l + 1, r - 1]

Заведем двумерный массив для хранения динамики и пройдемся по базовым случаям: подстрокам размера 1, всегда являющимися палиндромами, и подстрокам размера 2, являющимися палиндромами если первый символ равен второму. Для остальных состояний будем пользоваться формулой выше.

Единственный нюанс — порядок обхода. Нельзя просто проходиться фориком сначала в порядке увеличения $l$ , а потом увеличения $r$ , потому что пересчет зависит от динамик с большими $l$ . Вместо этого будем итерироваться по размеру подстроки $d = r - l + 1$ , а затем перебирать все подстроки с таким размером. Тогда для любой подстроки динамика для $f[l + 1][r - 1]$ уже будет посчитана.

bool f[n][n];

for (int i = 0; i < n; i++) {
    f[i][i] = true;
    f[i][i + 1] = (s[i] == s[i + 1]);
}

for (int d = 3; d <= n; d++)
    for (int l = 0, r = l + d - 1; r < n; l++, r++)
        f[l][r] = (s[l] == s[r]) && f[l + 1][r - 1];

int ans = 0;
for (int l = 0; l < n; l++)
    for (int r = l; r < n; r++)
        ans += f[l][r];

Альтернативно, можно проходиться в порядке уменьшения $l$ и увеличения $r$ . Также базовым состоянием для палиндромов четного размера можно выбрать «подстроки размера ноль», всегда являющиеся палиндромами, выполнив в цикле f[i][i - 1] = true — либо тогда уже просто инициализировать весь массив динамик единицами и начинать с $d=2$ :

memset(f, 1, sizeof f);

for (int l = n - 1; l >= 0; l--)
    for (int r = l + 1; r < n; r++)
        f[l][r] = (s[l] == s[r]) && f[l + 1][r - 1];

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