23.08 Прочие прототипы

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

Мы используем рекурсивную функцию , которая считает количество программ, переводящих текущую координату в конечную . Идея такова:

1. Если текущие координаты совпадают с конечными , то найден один путь, возвращаем 1. 2. Если текущие координаты превышают конечные по или , путь невозможен, возвращаем 0. 3. В остальных случаях мы рассматриваем все возможные действия: - Увеличиваем на 2 и рекурсивно считаем пути из - Умножаем на 2 и рекурсивно считаем пути из - Двигаемся вверх на все возможные значения от 1 до и суммируем пути из для каждого

Мы используем lru_cache для мемоизации, чтобы повторные вызовы с одинаковыми координатами не вычислялись заново. Рекурсивный вызов f((1,2),(12,19)) вернет общее количество программ.

# Импортируем декоратор для кеширования результатов рекурсии
from functools import lru_cache

# Определяем рекурсивную функцию f(st, fn), где st - текущие координаты, fn - конечные
@lru_cache(None)
def f(st, fn):
    # Если достигли конечной точки, возвращаем 1
    if st == fn:
        return 1
    # Если текущие координаты вышли за пределы конечных, возвращаем 0
    if st[0] > fn[0] or st[1] > fn[1]:
        return 0
    # Считаем количество программ при увеличении X на 2
    c1 = f((st[0] + 2, st[1]), fn)
    # Считаем количество программ при умножении X на 2
    c2 = f((st[0] * 2, st[1]), fn)
    # Создаем список для подсчета вариантов движения вверх
    c = [0] * (fn[1] - st[1] + 1)
    # Перебираем все возможные вертикальные перемещения вверх
    for i in range(1, fn[1] - st[1] + 1):
        c[i] = f((st[0], st[1] + i), fn)
    # Суммируем все возможные варианты
    return c1 + c2 + sum(c)

# Вычисляем и выводим количество программ от (1,2) до (12,19)
print(f((1, 2), (12, 19)))

—

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

Мы создаем двумерный массив , где и — координаты, а — количество программ, ведущих из начальной точки в .

1. Инициализируем массив нулями и присваиваем , так как стартуем из точки (1,2) одним способом. 2. Проходим по всем координатам от 1 до 12 и от 2 до 19: - Если , добавляем к - Если , добавляем к - Для вертикального движения перебираем все координаты от до 19 и добавляем к

3. После завершения всех итераций хранит количество программ, ведущих в конечную точку.

# Создаем двумерный массив для координат от 0 до 12 по X и от 0 до 19 по Y
dp = [[0] * 20 for i in range(13)]
# Инициализация стартовой точки
dp[1][2] = 1
# Перебираем все координаты X
for x in range(1, 13):
    # Перебираем все координаты Y
    for y in range(2, 20):
        # Если можно увеличить X на 2, добавляем количество программ
        if x + 2 < 13:
            dp[x + 2][y] += dp[x][y]
        # Если можно умножить X на 2, добавляем количество программ
        if x * 2 < 13:
            dp[x * 2][y] += dp[x][y]
        # Перебираем вертикальные перемещения вверх
        for to in range(y + 1, 20):
            dp[x][to] += dp[x][y]

# Выводим количество программ, ведущих из (1,2) в (12,19)
print(dp[12][19])