Динамическое программирование: постановка, состояния и оптимизации
Динамическое программирование (DP) на LeetCode встречается так же часто, как хеш-таблицы и BFS. Но в отличие от “готовых” структур данных, DP требует правильно поставить задачу: выбрать состояние, придумать переход и не выйти за ограничения времени/памяти.
Связь с предыдущими темами курса прямая:
Из темы про Big-O вы берёте навык заранее оценивать, пройдёт ли или нужен .
Из темы про коллекции вы берёте инструменты хранения состояний (массив, словарь) и цену операций.
Из темы про обходы вы берёте идею “посещать состояния системно”: DP почти всегда можно понимать как обход графа состояний.Что такое динамическое программирование
Динамическое программирование — это подход, где задача разбивается на подзадачи, ответы на подзадачи сохраняются, а затем используются повторно.
Два ключевых признака задач, где DP часто уместно:
Перекрывающиеся подзадачи: одни и те же промежуточные вычисления возникают много раз.
Оптимальная подструктура: оптимальный ответ собирается из оптимальных ответов меньших частей.Обычно DP применяют, когда нужно:
найти минимум/максимум (стоимость, число операций, прибыль)
посчитать количество способов
определить существование решения (можно ли набрать сумму, можно ли дойти)Источник для общего определения:
Dynamic programming (Wikipedia)Как распознать DP в условии
Частые “сигнальные слова”:
“минимальная/максимальная стоимость”, “оптимальный”
“сколько способов”, “количество путей”, “сколько раз”
“можно ли” с множеством выборов на каждом шаге
“разбить”, “разделить”, “склеить”, “выбрать подмножество”И важная подсказка про ограничения:
если до , классическое DP чаще всего не пройдёт
если до , иногда проходит
если есть два параметра и , DP часто становится и это нужно сопоставить с лимитамиПошаговая постановка DP
DP почти всегда строится по одному и тому же плану.
Состояние
Состояние — это то, что полностью описывает подзадачу.
Практический вопрос:
что я должен знать, чтобы продолжить решение, не вспоминая весь путь?Типичные формы состояния:
dp[i] — ответ для префикса длины i
dp[i][j] — ответ для позиции (i, j) (сетка), или для двух индексов (подстрока i..j)
dp[i][k] — ответ после обработки i элементов при ресурсе kБаза
Базовые случаи — минимальные подзадачи, которые считаются напрямую.
Пример: если dp[i] зависит от dp[i-1], надо определить dp[0] и, возможно, dp[1].
Переход
Переход — формула или правило, как собрать dp[state] из меньших состояний.
Пример перехода словами:
“чтобы оказаться в i, я мог прийти из i-1 или i-2”Порядок вычисления
DP бывает двух основных видов по стилю вычисления:
сверху вниз (top-down): рекурсия + мемоизация
снизу вверх (bottom-up): табличное заполнениеПравильный порядок важен, чтобы все зависимости уже были посчитаны.
Оценка сложности
После того как вы придумали состояние и переход, сложность обычно читается почти автоматически.
время: число состояний умножить на стоимость обработки одного состояния
память: сколько состояний храните одновременноTop-down и bottom-up: два способа сделать одно и то же
Top-down: рекурсия с мемоизацией
Идея: считаем ответ рекурсивно и сохраняем результаты, чтобы не пересчитывать.
Плюсы:
часто проще придумать
вычисляет только те состояния, которые реально нужныМинусы:
риск переполнить стек рекурсии
иногда медленнее из-за накладных расходов вызововПример (Python) для “лестницы” (аналог Climbing Stairs):
Здесь состояние f(i) означает “сколько способов попасть на ступень i”.
Bottom-up: табличное заполнение
Идея: заполняем dp по возрастанию, чтобы зависимости уже были готовы.
Плюсы:
нет рекурсии
проще контролировать памятьМинусы:
иногда приходится заполнять “лишние” состояния!Граф состояний помогает увидеть, почему мемоизация убирает повторные вычисления
Самые частые формы DP на LeetCode
Одномерное DP по префиксу
Состояние вида dp[i] — ответ для первых i элементов.
Примеры задач:
“дойти до конца с минимальной стоимостью”
“максимальная сумма подмассива с условиями”
“количество способов декодирования”Типовая логика:
вы на позиции i
выбираете один из нескольких переходов из меньших iDP на сетке
Состояние вида dp[i][j] — ответ в клетке (i, j).
Обычно переходы идут из соседей:
сверху (i-1, j)
слева (i, j-1)Классический пример: “сколько путей до клетки при движении вправо/вниз”.
!Иллюстрация табличного заполнения DP на сетке
DP “выбор/не выбор”: рюкзак и суммы
Состояние часто выглядит так:
dp[i][k] — можно ли набрать сумму k, используя первые i элементов
или dp[i][k] — максимальная ценность при ограничении kЭто типичный класс:
0/1 Knapsack
Partition Equal Subset SumГлавная опасность: может быть слишком большим, если сумма не ограничена.
DP по подстрокам и интервалам
Состояние вида dp[l][r] — ответ для подстроки/подмассива от l до r.
Примеры:
палиндромы (является ли s[l..r] палиндромом)
“оптимальное разбиение строки”Ключевой момент: порядок заполнения должен идти от маленьких интервалов к большим.
DP на подпоследовательностях
Состояния часто завязаны на индекс:
dp[i] — лучший ответ для подпоследовательности, заканчивающейся в iКлассический пример: LIS за через переход по всем j < i.
Этот вид DP важен как базовый, даже если в некоторых задачах есть более быстрые оптимизации.
Как правильно считать сложность DP
Удобная “формула здравого смысла”:
Здесь:
— оценка времени
“число состояний” — сколько разных dp[...] вы храните
“стоимость перехода” — сколько операций нужно, чтобы вычислить одно состояниеПримеры:
dp[i] с константным числом переходов:
dp[i][j] для сетки :
dp[i] где переход перебирает все j < i: Для памяти часто достаточно оценить размер таблицы:
dp длины n:
dp размера n \times m: Оптимизации: как укладываться в память и время
Оптимизация памяти: “rolling array”
Если dp[i] зависит только от нескольких предыдущих значений, хранить весь массив не обязательно.
Пример для лестницы:
вместо dp[0..n] можно держать только последние два значенияТо же самое часто работает для сетки:
если dp[i][j] зависит только от строки i-1, можно хранить одну строку dp[j]Оптимизация перехода
Частая причина TLE в DP — не количество состояний, а дорогой переход.
Типовые приёмы ускорения:
хранить дополнительные “префиксные” значения (минимумы/максимумы/суммы), чтобы переход стал
использовать хеш-таблицу для переходов по редким состояниям
заранее отсортировать данные, чтобы переходы стали монотонными и считались линейноПрактическая мысль: если переход выглядит как “перебрать всех предыдущих”, это кандидат на оптимизацию.
Оптимизация за счёт смены постановки
Иногда можно поменять определение состояния и резко упростить переход.
Пример типичной смены угла:
вместо “какой лучший ответ, если я выбрал конкретные элементы”
перейти к “какой лучший ответ, если я на позиции i и у меня такой-то ресурс/баланс”Это особенно часто встречается в задачах со строками и массивами, где состояние можно выразить через индекс и пару параметров.
Когда DP превращается в BFS/DFS по состояниям
Если переходы выглядят как “из состояния можно перейти в несколько новых”, а стоимость каждого шага одинаковая, это очень похоже на граф.
Практический вывод:
если нужно “минимум шагов” и все шаги одинаковые, сначала подумайте про BFS
если нужно “минимальная стоимость”, подумайте про DP или алгоритмы кратчайших путейДля связи темы с графами полезна базовая статья:
Shortest path problem (Wikipedia)Типичные ошибки в DP на LeetCode
Состояние не полное: вы потеряли важный параметр, и переход становится неверным.
Переход считает одно и то же много раз: забыли мемоизацию или неправильно выбрали порядок.
Неправильные базовые случаи: dp[0] и “пустые” ситуации часто ломают ответ.
Таблица слишком большая: по памяти не проходит, нужна оптимизация по памяти.
Переход слишком дорогой: получилось при .Как эта тема встраивается в курс
Ранее вы научились:
оценивать, какие классы сложности “реально проходят”
выбирать структуры данных для быстрых операций
обходить деревья и графы за линейное времяDP объединяет всё это в один навык: вы проектируете пространство состояний и “обходите” его так, чтобы уложиться в ограничения.
На практике в большинстве задач LeetCode достаточно уверенно владеть базовыми формами:
dp[i] и dp[i][j]
memoization и tabulation
rolling array и аккуратная оценка