23.01 Количество программ из A в B

Решение 1 (Рекурсия)

Определим функцию f(a, b), которая будет вызывать саму себя. Она подсчитает количество программ, преобразующих число a в b. Функция возвращает:

• 0, если a > b
• 1, если a == b, так как единица означает, что мы нашли путь, который число А может превратить в число B выполнив все условия задачи;
• сумму значений для двух возможных переходов (+1 и +10), если a < b, так как такая траектория еще не нарушила условия задачи и может стать подходящей.

# Функция для подсчета количества программ преобразования a -> b
def f(a,b):
if a>b: # Если начальное число больше конечного, то возвращаем 0
return 0
if a==b: # Начальное число равно конечному числу - Возвращаем 1
return 1
# Иначе делаем все возможные варианты
return f(a + 1, b) + f(a + 10, b)
# Выводим результат
print(f(12,36))

Решение 2 (Динамика)

a = [0] * 37 # Создаем список длины 37 с нулями
a[12] = 1
# 12 это наше начало, значит в него прийти можно только одним способом (ставим 1)
# Перебираем все числа от 13 до 36 включительно
for i in range(13, 37):
    # Добавляем к нашему a[i] значения а[i-1] и a[i-10]
    # Если a[i] можно получить шагами +1 и +10, то a[i] увеличивается
    a[i] += a[i - 1]
    a[i] += a[i - 10]
print(a[36]) # Выводим результат