У исполнителя Абоба две команды, которым присвоены номера:
1. Прибавь 1
2. Увеличь число десятков на 1
Например: при помощи команды 2 число 23 преобразуется в 33. Если перед выполнением команды 2 вторая с конца цифра равна 9, она не изменяется. Сколько есть программ, которые число 11 преобразуют в число 27?
Решение рекурсией:
def f(a, b):
if a > b:
return 0
if a == b:
return 1
return f(a + 1, b) + f(a + 10, b)
print(f(11, 27))
Решение динамикой:
a = [0] * 28
a[11] = 1
for i in range(12, 28):
a[i] = a[i-1] + a[i-10]
print(a[27])