Разбор добавил Дмитрий Бородий

Пусть d[i][k] - количество гладких чисел длины i и с цифрой k в конце. Тогда 

    d[i][j] = d[i - 1][j] + d[i - 1][j - 1] + d[i - 1][j + 1], j = [1..8];
    d[i][0] = d[i - 1][0] + d[i - 1][1];
    d[i][9] = d[i - 1][9] + d[i - 1][8].

Остается только задать начальные условия:

    d[1][1..9] = 1, d[1][0] = 0

а затем в цикле по i посчитать значения d[i][k].

Ответом будет сумма d[n][j] по j от 0 до 9 (количество гладких чисел длины n с
произвольной последней цифрой).