Одномерная динамика

Динамическое программирование звучит внушительно, а на деле это дисциплина: на любую задачу отвечают три вопроса, и ответы на них и есть решение.

1. Что такое состояние? Какую величину мы считаем и чем она задаётся. «Количество способов дойти до ступени $i$». «Наименьшая стоимость добраться до камня $i$».

2. Каков переход? Как состояние выражается через меньшие состояния. Здесь важно слово «меньшие»: если состояние выражается через себя же, ничего не посчитается.

3. Какова база? С чего всё начинается — те состояния, которые известны без вычислений.

Всё остальное — техника. Если три ответа даны верно, код пишется механически.

Почему это работает

Динамика применима, когда задача обладает свойством: оптимальное решение целого собирается из оптимальных решений частей.

Звучит очевидно, но верно не всегда. Если бы стоимость пути зависела от того, как именно мы пришли в предыдущую точку, знать «лучшее до предыдущей точки» было бы недостаточно — пришлось бы помнить и историю. Тогда состояние надо расширять, и это уже другая задача.

Проверка на честность та же, что была у жадности и у окна: достаточно ли того, что я храню в состоянии, чтобы посчитать следующее? Если нет — состояние выбрано неудачно.

Задача, на которой видно всё сразу. Кузнечик стоит на нулевой ступени и прыгает на одну или две. Сколькими способами он доберётся до ступени $n$?

Отвечаем на три вопроса.

Состояние: dp[i] — количество способов оказаться на ступени $i$.

Переход: на ступень $i$ можно попасть только с $i-1$ или с $i-2$. Эти способы не пересекаются — последний прыжок у них разный, — значит количества складываются: dp[i] = dp[i-1] + dp[i-2].

База: dp[0] = 1. Одна пустая последовательность прыжков: стоять на месте — это тоже способ оказаться на нулевой ступени.

dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
    dp[i] = dp[i - 1] + (dp[i - 2] if i >= 2 else 0)

Числа получились знакомые — это Фибоначчи. Так и должно быть: рекуррентность у них одна и та же.

Порядок обхода

Цикл идёт снизу вверх не случайно: к моменту вычисления dp[i] оба слагаемых уже посчитаны. Это общее правило — состояния вычисляются в таком порядке, чтобы всё, от чего они зависят, было готово раньше.

Экономия памяти

Для перехода нужны только два предыдущих значения, а не весь массив:

previous, current = 1, 1
for i in range(2, n + 1):
    previous, current = current, previous + current

При $n$ в миллионы это разница между «работает» и «не хватило памяти». Приём общий: если переход смотрит недалеко назад, хранить всё не нужно.

Почему в задаче о кузнечике база dp[0] = 1, а не dp[0] = 0?

Одна и та же схема отвечает на два разных вопроса, и различие ровно в одном действии.

Сравните. Количество способов дойти до ступени: dp[i] = dp[i-1] + dp[i-2]. Наименьшая плата за подъём: dp[i] = min(dp[i-1], dp[i-2]) + cost[i].

Состояние, переход и база — те же. Меняется только то, что делают с вариантами.

Про остаток

Количества растут стремительно: способов дойти до миллионной ступени — число из двухсот тысяч цифр. Поэтому в таких задачах просят ответ по модулю, обычно $10^9 + 7$.

Остаток берут на каждом шаге, а не в конце: иначе числа успевают разрастись, и в Python это станет медленно, а в других языках просто переполнится.

dp[i] = (dp[i - 1] + dp[i - 2]) % MOD

Недостижимые состояния

В задачах на минимум надо отличать «стоит ноль» от «сюда нельзя попасть». Ноль — это законная стоимость, и если пометить им недостижимое состояние, оно окажется самым выгодным. Помечайте недостижимость отдельно: бесконечностью или значением -1, которое проверяется перед использованием.

Кузнечик прыгает на одну или две ступени с нулевой.

Сколькими способами он доберётся до пятой ступени? Введите целое число.

Динамика по умолчанию отвечает «сколько» или «насколько хорошо», но не «как именно». Между тем условие часто просит сам путь, сам набор, саму подпоследовательность.

Приём тот же, что при обходе в ширину: вместе со значением состояния запоминаем, откуда мы в него пришли.

for i in range(1, n + 1):
    if dp[i - 1] <= dp[i - 2]:
        dp[i] = dp[i - 1] + cost[i]
        came_from[i] = i - 1        # запомнили выбор
    else:
        dp[i] = dp[i - 2] + cost[i]
        came_from[i] = i - 2

Потом идём от конечного состояния назад по этим отметкам и переворачиваем получившуюся последовательность:

path = []
i = n
while i > 0:
    path.append(i)
    i = came_from[i]
path.append(0)
path.reverse()

Памяти это стоит ещё одного массива, времени — ничего.

Второй способ — не хранить ничего, а восстанавливать задним ходом: стоя в состоянии $i$, проверить, какой из переходов даёт записанное значение. Он экономит память, но требует аккуратности при равенствах.

База не задана или задана неверно. Самая частая. Если dp[0] = 0 в задаче на подсчёт, обнулится весь ответ. Проверяйте базу на самом маленьком входе, где ответ известен наизусть.

Порядок циклов, меняющий смысл. В подсчёте наборов монет внешний цикл по суммам вместо монет превращает наборы в последовательности, и ответ становится больше. Разберём это подробно в задании ниже.

Ноль вместо «недостижимо». Разобрано выше. Признак: в задаче на минимум ответ подозрительно мал.

Остаток берётся в конце. Числа успевают разрастись до сотен тысяч цифр.

Рекурсия с запоминанием на длинной цепочке. Та же ловушка, что была с обходами: глубина вызовов упирается в предел. Одномерная динамика прекрасно пишется циклом — так и пишите.

Ответ взят из последнего состояния, а не из лучшего. В задачах вроде «самый выгодный отрезок» или «возрастающая подпоследовательность» ответ — это максимум по всем состояниям. Последнее состояние отвечает лишь на вопрос «а если кусок кончается ровно здесь».

Как проверять себя

• самый маленький вход: $n = 0$, $n = 1$ — там ответ виден без программы;
• все элементы одинаковые;
• все числа отрицательные — в задачах на максимум это ловит неверную базу;
• сравнение с перебором при $n = 10$: приём из занятия про перебор работает и здесь.

Лестница прежняя: пять разминочных, семь основных, три со звёздочкой. Зачёт при десяти решённых.

Перед каждой задачей отвечайте на три вопроса вслух: состояние, переход, база. Это занимает полминуты и экономит час отладки.

И помните про два разных ответа одной схемы: «сколькими способами» складывает, «как лучше» берёт минимум или максимум.

Задача: «есть монеты нескольких номиналов, каждого сколько угодно; сколькими способами набрать сумму $s$? Наборы, отличающиеся только порядком монет, считаются одним».

Ученик написал:

n, s = map(int, input().split())
coins = list(map(int, input().split()))

dp = [0] * (s + 1)
dp[0] = 1

for total in range(1, s + 1):
    for coin in coins:
        if coin <= total:
            dp[total] += dp[total - coin]

print(dp[s])

Состояние выбрано верно, база тоже, программа не падает. Но на многих тестах ответ оказывается больше правильного.

Постройте вход, на котором видно расхождение, объясните, что именно считает эта программа, и предложите исправление.