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

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

Мы используем функцию f(x, y), которая возвращает количество программ, преобразующих число x в число y.

1. Если x > y, возвращаем 0, так как число превысило цель и путь невозможен.

2. Если x == y, возвращаем 1, так как найден один корректный путь.

3. В остальных случаях количество программ равно сумме двух рекурсивных вызовов:

- f(x + 1, y) — применение команды «прибавь 1»;

- f(x + 4, y) — применение команды «прибавь 4».

Использование декоратора @lru_cache позволяет кэшировать уже вычисленные значения, ускоряя рекурсию.

from functools import lru_cache

# Декоратор для кэширования результатов рекурсии
@lru_cache
def f(x, y):
    # Если текущее число больше целевого, путь невозможен
    if x > y:
        return 0
    # Если текущее число равно целевому, найден один путь
    if x == y:
        return 1
    # Суммируем количество программ для двух команд: +1 и +4
    return f(x + 1, y) + f(x + 4, y)

# Выводим количество программ для преобразования числа 1 в 128
print(f(1, 128))

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

Создаём массив num, где num[i] — количество способов получить число i от числа .

1. Инициализируем num[1] = 1, так как стартовое число имеет один способ «быть» в нём.

2. Для чисел от до :

- прибавляем num[i-1] для команды «прибавь 1»;

- если , прибавляем num[i-4] для команды «прибавь 4».

После заполнения массива значение num[128] покажет количество всех программ.

# Создаем массив для динамического программирования
num = [0] * 129
# Начальная точка (число 1) имеет один способ
num[1] = 1
# Заполняем массив для чисел от 2 до 128
for i in range(2, 129):
    # Количество способов через команду +1
    num[i] = num[i - 1]
    # Если число >= 5, добавляем путь через команду +4
    if i >= 5:
        num[i] += num[i - 4]
# Выводим количество программ для числа 128
print(num[128])