Исполнитель Щелчок очень хочет быть похожим на исполнителя Робота, поэтому учится двигаться по прямоугольной системе координат. У исполнителя есть три команды:
1. Прибавить 2 к координате X ((1, 2) 
(3, 2))
2. Умножить координату X на 2 ((1, 2) 
(2, 2))
3. Переместиться вверх на любое количество клеток от 1 до разницы между нынешней координатой и стеной, (стеной считается прямая y = «значение Y у конечной точки»)
Пример для команды 3, y = 5 — стена, ((1, 1) 
(1, 2), или (1, 1) 
(1, 3), или …, или (1, 1) 
(1, 5))
Программа для исполнителя — это последовательность команд.
Сколько существует различных программ, которые приведут исполнителя из точки с координатами (1, 2) в точку с координатами (12, 19).
Решение 1 (Рекурсия)
from functools import lru_cache
@lru_cache(None)
def f(st, fn):
if st == fn:
return 1
if st[0] > fn[0] or st[1] > fn[1]:
return 0
c1 = f((st[0] + 2, st[1]), fn)
c2 = f((st[0] * 2, st[1]), fn)
c = [0] * (fn[1] - st[1] + 1)
for i in range(1, fn[1] - st[1] + 1):
c[i] = f((st[0], st[1] + i), fn)
return c1 + c2 + sum(c)
print(f((1, 2), (12, 19)))
Решение 2 (Динамика)
dp = [[0] * 20 for i in range(13)]
dp[1][2] = 1
for x in range(1, 13):
for y in range(2, 20):
if x + 2 < 13:
dp[x + 2][y] += dp[x][y]
if x * 2 < 13:
dp[x * 2][y] += dp[x][y]
for to in range(y + 1, 20):
dp[x][to] += dp[x][y]
print(dp[12][19])