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

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

def f(a, b):
    if a == b:
        return 1
    if a < b:
        return 0
    return f(a - 1, b) + f(a - 3, b) + f(a // 3, b)

print(f(22, 2))

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

a = [0] * 70
a[22] = 1
for i in range(21, 1, -1):
    a[i] = a[i + 1] + a[i + 3] + a[i * 3] + a[i * 3 + 1] + a[i * 3 + 2]
print(a[2])

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

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