«Олимпиадное программирование» - курс для начинающих

Псевдодвумерное динамическое программирование — это такой тип задач, в которых уже не достаточно одномерного массива для хранения результатов, а нужен двумерный массив, но при этом одна из его размерностей мала, например, равна двум. В таком случае бывает удобно не заводить двумерный массив, а завести два одномерных массива. Также в таких задачах, как правило, заполнение значений происходит в одномерном цикле.

Задача. Даны два целых числа n>0$n>0$ и 2≤k≤10$2\le k\le 10$. Требуется найти количество последовательностей длины n$n$, которые состоят из цифр от 0$0$ до k−1$k-1$ и в которых нет двух подряд идущих нулей.

Пусть dp[i][0]$dp[i][0]$ — это количество последовательностей длины i$i$, которые заканчиваются на цифру 0$0$, а dp[i][1]$dp[i][1]$ — это количество последовательностей длины i$i$, которые заканчиваются не на цифру 0$0$. Таким образом, мы имеем массив dp[i][j],$dp[i][j],$ у которого вторая размерность равна двум.

Начинаем заполнение с последовательностей длины один:

dp[1][0]=1$dp[1][0]=1$

dp[1][1]=k−1$dp[1][1]=k-1$

Далее для всех значений i≥2$i\ge 2$ можно записать формулы пересчёта:

dp[i][0]=dp[i−1][1]$dp[i][0]=dp[i-1][1]$

dp[i][1]=(k−1)⋅(dp[i−1][0]+dp[i−1][1])