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

Решение динамикой

a = [0] * (16 + 1)  # Создаем ячейки до конечного числа включительно
a[1] = 1  # Задаём начало в числе 1
for i in range(2, 16 + 1):
    a[i] = a[i - 1]  # В текущее число можно попасть командой +1
    if i % 2 == 0:  # Если в текущее число можно было попасть командой *2
        a[i] += a[i // 2]
print(a[16])

Решение рекурсией

def f(a):
    if a > 16:
        return 0
    if a == 16:
        return 1
    return f(a + 1) + f(a * 2)


print(f(1))

Решение руками

В четные числа мы можем попасть из числа деленного на 2 или предыдущего, а в нечетные только из предыдущих.
Получается, что в число 2 мы можем попасть из 1 двумя разными способами.
В число 3 мы можем попасть только из 2.
В число 4 мы можем попасть из 2 или 3.
В число 5 мы можем попасть только из 4.
И т.д.