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

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

def f(start, finish, limits, visited):
    if (start == finish):
        return 1
    if (start < limits[0]) or (start > limits[1]):
        return 0
    if (start in visited):
        return 0
    vis = visited.copy()
    vis.add(start)
    x = f(start + 4, finish, limits, vis)
    y = f(start - 5, finish, limits, vis)
    return x + y
print(f(1, 20, (-20, 40), set()))

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

ans = []
ans.append((1, set([1])))
otv = 0
for operations in range(1000):
    can_get = []
    for i in ans:
        a, vis = i
        vis_first = vis.copy()
        vis_second = vis.copy()
        if a == 20:
            otv += 1
            continue
        if ((a + 4) in vis) == 0 and (a + 4 <= 40):
            vis_first.add(a + 4)
            can_get.append((a + 4, vis_first))
        if ((a - 5) in vis) == 0 and (a - 5 >= -20):
            vis_second.add(a - 5)
            can_get.append((a - 5, vis_second))
    if len(can_get) == 0:
        break
    ans = can_get
print(otv)