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

Способ 1 · рекурсия с запоминанием

# Считаем динамикой «с конца»: f(x, goal) — число программ,
# переводящих x в goal и не проходящих через запрещённое число 7.
from functools import lru_cache

BAN = 7              # это число на траектории запрещено

@lru_cache(None)     # запоминаем уже посчитанные значения
def f(x, goal):
    if x == goal:                # цель достигнута — это одна программа
        return 1
    if x < goal or x == BAN:     # ниже цели или запрет — программ нет
        return 0
    # команды: A — вычесть 1, B — вычесть 4, C — взять целую часть от деления на 3
    return f(x - 1, goal) + f(x - 4, goal) + f(x // 3, goal)

# Обязательное число 13 делит путь на два участка: 19→13 и 13→2.
print(f(19, 13) * f(13, 2))

Вставить код в песочницу

Способ 2 · обход чисел от старта вниз

# ways[x] — число программ, ведущих из старта a в число x.
# Все команды уменьшают число, поэтому идём от старта вниз.
BAN = 7

def count(a, b):
    ways = {a: 1}                 # из a в a ведёт одна (пустая) программа
    for x in range(a, b - 1, -1): # от старта к цели по убыванию
        if x == BAN or x not in ways:
            continue              # запрещённое число пропускаем
        for y in (x - 1, x - 4, x // 3):
            if y >= b:            # ниже цели уходить нельзя
                ways[y] = ways.get(y, 0) + ways[x]
    return ways.get(b, 0)         # сколько путей дошло до цели

# Обязательное 13: пути через него = (19→13) × (13→2).
print(count(19, 13) * count(13, 2))

Вставить код в песочницу