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

Стоит сказать, что динамическое решение данной задачи более трудоемкое и занимает большее количество времени для исполнения. Поэтому рекомендуется использовать именно рекурсивную реализацию.

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

def f(st, fn, flag, flag_number, count, end_count):
    if st == fn and count == end_count and flag:
        return 1
    if st > fn or count > end_count:
        return 0
    if st == flag_number:
        flag = True
    x = f(st + 1, fn, flag, flag_number, count + 1, end_count)
    y = f(st * 2, fn, flag, flag_number, count + 1, end_count)
    z = f(st + st * 0.75, fn, flag, flag_number, count + 1, end_count) * \
(st % 8 == 0)
    return x + y + z
print(f(3, 50, False, 15, 0, 20))

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

ans = []
ans.append((3, 0))
for operations in range(20):
    can_get = []
    for i in ans:
        a, flag = i
        if a + 1 == 15:
            can_get.append((a + 1, 1))
        else:
            can_get.append((a + 1, flag))
        if a % 8 == 0:
            if int(a + a * 0.75) == 15:
                can_get.append((int(a + a * 0.75), 1))
            else:
                can_get.append((int(a + a * 0.75), flag))
        can_get.append((a * 2, flag))
    ans = can_get
otv = 0
for i in ans:
    a, flag = i
    if (a == 50) and (flag):
        otv += 1
print(otv)