23.02 Количество программ из A в B (на убывание)

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

def f(st, fn):
    if st == fn:
        return 1
    if st < fn:
        return 0
    x = f(st // 3, fn) * (st % 3 == 0)
    y = f(st // 2, fn) * (st % 2 == 0)
    z = f(st - 3, fn)
    return x + y + z
print(f(30, 3))

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

a = [0] * 31
a[30] = 1
for i in range(30, 1, - 1):
    a[i - 3] += a[i]
    a[i // 2] += a[i] * (i % 2 == 0)
    a[i // 3] += a[i] * (i % 3 == 0)
print(a[3])

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

a = [0] * 100
a[30] = 1
for i in range(29, 2, -1):
    a[i] = a[i + 3] + a[i * 3] + a[i * 2]
print(a[3])