Динамическое программирование в поиске чисел

#алгоритм #любой_язык #динамическое_программирование

На всех n-значных числах нужно посчитать кол-во таких чисел у которых любые две соседние
цифры имеют разность по модулю <= 1 
Допустим есть функция f(n) = кол-ву этих чисел 
Если для f(1) = 0, таких нет, для f(2) таких 8*3+2 (т.к. на промежутке 10-99 на всех
десятках есть по 3 таких числа, кроме числа начинающегося с 9 там их 2 т.к. оно крайнее,
например 10,11,12,21,22,23,32,33,34 ... 98,99.)
Получается что f(n) = f(n-1)*10 (т.к. если к изначально подходящему числу подставить
в конец любую цифру, то оно все равно удовлетворяет условию) + ..что то еще..
Долго не могу сложить этот пазл, как посчитать кол-во следующих n
    

Ответы

Ответ 1

Заполняем табличку. F - количество чисел длиной N, заканчивающихся цифрой L:

  F(N, L) {L=1..8} = F(N-1, L-1) + F(N-1, L) + F(N-1, L+1)
  F(N, 0) = F(N-1, 0) + F(N-1, 1)
  F(N, 9) = F(N-1, 9) + F(N-1, 8)
  F(1, 0) = 0
  F(1, K>0) = 1