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

Решение рекурсией:

def f(x, y):
    if x > y:
        return 0
    if x == y:
        return 1
    return f(x + 2, y) + f(x * 10, y)

print(f(2, 40))

Решение динамикой:

a = [0] * 100
a[2] = 1
for i in range(3, 41):
    a[i] = a[i - 2]
    if i % 10 == 0:
        a[i] += a[i // 10]
print(a[40])

Решение аналитикой:

Количество программ, которые преобразуют число 2 в число n, обозначим . Число 2 у нас уже есть, значит, его можно получить с помощью “пустой” программы. Любая непустая программа увеличит исходное число, т.е. даст число, больше 2. Значит, . Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Если число не делится на десять, то оно может быть получено только из предыдущего с помощью команды прибавь 2. Значит, количество искомых программ для такого числа равно количеству программ для предыдущего возможного числа: .
Если число делится на 10, то вариантов последней команды два: прибавь 2 и умножь на 10, тогда . Заполним таблицу по данной формуле:

Отсюда получаем искомое количество программ - 3.