Количество чисел у которых две соседние цифры различной четности

Задача

Найти количество чисел из $n$ разрядов, у которых все соседние цифры разной четности

Решение

1) $dp_{i, mod}$ - количество чисел из $i$ разрядов с четностью последней цифры - mod 2) База $dp_{1, 1} = 4, dp_{1, 0} = 1$ 3) $dp_{i, mod} = dp_{i - 1, 1 \bigoplus mod} \cdot 5$ 4) Порядок обхода - вперед 5) Ответ - $dp_{n, 0} + dp_{n, 1}$

Также можно подумать о комбинаторном решении задачи.