Подсчёт путей и динамическое программирование

В задаче № 23 исполнитель преобразует число набором команд, например:

1. прибавь 1;
2. прибавь 2;
3. умножь на 2.

Нужно найти, сколько существует программ, которые переводят число A в число B, возможно, с условием вроде «траектория содержит число C» или «не содержит число D».

Идея

Обозначим ways[x] — число способов получить число x из числа A. Тогда:

• ways[A] = 1 — пустая программа;
• для каждого x по возрастанию каждая команда добавляет ways[x] к тому числу, в которое она переводит x.

Так как все команды увеличивают число, к моменту обработки x значение ways[x] уже окончательно известно.

def paths(start, target):
    ways = [0] * (target + 1)
    ways[start] = 1
    for x in range(start, target + 1):
        for nxt in (x + 1, x + 2, x * 2):
            if nxt <= target:
                ways[nxt] += ways[x]
    return ways[target]

print(paths(1, 10))   # 154

Для команд «+1, +2, ×2» из числа 1 в число 10 получается 154 программы.

Если команда уменьшает число (например, «вычти 1»), порядок по возрастанию не подходит: тогда нужен граф с обходом или рекурсия с запоминанием, и нужно следить за зацикливанием.

Траектория должна содержать число C

Любая подходящая программа сначала приходит в C, а потом из C в B. Поэтому количество путей перемножается:

print(paths(1, 5) * paths(5, 10))   # 90

В примере число 5 обязательно, и программ становится 90: из 154 исключены те, что обходят 5.

Траектория не должна содержать число D

Когда программа доходит до запрещённого числа, её нужно «обнулить»: количество способов в нём равно нулю, и дальше оно ничего не передаёт.

def paths_avoid(start, target, bad):
    ways = [0] * (target + 1)
    ways[start] = 1
    for x in range(start, target + 1):
        if x == bad:
            ways[x] = 0
        for nxt in (x + 1, x + 2, x * 2):
            if nxt <= target:
                ways[nxt] += ways[x]
    return ways[target]

print(paths_avoid(1, 10, 6))   # 54

Запрещаем число 6 — остаётся 54 программы. Обратите внимание: обнуляем ways[x] до того, как передать его дальше.

Если запрещено несколько чисел, проверяйте условие x in bad в том же месте.

Проверка на малом примере

Из 1 в 3 командами «+1, +2, ×2» ровно три программы: +2, +1 +1 и ×2 +1. Значение paths(1, 3) должно быть равно 3. Простая сверка на малых числах быстро выявляет ошибки в порядке команд и в условиях.

Типичные ошибки

• Начинают цикл с нуля или забывают поставить ways[start] = 1.
• Считают, что ways[nxt] нужно присваивать, а не добавлять: путей может быть несколько.
• При запрещённом числе обнуляют после передачи, а не до.
• Для команд, которые уменьшают число, применяют заполнение по возрастанию.