Задание 12 КЕГЭ: исполнитель с командами +N и ×N — как найти программу?

Это классическая задача на динамику «снизу вверх»: число способов получить n = сумма способов получить все его прообразы.

start, end = 3, 20
d = [0] * (end + 1)
d[start] = 1
for n in range(start + 1, end + 1):
    ways = 0
    if n - 1 >= start:          # последней была команда +1
        ways += d[n - 1]
    if n % 2 == 0:              # последней была команда *2
        ways += d[n // 2]
    d[n] = ways
print(d[end])

Идея: чтобы попасть в n, последний шаг был либо +1 (из n−1), либо ×2 (из n/2, если n чётное). Складываем способы добраться до этих предшественников. Если в условии есть «обязательно пройти через число K» — считаешь d[start→K] и d[K→end] и перемножаешь.