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

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

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

def f(st, fn, count_2, count_3):
    if st == fn and count_3 > count_2:
        return True
    if st > fn:
        return False
    x = f(st + 3, fn, count_2, count_3)
    y = f(st * 2, fn, count_2 + 1, count_3)
    z = [0] * 10
    for i in range(10):
        z[i] = f(st * 10 + i, fn, count_2, count_3 + 1)
    return x + y + sum(z)
print(f(1, 48, 0, 0))

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

ans = set()
ans.add((1, 0, 0))  # (куда пришли, сколько раз использовали вторую команду, раз использовали третью команду)
otv = 0
for operations in range(1000):
    can_get = set()
    for i in ans:
        a, cnt_2, cnt_3 = i
        if (a == 48) and (cnt_2 < cnt_3):
            otv += 1
            continue
        if a + 3 <= 48:
            can_get.add((a + 3, cnt_2, cnt_3))
        if a * 2 <= 48:
            can_get.add((a * 2, cnt_2 + 1, cnt_3))
        for j in range(9):
            new_numb = int(str(a) + str(j))
            if new_numb <= 48:
                can_get.add((new_numb, cnt_2, cnt_3 + 1))
    if len(can_get) == 0:
        break
    ans = can_get
print(otv)