DP 1D на Python: как решать + 12 задач с проверкой

DP 1D (одномерное динамическое программирование) — это приём для задач, где есть последовательность: кварталы на улице, ступеньки, дни, позиции на табло, призы в коридоре. В таких задачах нужно выбрать/собрать/дойти так, чтобы получить максимум (или минимум), соблюдая простые локальные ограничения — например «нельзя брать соседние», «прыжок на 1 или 2», «учитываем последние k шагов», «платим сумму монетами».

Как распознать задачу на DP 1D

• Есть массив/строка из n элементов и нужно оптимизировать результат.
• Ответ для позиции i зависит только от нескольких предыдущих позиций (i-1, i-2, …).
• В лоб получается перебор вариантов на каждом шаге (часто “выбрать/не выбрать”), который растёт слишком быстро.
• В условии явно звучит «для первых i элементов», «пройти до i», «максимум на префиксе».

Суть приёма

Мы заводим массив dp[i] — лучший ответ для первых i элементов (или для позиции i). Дальше пишем переход: как получить dp[i] из уже посчитанных dp[i-1], dp[i-2] и т.п. Это ускоряет решение, потому что каждый dp[i] считается один раз: обычно получается O(n) вместо экспоненты.

С чего начать учиться

• Научиться формулировать: что именно означает dp[i] (префикс, позиция, “до i включительно”).
• Выписать варианты последнего шага (взять i или пропустить; прийти из i-1 или i-2).
• Аккуратно задать базу (dp[0], dp[1]) и проверить на маленьких n.
• Следить за типами: суммы легко требуют 64-битные целые.
• Освоить оптимизацию памяти: иногда достаточно хранить только последние 2–3 значения.

Ниже — задачи с автопроверкой и разбором подхода, чтобы закрепить DP 1D на практике.