Динамическое программирование на LeetCode

Основы DP: состояния, переходы, базовые случаи

Динамическое программирование (DP) — это способ решать задачи, где ответ для большой задачи можно собрать из ответов для меньших задач, а повторные вычисления можно избежать, сохраняя уже найденные результаты.

На LeetCode DP встречается постоянно: от простых задач вроде Climbing Stairs до сложных задач на строки, интервалы и графы.

Полезные справочные источники:

LeetCode

Dynamic programming (Wikipedia)

Introduction to Dynamic Programming (cp-algorithms)

Когда DP действительно нужно

DP обычно подходит, если выполняются оба пункта:

Оптимальная подструктура: оптимальный ответ для исходной задачи выражается через оптимальные ответы для подзадач.

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

Пример без формализма: если вы много раз задаёте вопрос “какой лучший результат для префикса длины i?”, то это сильный намёк на DP.

Главные компоненты DP

Практически любое DP-решение на LeetCode можно собрать из четырёх деталей:

Состояние: что именно мы храним в dp.

Переход: как вычислить одно состояние из других.

Базовые случаи: от чего мы отталкиваемся, чтобы цепочка вычислений стартовала.

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

Дальше разберём каждую часть.

Состояние DP

Состояние — это ответ на вопрос: “что означает dp[x]?”.

Чаще всего на LeetCode встречаются такие формы:

dp[i] — ответ для первых i элементов (префикс) или для позиции i.

dp[i][j] — ответ для подотрезка от i до j, или для двух параметров (например, позиции и бюджета).

dp[i][mask] — позиция плюс битмаска (часто в задачах на подмножества).

Хорошее состояние:

однозначно интерпретируется словами;

достаточно маленькое, чтобы поместиться по памяти;

позволяет выразить переход коротко и без перебора лишнего.

Пример: Climbing Stairs

Задача: есть лестница из n ступенек, можно идти на 1 или 2 ступени. Сколькими способами можно дойти до верха?

Выбор состояния:

dp[i] — количество способов добраться до ступени i.

Это состояние простое и напрямую ведёт к переходу.

Переходы

Переход — это правило, как вычислить dp[state] через меньшие состояния.

В задаче про лестницу последним шагом на ступень i может быть:

шаг с i-1 (на 1 ступень),

шаг с i-2 (на 2 ступени).

Значит количество способов суммируется:

Расшифровка формулы:

— число способов добраться до ступени i.

— число способов добраться до i-1, а затем сделать шаг на 1.

— число способов добраться до i-2, а затем сделать шаг на 2.

Сумма, потому что это два непересекающихся варианта последнего шага.

!Диаграмма показывает, откуда берётся dp[i и почему это сумма двух предыдущих состояний]

Частая ошибка в переходах

Нельзя “просто суммировать” или “просто брать минимум”, не доказав смысл:

если считаете количество — обычно суммируете количества путей;

если оптимизируете (минимум/максимум) — выбираете лучший из вариантов;

если проверяете достижимость — часто используете логическое “или”.

Тип перехода всегда должен совпадать с тем, что означает dp.

Базовые случаи

Базовые случаи — это стартовые значения, которые не вычисляются из других.

В Climbing Stairs (при нумерации ступеней от 0):

dp[0] = 1 — один способ быть на нулевой ступени: ничего не делать.

dp[1] = 1 — один способ добраться до 1: шаг на 1.

Почему важно аккуратно выбрать базу:

неправильная база ломает всё решение, даже если переход верный;

база влияет на граничные случаи, например n = 0, n = 1, n = 2.

Практическое правило: прогоните руками самые маленькие входы и проверьте, что dp совпадает со здравым смыслом.

Порядок вычисления

DP можно считать двумя основными способами.

Top-down: рекурсия + мемоизация

Идея: пишем функцию f(state), которая рекурсивно вызывает меньшие состояния, а результаты кэшируем, чтобы не пересчитывать.

Плюсы:

часто проще вывести правильную рекурсию;

вычисляются только реально нужные состояния.

Минусы:

риск упереться в ограничение глубины рекурсии (зависит от языка);

иногда сложнее контролировать порядок и память.

Bottom-up: табуляция

Идея: создаём таблицу dp и заполняем её в таком порядке, чтобы зависимости уже были посчитаны.

Плюсы:

нет рекурсивной глубины;

обычно проще оптимизировать память.

Минусы:

иногда приходится считать “лишние” состояния.

Минимальный шаблон DP-мышления для LeetCode

Если вы застряли, пройдите по чек-листу:

Сформулируйте dp словами.

Определите, какие предыдущие состояния нужны, чтобы получить текущее.

Выпишите переход.

Найдите базовые случаи.

Определите порядок вычисления.

Проверьте на маленьких входах.

Пример решения: Climbing Stairs (bottom-up)

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

Оптимизация памяти

Если переход использует только несколько предыдущих состояний (как в лестнице: i-1 и i-2), то хранить весь массив необязательно.

Идея: вместо массива держим пару переменных.

Важно: оптимизацию делайте после того, как получили корректное решение с массивом. На собеседованиях и на LeetCode правильность важнее преждевременной оптимизации.

Как это переносится на другие DP-задачи LeetCode

Одна и та же схема повторяется во многих задачах:

House Robber: dp[i] — максимум денег на префиксе до i, переход выбирает “брать дом i” или “не брать”.

Longest Increasing Subsequence: dp[i] — длина наилучшей возрастающей подпоследовательности, заканчивающейся в i.

0/1 Knapsack-подобные задачи: dp[i][w] — лучший результат, используя первые i предметов и ограничение w.

Во всех случаях решающее — правильно назвать состояние словами и затем честно перечислить варианты последнего шага.

Итоги

Состояние отвечает на вопрос, что именно хранит dp.

Переход объясняет, как получить текущее из предыдущих.

Базовые случаи дают старт, без них формула не работает.

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

В следующих материалах курса мы будем усложнять состояния (2D DP, DP по строкам, по отрезкам) и учиться узнавать типовые паттерны LeetCode.

Рекурсия, мемоизация и табуляция: как выбирать подход

В прошлой статье мы разобрали базовую конструкцию DP: состояние, переход, базовые случаи и порядок вычисления. Теперь добавим практический навык, без которого на LeetCode часто “не взлетает”: как именно реализовать DP.

Одна и та же идея DP почти всегда может быть записана двумя способами:

top-down (рекурсия) + мемоизация

bottom-up табуляция (итеративное заполнение таблицы)

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

Рекурсия как “естественная” форма DP

Рекурсивная формулировка обычно появляется первой: вы описываете ответ для состояния через ответы для меньших состояний.

Пример на мотиве Climbing Stairs:

Пусть f(i) = число способов добраться до ступеньки i.

Тогда f(i) = f(i-1) + f(i-2).

База: f(0)=1, f(1)=1.

Если написать это в лоб, получится корректно по смыслу, но медленно, потому что одни и те же f(i) будут вычисляться много раз.

Почему медленно:

f(n) вызывает f(n-1) и f(n-2)

f(n-1) снова вызывает f(n-2)

и так далее, количество повторов растёт лавинообразно

Вывод: одна рекурсия без памяти в DP почти всегда недостаточна.

Мемоизация: “рекурсия с памятью”

Мемоизация — это сохранение ответа для каждого состояния, чтобы при повторном запросе вернуть готовый результат.

Ключевая мысль: состояние должно однозначно определяться параметрами функции.

Top-down DP: рекурсия + кэш

В Python чаще всего удобно использовать functools.lru_cache.

Документация: functools.lru_cache

Что изменилось:

первое вычисление f(i) сохраняется

последующие вызовы f(i) становятся “дешёвым” чтением из кэша

Типичная картина на LeetCode:

сверху вниз удобно решать задачи на строки, на отрезки, на “выбор/не выбор”, где естественно думать рекурсией

мемоизация позволяет не думать о порядке заполнения таблицы, он получается “сам собой” из рекурсивных зависимостей

Важные ограничения memoization-подхода

Глубина рекурсии: в некоторых языках (и в Python) на больших входах можно упереться в лимит глубины стека.

Скрытая стоимость: рекурсивные вызовы и хеширование ключей кэша дают накладные расходы.

Риск “плохого” состояния: если состояние содержит лишние параметры, число различных состояний резко растёт, и мемоизация перестаёт помогать.

Табуляция: “таблица снизу вверх”

Табуляция — это итеративное заполнение массива или таблицы dp в правильном порядке.

Главное отличие от мемоизации:

вы сами выбираете порядок, в котором гарантированно посчитаны все зависимости

вы обычно заранее создаёте структуру dp нужного размера

Для Climbing Stairs:

Плюсы табуляции:

нет проблем с глубиной рекурсии

часто проще гарантировать скорость на больших входах

обычно проще оптимизировать память, если зависимости локальные

Минусы:

иногда сложно “сходу” понять порядок заполнения (особенно в 2D DP)

иногда вы считаете состояния, которые топ-даун даже не посетил бы

Как выбирать: практические критерии

Ниже — прикладной чек-лист выбора подхода для задач LeetCode.

!Блок-схема, помогающая выбрать между мемоизацией и табуляцией

Когда чаще выбирать мемоизацию

Мемоизация обычно сильна, когда:

рекурсия получается “чистой” и короткой: f(i, j) или f(pos, prev)

часть состояний может быть недостижима, и топ-даун их не считает

порядок табуляции неочевиден, а зависимости описать рекурсией легко

Типичные примеры на LeetCode:

DP по строкам и подстрокам, где состояние похоже на “ответ для s[i:j]”

задачи с несколькими параметрами, где рекурсивная логика проще, чем ручной порядок обхода

Практический сигнал: если вы можете словами сформулировать функцию f(state) и базу за 30 секунд, мемоизация часто будет самым быстрым путём к верному решению.

Когда чаще выбирать табуляцию

Табуляция обычно лучше, когда:

вход большой, и есть риск переполнить стек рекурсии

есть очевидный линейный или двойной цикл по i, j

вы хотите гарантированно минимальные накладные расходы

вы хотите легко сделать оптимизацию памяти

Типичные примеры:

одномерные DP, которые заполняются слева направо

задачи типа “рюкзак” с dp[w] и проходом по весам

ситуации, где вам нужно построить ответ итеративно (например, восстановить путь по parent, хотя это можно и в топ-даун)

Одна и та же задача: два корректных стиля

Рассмотрим House Robber (классика LeetCode).

Идея:

на позиции i либо грабим дом i (тогда предыдущий нельзя)

либо не грабим дом i

Memoization-вариант

Почему это удобно:

состояние i очень естественное

базовый случай “вышли за массив” понятный

Tabulation-вариант

Почему это удобно:

нет рекурсии

простой линейный проход

Вывод: и мемоизация, и табуляция одинаково “правильные”, выбор — про удобство и ограничения.

Частые ошибки при выборе и реализации

Ошибка: мемоизация “не помогает”

Обычно причина одна из двух:

состояние определено неправильно и включает лишнее, из-за чего кэш почти не переиспользуется

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

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

Ошибка: табуляция “даёт неверный ответ”

Частая причина:

нарушен порядок вычисления, и вы читаете dp-ячейки, которые ещё не посчитаны

неверно выставлены базовые случаи

Практика: выпишите зависимость для dp[i] и убедитесь, что все нужные индексы были заполнены раньше.

Ошибка: рекурсия падает на больших тестах

Признак:

решение проходит маленькие тесты и падает на больших, или получает runtime error

Лечение:

переписать на табуляцию

или уменьшить глубину рекурсии, если это возможно за счёт другого состояния

Мини-резюме

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

Мемоизация делает top-down DP практичным: считаете только нужные состояния, проще выводить рекурсию.

Табуляция даёт максимальный контроль: порядок, память, скорость, отсутствие проблем со стеком.

Выбор подхода на LeetCode чаще всего определяется глубиной рекурсии, ясностью порядка и удобством формулировки состояния.

Полезные ссылки для практики и справки:

LeetCode

functools.lru_cache

Dynamic Programming Introduction (cp-algorithms)

Одномерное DP: подмассивы, прыжки, оптимизация памяти

В прошлых статьях курса мы разобрали, из чего состоит динамическое программирование: состояние, переход, база и порядок вычисления, а также сравнили мемоизацию и табуляцию. Теперь закрепим всё это на самом частом формате LeetCode: одномерное DP.

Под одномерным DP будем понимать решения, где состояние выглядит как dp[i] и отвечает на вопрос про префикс массива, позицию i или лучший результат, заканчивающийся в i.

В этой статье разберём три практических семейства задач:

подмассивы и подпоследовательности, где важно “заканчивается в i”

прыжки и достижимость, где важно “минимум шагов до i” или “можно ли дойти до i”

оптимизацию памяти, когда массив dp можно заменить несколькими переменными

Полезные задачи для практики на LeetCode:

Maximum Subarray

Min Cost Climbing Stairs

Jump Game

Jump Game II

House Robber

Главная идея одномерного DP

Почти всегда вы выбираете одно из двух смыслов состояния:

dp[i] = ответ для первых i элементов (префикс)

dp[i] = лучший ответ с условием, что решение заканчивается в i

Эти варианты похожи, но приводят к разным переходам.

Быстрый тест на правильность состояния

Спросите себя:

Можно ли сказать словами, что означает dp[i]?

Можно ли получить dp[i] из нескольких “соседних” или “ранних” состояний?

Есть ли понятная база для маленьких i?

Если на любой вопрос нет ясного ответа, состояние, скорее всего, выбрано неудачно.

Подмассивы: “лучшее, заканчивающееся здесь”

Maximum Subarray и алгоритм Кадане

Задача Maximum Subarray просит максимальную сумму непустого непрерывного подмассива.

Естественное состояние:

dp[i] = максимальная сумма подмассива, который обязательно заканчивается на индексе i

Почему это удобно:

любой подмассив, заканчивающийся в i, либо

- состоит только из nums[i] - либо это “продолжение” лучшего подмассива, заканчивающегося в i-1

Переход можно сказать словами так:

чтобы получить лучший подмассив, заканчивающийся в i, мы выбираем максимум из:

- начать заново в i - продолжить то, что было лучшим до i-1

В виде формулы:

Расшифровка каждого элемента:

— лучшая сумма подмассива, который заканчивается в i

— вариант “начинаем новый подмассив в i”

— вариант “продолжаем лучший подмассив, который заканчивался в i-1”

— выбираем лучший из двух вариантов

Финальный ответ задачи — это максимум среди всех dp[i], потому что лучший подмассив может заканчиваться где угодно.

!Иллюстрация показывает, почему состояние "заканчивается в i" даёт простой переход

#### Реализация (табуляция, O(1) память)

Здесь мы уже применили оптимизацию памяти: dp[i] зависит только от dp[i-1], значит хранить весь массив не нужно.

Частая ошибка в Maximum Subarray

Путают “подмассив” и “подпоследовательность”.

подмассив — элементы идут подряд

подпоследовательность — можно пропускать элементы

Алгоритм выше работает именно для подмассива.

Прыжки: достижимость и минимум шагов

Задачи про прыжки часто формулируются как:

можно ли добраться до конца

за сколько минимальных прыжков можно добраться

Их удобно решать DP, потому что “попасть в i” можно из каких-то предыдущих позиций.

Достижимость: Jump Game

Задача Jump Game спрашивает, можно ли добраться до последнего индекса.

DP-идея:

dp[i] = достижима ли позиция i

база: dp[0] = True

переход: dp[i] = True, если существует j < i, такое что:

- dp[j] = True - и из j можно прыгнуть в i, то есть j + nums[j] >= i

Такое DP корректно, но часто получается из-за перебора всех j.

Практический вывод для LeetCode:

для Jump Game чаще используют жадный алгоритм

но DP-формулировка полезна как тренировка: вы учитесь строить состояние и переход

Минимум прыжков: Jump Game II

В Jump Game II нужно минимальное число прыжков, чтобы добраться до конца.

DP-формулировка:

dp[i] = минимальное число прыжков, чтобы попасть в i

база: dp[0] = 0

переход: чтобы попасть в i, мы могли прыгнуть из любого j < i, откуда j + nums[j] >= i

тогда dp[i] = min(dp[j] + 1) по всем таким j

Смысл элементов перехода:

dp[j] — сколько прыжков надо, чтобы добраться до j

+ 1 — один прыжок из j в i

min — выбираем лучший предыдущий j

Этот DP тоже , и на практике задачу обычно решают жадно за . Но как упражнение это отличный пример “минимизации” в DP и правильного выбора базового случая.

#### DP-реализация Jump Game II (как учебный шаблон)

Важно: даже если вы знаете жадное решение, умение записать DP помогает на задачах, где жадность не проходит.

Префиксное DP: “лучший результат на первых i элементах”

Теперь паттерн, где dp[i] относится к префиксу.

Min Cost Climbing Stairs

Задача Min Cost Climbing Stairs предлагает цену за ступеньки и просит минимальную стоимость, чтобы подняться на “верх” (позиция за пределами последней ступени). Можно шагать на 1 или 2.

Удобная формулировка:

dp[i] = минимальная стоимость, чтобы оказаться на ступеньке i

Тогда переход:

чтобы попасть на i, мы приходим либо с i-1, либо с i-2

значит выбираем минимум из двух вариантов и добавляем стоимость текущей ступеньки

С практической точки зрения здесь важна деталь:

“верх” не имеет стоимости

вы можете стартовать с 0 или 1 без оплаты “перед стартом”

Один из популярных вариантов реализации (через стоимость прихода на ступень):

Здесь снова видно правило оптимизации памяти: если dp[i] зависит только от двух предыдущих, достаточно двух переменных.

House Robber как классический “выбор или не выбор”

В House Robber нельзя брать соседние элементы.

Типовое префиксное состояние:

dp[i] = максимум денег, который можно заработать, рассматривая дома 0..i

Переход:

либо мы не берём дом i, тогда результат dp[i-1]

либо мы берём дом i, тогда дом i-1 брать нельзя, и результат dp[i-2] + nums[i]

Итого:

Расшифровка:

— максимум на префиксе без обязательного взятия i

— берём i и добавляем к лучшему на префиксе до i-2

— выбираем более выгодный план

Оптимизированная по памяти реализация:

Оптимизация памяти в одномерном DP

Оптимизация памяти почти всегда сводится к вопросу:

сколько прошлых состояний нужно для вычисления текущего?

Когда можно заменить массив на переменные

Можно заменить dp на несколько переменных, если:

переход использует только фиксированное число прошлых значений, например dp[i-1], dp[i-2]

Примеры:

Climbing Stairs из прошлой статьи

Min Cost Climbing Stairs

House Robber

Maximum Subarray

Когда оптимизация памяти опасна

Опасно “сжимать” DP, если:

dp[i] зависит от многих прошлых значений, например от всех dp[0..i-1]

нужно восстановить ответ (путь, индексы), а вы выбросили информацию

Практическое правило для LeetCode:

сначала сделайте корректное решение с массивом dp

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

Как быстро узнавать, что перед вами одномерное DP

На LeetCode сильные сигналы такие:

есть “движение” по индексу: слева направо или справа налево

у ответа естественный параметр “позиция” или “длина префикса”

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

Если вы видите это, попробуйте зафиксировать dp[i] словами и выписать “что было последним шагом”. Это почти всегда приводит к рабочему решению.

Итоги

Одномерное DP чаще всего строится вокруг dp[i] как ответа для позиции i или префикса до i.

Для подмассивов часто удобно состояние “лучшее, заканчивающееся в i” (пример: Maximum Subarray).

Для прыжков можно формулировать DP через достижимость или минимум шагов, даже если на практике иногда быстрее жадность.

Если переход использует только dp[i-1], dp[i-2] или другое малое окно, память легко сжимается до нескольких переменных.

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

Двумерное DP: сетки, строки, подпоследовательности

В прошлых статьях курса мы разобрали базовые кирпичики DP (состояние, переход, базовые случаи, порядок вычисления), сравнили мемоизацию и табуляцию, а затем закрепили это на одномерном DP dp[i].

Следующий шаг, который очень часто встречается на LeetCode, — двумерное DP: состояние выглядит как dp[i][j]. Обычно это означает, что ответ зависит сразу от двух координат/индексов: позиция в сетке, позиция в двух строках, границы подотрезка или “первые i символов и первые j символов”.

Полезные задачи для практики:

Unique Paths

Minimum Path Sum

Longest Common Subsequence

Edit Distance

Когда 2D DP — естественный выбор

Сигналы, что вам, вероятно, нужно dp[i][j]:

В условии есть две оси: строки/столбцы в матрице, две строки, два указателя.

Вы постоянно задаёте вопросы вида “что лучше/сколько способов для префиксов длины i и j?”.

Переход для текущего состояния опирается на “соседние” состояния: слева, сверху, по диагонали.

Ключевая привычка: прежде чем писать код, одной фразой проговорите смысл dp[i][j].

Общий шаблон 2D DP

Почти всегда вы делаете одно и то же:

Состояние: dp[i][j] — ответ для подзадачи с параметрами i и j.

Переход: перечисляете варианты последнего шага и собираете dp[i][j] из уже посчитанных состояний.

База: задаёте значения для первой строки/первого столбца или для dp[0][], dp[][0].

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

Ниже разберём три самых частых семейства: сетки, строки, подпоследовательности (на примере LCS).

Сетки: пути и стоимости

Сетки на LeetCode часто формулируются так:

вы стоите в клетке (0, 0)

хотите попасть в (m-1, n-1)

можно ходить только вправо/вниз

нужно посчитать количество путей или минимальную стоимость

!Иллюстрация зависимостей в задачах на сетку

Unique Paths: считаем количество путей

Задача Unique Paths просит количество способов дойти из левого верхнего угла в правый нижний, двигаясь только вправо или вниз.

Состояние:

dp[i][j] = количество путей, чтобы попасть в клетку (i, j).

Переход (последний шаг):

в (i, j) можно прийти либо сверху (i-1, j), либо слева (i, j-1)

значит количество путей складывается

Формула:

Расшифровка элементов:

— сколько путей ведёт в клетку (i, j)

— сколько путей ведёт в клетку сверху, а затем делаем шаг вниз

— сколько путей ведёт в клетку слева, а затем делаем шаг вправо

сумма, потому что эти множества путей не пересекаются по последнему шагу

Базовые случаи:

первая строка i = 0: в каждую клетку можно попасть только двигаясь вправо, поэтому dp[0][j] = 1

первый столбец j = 0: аналогично dp[i][0] = 1

Порядок вычисления:

идём по строкам слева направо, сверху вниз: для (i, j) уже посчитаны верх и лево

Minimum Path Sum: минимизируем стоимость

В Minimum Path Sum у каждой клетки есть “стоимость”, и нужно найти минимальную сумму стоимостей на пути.

Состояние:

dp[i][j] = минимальная сумма, чтобы дойти до (i, j).

Переход:

в (i, j) приходим сверху или слева

берём минимум из двух вариантов и добавляем стоимость текущей клетки grid[i][j]

Формула:

Расшифровка элементов:

— стоимость клетки (i, j), её нужно заплатить, если мы в неё заходим

и — лучшая стоимость прийти сверху/слева

— выбираем более дешёвый путь

Базовые случаи:

dp[0][0] = grid[0][0]

первая строка: туда можно прийти только слева

первый столбец: туда можно прийти только сверху

Строки: DP по префиксам

Строковые DP-задачи почти всегда строятся вокруг идеи префиксов.

Типовая формулировка:

dp[i][j] — ответ для первых i символов строки s и первых j символов строки t

Важно договориться о нумерации:

i и j — длины префиксов, а не индексы символов

тогда “последний символ префикса длины i” — это s[i-1]

Эта договорённость резко упрощает базовые случаи: dp[0][] и dp[][0] легко трактуются как ситуации, где одна строка пустая.

Подпоследовательности: Longest Common Subsequence

Задача Longest Common Subsequence просит длину наибольшей общей подпоследовательности двух строк.

Напоминание:

подпоследовательность — можно пропускать символы

это не подстрока, символы не обязаны идти подряд

!Визуализация переходов LCS по двум строкам

Состояние

dp[i][j] = длина LCS для префиксов s[:i] и t[:j].

Переход

Смотрим на последние символы префиксов: s[i-1] и t[j-1].

Если s[i-1] == t[j-1], то этот символ можно добавить к общей подпоследовательности.

тогда dp[i][j] = dp[i-1][j-1] + 1

Если s[i-1] != t[j-1], то последний символ хотя бы одной строки не входит в оптимальный ответ.

тогда dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Почему это логично:

dp[i-1][j] означает “выкинуть последний символ s”

dp[i][j-1] означает “выкинуть последний символ t”

берём максимум, потому что хотим максимальную длину

Базовые случаи

dp[0][j] = 0 для любого j: если s пустая, общая подпоследовательность длины 0

dp[i][0] = 0 для любого i: если t пустая, аналогично

Реализация (bottom-up)

Edit Distance: когда переходов больше, чем два

Задача Edit Distance просит минимальное количество операций, чтобы превратить word1 в word2. Разрешены:

вставка символа

удаление символа

замена символа

Это хороший пример, где dp[i][j] зависит от трёх соседей.

Состояние

dp[i][j] = минимальная стоимость превратить word1[:i] в word2[:j].

База

dp[0][j] = j: из пустой строки получить префикс длины j можно j вставками

dp[i][0] = i: превратить префикс длины i в пустую строку можно i удалениями

Переход

Если последние символы равны (word1[i-1] == word2[j-1]), то платить за них не надо:

dp[i][j] = dp[i-1][j-1]

Если не равны, то рассмотрим три последнего действия:

удалить word1[i-1] → прийти из dp[i-1][j] и добавить 1

вставить word2[j-1] → прийти из dp[i][j-1] и добавить 1

заменить символ → прийти из dp[i-1][j-1] и добавить 1

Итого:

dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

Оптимизация памяти: когда 2D DP можно “сжать” до 1D

Как и в одномерном DP, главный вопрос:

от каких ячеек зависит dp[i][j]?

Во многих 2D задачах зависимость идёт только от:

текущей строки i (левая ячейка dp[i][j-1])

предыдущей строки i-1 (верхняя dp[i-1][j] и диагональная dp[i-1][j-1])

Тогда можно хранить только две строки: prev и cur.

Пример: LCS со сжатием памяти

Идея:

prev[j] — это dp[i-1][j]

cur[j] — это dp[i][j]

диагональ dp[i-1][j-1] можно держать во временной переменной diag

Практическое правило:

сначала решайте задачу обычной таблицей

затем сжимайте память, только если вы уверены в зависимостях и вам не нужно восстанавливать ответ (например, саму подпоследовательность)

Как быстро распознать паттерн и не ошибиться

Ниже — короткая шпаргалка, что означает 2D DP в самых частых темах.

| Семейство задач | Типичный смысл dp[i][j] | Откуда переход | Что часто путают | |---|---|---|---| | Сетки | ответ для клетки (i, j) | сверху/слева | базу первой строки/столбца | | Две строки | ответ для префиксов s[:i] и t[:j] | верх/лево/диагональ | индексы: i как длина, символ как s[i-1] | | LCS-подобные | длина/стоимость лучшего для двух префиксов | max или min из соседей | подстрока vs подпоследовательность |

Итоги

Двумерное DP почти всегда означает, что подзадача зависит от двух параметров: координат, двух указателей, двух префиксов.

В сетках чаще всего переход идёт из “соседей” (сверху/слева), а база задаётся по первой строке и первому столбцу.

В строковых задачах удобно трактовать i и j как длины префиксов, тогда базовые случаи dp[0][] и dp[][0] становятся очевидными.

2D DP часто можно оптимизировать по памяти до двух строк (или даже одной), если зависимости локальны.

Дальше по курсу обычно переходят к более “тяжёлым” формам: DP по отрезкам, DP по подмножествам (битмаски), а также к технике восстановления ответа (не только длины/стоимости, но и самого решения).

Рюкзак и подсчёт способов: coin change, subset sum

DP по типу рюкзака — один из самых важных паттернов на LeetCode. Он связывает вместе почти всё, что мы уже прошли:

из основ DP берём смысл состояния, переход и базу;

из табуляции — правильный порядок заполнения;

из одномерного DP — умение сжимать таблицу до dp[w].

В этой статье разберём два близких семейства:

subset sum / 0/1 knapsack: каждый элемент можно взять не более одного раза

coin change / unbounded knapsack: каждую монету можно взять сколько угодно раз

И отдельно подчеркнём важную развилку: мы можем искать

оптимум (минимум/максимум)

достижимость (можно/нельзя)

число способов (сколько вариантов)

Полезные задачи на LeetCode:

Coin Change

Coin Change II

Partition Equal Subset Sum

Target Sum

Last Stone Weight II

Что такое рюкзак в терминах DP

Есть набор “предметов” (чисел, монет, весов), и есть параметр “ёмкость” или “сумма” .

Дальше вы выбираете одну из двух моделей:

0/1: предмет можно взять 0 или 1 раз

unbounded: предмет можно брать неограниченно

И выбираете тип ответа:

boolean: достижима ли сумма

min/max: оптимальное значение при сумме/весе

count: сколько способов набрать сумму

Ключевой навык для LeetCode: одна и та же “задача про суммы” меняется на 180 градусов из-за направления цикла по .

!Наглядно показывает, почему в 0/1 нужен обратный цикл по сумме, а в unbounded — прямой

Два способа хранить состояние: 2D и 1D

2D состояние как “учебный вариант”

Частая формулировка:

dp[i][w] = ответ, если мы рассматриваем первые i предметов и хотим получить сумму w

Плюсы:

проще доказать корректность

меньше шансов ошибиться с порядком

Минусы:

память

1D состояние как “боевой вариант”

Очень часто можно сжать до:

dp[w] = ответ для суммы w после обработки некоторого количества предметов

Но тогда становится критичным:

в каком порядке вы обновляете dp[w]

0/1 rюкзак: subset sum и достижимость

Классический смысл subset sum:

дан массив nums

можно ли выбрать подмножество с суммой target?

На LeetCode это встречается, например, в Partition Equal Subset Sum: нужно понять, можно ли набрать сумму sum(nums) / 2.

Состояние

Берём boolean DP:

dp[w] = True, если сумму w можно набрать из уже обработанных элементов

База

dp[0] = True

Объяснение: сумму 0 всегда можно набрать, выбрав пустое подмножество.

Переход

Обрабатываем очередное число x. Тогда сумма w становится достижима, если раньше была достижима сумма w - x.

Формально:

Пояснение каждого элемента:

слева — “достижима ли сумма теперь”

справа — “она могла быть достижима и без нового элемента”

— “если раньше мы могли набрать , то добавлением получим ”

— логическое “или”, потому что достаточно любого способа

Самое важное: порядок по w в 0/1

В 0/1 модели элемент x нельзя использовать дважды. Поэтому w нужно перебирать в обратном порядке:

от target вниз до x

Иначе, при прямом проходе, вы можете “увидеть” только что обновлённое dp[w-x] и тем самым использовать x повторно в рамках одной итерации.

Реализация: Partition Equal Subset Sum

Unbounded рюкзак: Coin Change как оптимизация

В Coin Change нужно набрать сумму amount монетами coins, причём каждую монету можно брать сколько угодно раз. Нужно минимальное число монет.

Состояние

dp[w] = минимальное число монет, чтобы набрать сумму w

База

dp[0] = 0

Пояснение: чтобы набрать сумму 0, монеты не нужны.

Остальные суммы изначально считаем недостижимыми:

dp[w] = INF для w > 0

INF — достаточно большое число, чтобы минимум корректно работал.

Переход

Если последняя взятая монета имеет номинал c, то до неё мы должны были набрать w - c.

Тогда:

Пояснение каждого элемента:

слева — “лучший найденный минимум для суммы ”

справа в первом аргументе min — “оставить как было, возможно уже оптимально”

— “лучший минимум для суммы, которая остаётся после добавления монеты c”

— “мы добавили одну монету номинала c”

— выбираем вариант с меньшим числом монет

Порядок циклов в unbounded

Так как монету можно использовать много раз, логично разрешить повторное использование “в рамках обработки этой же монеты”. Поэтому w идёт вперёд:

от c до amount

Реализация: Coin Change

Coin Change II: подсчёт способов (комбинации)

В Coin Change II нужно посчитать, сколькими способами можно набрать amount, если монеты можно брать сколько угодно раз.

Тут типичный поворот: вместо min используем сумму способов.

Что именно считаем: комбинации, а не перестановки

В Coin Change II “способ” обычно означает комбинацию, то есть порядок монет не важен:

2 + 1 + 1 и 1 + 2 + 1 считаются одним способом

DP это обеспечивает, если:

внешний цикл идёт по монетам

внутренний по сумме

Состояние

dp[w] = число способов набрать сумму w из уже обработанных номиналов

База

dp[0] = 1

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

Переход

Добавляя монету c, для каждой суммы w мы можем дописать к любому способу набрать w - c ещё одну монету c.

Пояснение каждого элемента:

слева — “новое число способов набрать ”

справа — “способы, которые были без использования текущей монеты c”

— “способы набрать меньшую сумму, к которым мы добавляем монету c”

— потому что мы складываем количества независимых вариантов

Реализация: Coin Change II

Один и тот же “рюкзак”, но разные ответы

Ниже — шпаргалка, которая помогает не путаться, что ставить в dp и что делать в переходе.

| Задача | Модель | dp[w] означает | База | Переход | |---|---|---|---|---| | Достижимость суммы | 0/1 | можно ли набрать w | dp[0]=True | dp[w] = dp[w] or dp[w-x] | | Минимум монет | unbounded | минимум монет на w | dp[0]=0, остальное INF | dp[w] = min(dp[w], dp[w-c] + 1) | | Кол-во способов | unbounded | сколько способов на w | dp[0]=1 | dp[w] += dp[w-c] |

Главная связь с прошлыми статьями:

смысл операции в переходе (логическое “или”, min, +) всегда должен соответствовать тому, что означает dp

Частые ошибки на LeetCode

Неправильный dp[0] в подсчёте способов: если поставить dp[0]=0, то “не из чего” строить ответы, и всё останется нулём.

Перепутали направление цикла по w:

- 0/1: w назад, чтобы не использовать элемент дважды - unbounded: w вперёд, чтобы можно было использовать монету повторно

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

INF слишком маленький в задачах на минимум: он должен быть заведомо больше любого возможного ответа.

Итоги

Рюкзак в DP — это задачи, где ключевой параметр состояния: сумма/ёмкость w.

Различайте модели:

- 0/1: каждый элемент максимум один раз - unbounded: элемент можно использовать сколько угодно

Различайте тип ответа:

- достижимость: логическое “или” - оптимум: min или max - количество способов: сумма количеств

В одномерной оптимизации решает всё порядок обхода w.

Этот паттерн дальше естественно расширяется в более сложные темы: DP с несколькими параметрами (например, dp[i][w] с восстановлением решения), а также задачи, где к “сумме” добавляются дополнительные ограничения.

DP по деревьям и графам: состояния на вершинах

В предыдущих статьях курса мы привыкли к DP, где состояние “живёт” в индексе массива (dp[i]), паре индексов (dp[i][j]) или сумме (dp[w] в рюкзаке). Следующий важный шаг для LeetCode — задачи, где естественная “ось” индексации не линейная, а структурная: вершины дерева или вершины графа.

В этой статье разберём паттерн DP на вершинах:

как “превратить” дерево в DP-таблицу

как выбирать состояние на вершине

как безопасно делать переходы по рёбрам

когда такой подход работает для графов (DAG) и почему ломается на циклах

Полезные задачи для практики:

House Robber III

Binary Tree Maximum Path Sum

Longest Increasing Path in a Matrix

Почему “состояние на вершине” — это DP

В дереве и графе ответ для вершины часто выражается через ответы для соседних вершин.

В дереве нет циклов, поэтому зависимости можно организовать как “снизу вверх” (от листьев к корню).

В DAG (ориентированном ациклическом графе) нет циклов по направлению рёбер, поэтому зависимости можно считать в топологическом порядке.

Ключевая идея та же, что и раньше:

состояние: что означает dp[u] или dp[u][k] для вершины u

переход: как собрать dp[u] из дочерних/соседних состояний

база: что делать на листьях / тупиках

порядок вычисления: пост-обход дерева или топологический порядок в DAG

DP по дереву

Договоримся: корень, родитель и дети

Чтобы делать DP по дереву, почти всегда удобно укоренить его.

В бинарном дереве на LeetCode корень уже задан.

В обычном дереве (граф без циклов) вы выбираете любой корень, например 0, и дальше определяете:

- parent[u] — родитель вершины u - children[u] — соседи, кроме родителя

Почему это важно:

если просто обходить соседей, в неориентированном дереве вы будете “ходить туда-сюда” и получите бесконечную рекурсию

корень задаёт направление зависимостей “ребёнок -> родитель”, что делает порядок вычисления понятным

!Схема укоренённого дерева и идея двух состояний на вершине

Самый частый паттерн: “взять вершину или не взять”

Это структурный аналог одномерного DP “выбор/не выбор” (как в House Robber), только вместо индекса i у нас вершина u.

Идея:

если мы берём вершину, некоторые соседние вершины брать нельзя

если мы не берём вершину, у соседей может быть больше свободы

Обычно это приводит к 2 состояниям на вершине:

dp[u][0] — лучший ответ в поддереве u, если вершину u не берём

dp[u][1] — лучший ответ в поддереве u, если вершину u берём

Под “лучшим ответом” может быть максимум суммы, максимум количества выбранных вершин и так далее.

Пример: House Robber III

Задача House Robber III: дома расположены в бинарном дереве, нельзя грабить два связанных ребром дома (родитель-ребёнок).

Состояние

Определим:

dp[u][0] — максимальная сумма в поддереве вершины u, если u не грабим

dp[u][1] — максимальная сумма в поддереве вершины u, если u грабим

Переход

Пусть у u дети left и right.

1) Если u грабим, то детей грабить нельзя. Значит:

Пояснение каждого элемента:

— лучший результат при условии “u грабим”

— деньги в текущем доме u

— при ограблении u левый ребёнок обязан быть “не ограблен”

— аналогично для правого ребёнка

сумма, потому что поддеревья детей независимы (связь только через u)

2) Если u не грабим, то для каждого ребёнка можно выбрать лучший из двух режимов (грабим/не грабим):

Пояснение каждого элемента:

— лучший результат при условии “u не грабим”

— лучший вариант для левого поддерева без ограничений со стороны u

— то же для правого

сумма, потому что выбор в левом и правом поддереве независим

База

Для пустого ребёнка (None) удобно вернуть (0, 0):

если вершины нет, то максимум в обоих режимах равен 0

Порядок вычисления

Нам нужны значения детей, чтобы посчитать родителя, значит нужен пост-обход: сначала дети, потом текущая вершина.

Реализация (рекурсия)

Практический комментарий:

здесь мемоизация не нужна, потому что бинарное дерево не содержит повторного посещения одной и той же вершины (если нет “общих” поддеревьев)

на общих графах это уже не так, и там кэш становится важным

Другое дерево-DP: когда состояние одно, но нужен “глобальный ответ”

Не всегда в дереве нужно два режима. Иногда dp[u] — это локальная величина, а итоговый ответ считается отдельной переменной.

Пример: Binary Tree Maximum Path Sum

Задача Binary Tree Maximum Path Sum: найти максимальную сумму по пути в дереве, где путь может начинаться и заканчиваться в любых вершинах, но должен идти по рёбрам.

Здесь удобно разделить две вещи:

“какой лучший путь вниз из u” (его можно отдавать родителю)

“какой лучший путь вообще” (его нельзя просто отдать родителю, потому что он может “разветвляться” в u)

Обычно делают так:

down(u) — максимальная сумма пути, который обязательно начинается в u и идёт вниз в одну сторону (в одного ребёнка)

глобальная переменная best обновляется значением “путь через u”, который может включать и левую, и правую ветку

Смысловая причина такого разделения:

родителю можно продолжить путь только по одному ребру вниз, нельзя “тащить” вверх путь, который уже пошёл в две стороны

Это тоже DP “на вершине”, просто состояние возвращаемое из dfs отличается от итогового ответа задачи.

Как обобщить дерево-DP на произвольное дерево (не бинарное)

Если дерево задано как список рёбер edges (неориентированный граф без циклов), обычно делают так:

Строят список смежности g.

Запускают dfs(u, parent).

В переходе перебирают всех соседей v и пропускают parent.

Состояния dp[u][0] и dp[u][1] при этом считаются одинаково, только вместо left/right будет цикл по детям.

DP по графам: когда это работает

Главная граница: циклы

DP как “заполнение состояний по зависимостям” работает, когда зависимости не образуют замкнутый круг.

В дереве циклов нет.

В DAG циклов нет (если идти по направлению рёбер).

В общем графе с циклами часто нельзя честно определить dp[u] через “меньшие” состояния, потому что нет естественного порядка.

Это не значит, что на графах не бывает DP, но обычно требуется дополнительная структура:

топологический порядок (DAG)

“слои” по расстоянию (иногда)

битмаски (DP по подмножествам)

или вообще другие алгоритмы (например, Дейкстра для кратчайших путей)

В этой статье сфокусируемся на DAG-подобной ситуации: у состояния вершины есть направленные зависимости на уже посчитанные вершины.

DP на DAG: состояние dp[v] и топологический порядок

Типовая постановка:

дан направленный граф без циклов

нужно найти максимум/минимум по пути (длина, сумма, стоимость)

Обычно задают:

dp[v] — лучший результат для пути, который заканчивается в v

И переход:

если в v можно прийти из u, то кандидат для dp[v] строится из dp[u]

Чтобы это работало, вершины нужно обрабатывать в порядке, где все u уже посчитаны. Это и есть топологический порядок.

Два способа посчитать DP в DAG

Через топологическую сортировку (Kahn или DFS-order) и затем один проход по вершинам.

Через DFS + мемоизацию: f(v) вызывает f(to) по направлению рёбер, а кэш не даёт пересчитывать.

Оба способа популярны на LeetCode.

Пример “граф скрыт в матрице”: Longest Increasing Path in a Matrix

Задача Longest Increasing Path in a Matrix: из клетки можно ходить в 4 стороны, но только в клетку со строго большим значением.

Ключевое наблюдение:

если разрешены переходы только в большее значение, то циклы невозможны

значит это DAG, просто вершины — клетки

Состояние:

dp[i][j] — длина самого длинного возрастающего пути, начинающегося в клетке (i, j)

Переход:

dp[i][j] = 1 + max(dp[ni][nj]) по всем соседям (ni, nj) с большим значением

если таких соседей нет, то dp[i][j] = 1

Здесь удобнее всего писать DFS + мемоизацию, потому что топологический порядок по значениям можно построить, но это сложнее и не нужно.

Типичные ошибки в DP по деревьям и графам

Забыли про родителя в неориентированном дереве: рекурсия уходит в бесконечность. Лечение: dfs(u, parent) и пропуск parent.

Неправильный смысл состояния: например, пытаются в одной переменной одновременно хранить “лучшее в поддереве” и “лучшее, что можно отдать родителю”. Иногда это разные величины (как в Maximum Path Sum).

Пытаются сделать DP на графе с циклами как на DAG: зависимости становятся круговыми. Лечение: доказать ацикличность (или изменить постановку/алгоритм).

Путают порядок вычислений:

- дерево: нужен пост-обход (дети -> родитель) - DAG: нужен топологический порядок (или мемоизация по направлению рёбер)

Итоги

DP “на вершинах” — это тот же подход, что и в массиве, но индексом выступает вершина.

Для дерева почти всегда выбирают корень и считают состояния в пост-обходе.

Очень частый паттерн — два режима на вершине: dp[u][0] и dp[u][1] (взять/не взять).

Для DAG можно делать dp[v] по топологическому порядку или DFS + мемоизацию.

Для графов с циклами такой DP напрямую обычно не применим: сначала нужна структура, которая убирает циклические зависимости.

Продвинутые паттерны: интервальное DP, битмаски, DP+монотоник

До этого в курсе мы решали DP, где ось состояний была “очевидной”: индекс массива (dp[i]), пара индексов (dp[i][j] для сеток и строк), сумма в рюкзаке (dp[w]), вершина дерева/графа. На LeetCode есть задачи, где DP всё ещё строится из тех же кирпичиков (состояние → переход → база → порядок), но правильная ось не так очевидна.

В этой статье разберём три продвинутых паттерна, которые регулярно встречаются в задачах уровня medium/hard:

Интервальное DP: состояние — подотрезок массива.

DP по битмаске (subset DP): состояние — множество уже выбранных элементов.

DP + монотоническая структура: переход “смотрит назад” в окно или на префикс, и его ускоряют деком/стеком.

Полезные задачи на LeetCode для практики по темам статьи:

Интервальное DP: Burst Balloons, Minimum Cost to Cut a Stick

Битмаски: Can I Win, Smallest Sufficient Team

DP+монотоник: Jump Game VI, Constrained Subsequence Sum

Интервальное DP

Интервальное DP — это DP, где состояние описывает отрезок массива или строки.

Обычно состояние выглядит как:

dp[l][r] — ответ для подотрезка с границами l..r (или полуинтервала).

Ключевая трудность (и главный навык): понять, какое событие считать “последним шагом” внутри отрезка, чтобы разложить отрезок на независимые части.

Когда узнаётся интервальное DP

Сигналы, что это оно:

В условии есть операции “удалить элемент”, “разбить отрезок”, “поставить скобки”, “разрезать палку”.

Ответ для большого отрезка можно собрать из ответов для двух подотрезков.

Вариантов последнего шага обычно (выбираем точку разбиения k).

!Как “последний шаг” внутри интервала разбивает задачу на две независимые подзадачи

Классический приём: выбирать “последний” элемент/разрез

Очень часто проще думать не “что сделать первым”, а что сделать последним внутри интервала. Тогда всё вокруг “последнего” уже независимо решено.

#### Пример: Burst Balloons

Задача Burst Balloons: есть шары с числами, при лопании шара k получаем nums[left] nums[k] nums[right], где left/right — ближайшие ещё не лопнувшие шары. Нужно максимум монет.

Главная проблема: “соседи” шара меняются со временем, поэтому прямой DP по индексу ломается.

Решение: выбрать последний лопнутый шар в интервале.

##### Подготовка массива

Добавим фиктивные шары со значением 1 по краям:

a = [1] + nums + [1]

Так мы всегда можем умножать на “соседей”, и границы стабильны.

##### Состояние

Будем использовать открытый интервал:

dp[l][r] = максимальные монеты, которые можно получить, если лопать шары строго между индексами l и r (то есть l < k < r).

Важно: шары l и r не лопаем в этой подзадаче — они играют роль фиксированных границ.

##### Переход

Пусть k — последний шар, который мы лопаем внутри (l, r).

Тогда:

всё внутри (l, k) уже лопнули оптимально и дали dp[l][k]

всё внутри (k, r) уже лопнули оптимально и дали dp[k][r]

в момент, когда лопаем k последним, его соседями гарантированно являются l и r, значит монеты за последний шаг: a[l] a[k] a[r]

Итоговый переход:

Пояснение каждого элемента:

— лучший результат для интервала между границами l и r.

— индекс шара, который выбираем “последним” в этом интервале.

— максимум монет, если сначала оптимально “очистить” левую часть.

— максимум монет, если сначала оптимально “очистить” правую часть.

— монеты за финальный хлопок шара k, когда его соседи уже точно l и r.

— потому что мы ищем максимум.

##### База

Если между l и r нет шаров (то есть r = l + 1), то:

dp[l][r] = 0

Потому что лопать нечего.

##### Порядок вычисления

Нужно, чтобы dp[l][k] и dp[k][r] были посчитаны раньше dp[l][r].

Самый удобный порядок:

Перебирать длину интервала len от маленькой к большой.

Для каждой пары (l, r) такой длины перебирать k внутри.

##### Реализация (bottom-up)

##### Типичные ошибки в интервальном DP

Неправильно выбран смысл интервала (закрытый/открытый), и “последний шаг” перестаёт фиксировать соседей.

Неверный порядок вычисления: интервалы должны считаться от меньших к большим.

Путают “разбиение по k” с “добавлением по k”: здесь k именно разделяет задачу на две независимые.

DP по битмаске (subset DP)

Битмаска — это число, в двоичной записи которого мы кодируем, какие элементы множества уже выбраны.

Если mask — битовая маска длины n, то бит i равен 1, когда элемент i уже “внутри состояния”.

Этот паттерн применим, когда:

n маленькое (обычно до 20–22, иногда до 25 при аккуратной оптимизации)

нужно учитывать “какие именно элементы уже использованы”, а не только их количество

Типичная оценка числа состояний:

всего масок

И переход часто добавляет/убирает один элемент, давая множитель n, то есть .

Когда это узнаётся

Сигналы:

“каждый элемент можно использовать не более одного раза”, но важно какие именно.

“нужно покрыть набор навыков/условий минимальным набором объектов”.

“игра/выбор ходов” с небольшим n, где состояние = какие ходы уже сделаны.

Пример: Can I Win (мемоизация по маске)

Задача Can I Win: есть числа 1..maxChoosableInteger, игроки по очереди выбирают ещё не выбранное число и прибавляют к сумме. Кто первым достигнет desiredTotal, тот победил. Нужно определить, выигрывает ли первый игрок при оптимальной игре.

#### Состояние

mask — какие числа уже взяты.

remain — сколько осталось набрать до desiredTotal.

Замечание: remain однозначно определяется mask, если мы знаем исходный desiredTotal, но на практике часто оставляют оба параметра для ясности. На LeetCode достаточно кэшировать по mask.

Определим функцию:

win(mask, remain) = может ли текущий игрок гарантированно выиграть из этого состояния.

#### Переход

Текущий игрок пробует взять любое число x, которого ещё нет в mask.

Если x >= remain, то он выигрывает сразу.

Иначе он передаёт ход сопернику в состоянии (mask | (1<<x), remain - x).

Если существует ход, после которого соперник не может выиграть, то текущий игрок выигрывает.

#### База

Если есть x >= remain, это немедленный выигрыш.

Явного remain <= 0 обычно не нужно, потому что мы перехватываем выигрывающий ход на шаг раньше.

#### Реализация (top-down + кэш)

#### Что важно понимать

Состояние “какие числа взяты” невозможно сжать до одного индекса, потому что важен набор, а не позиция.

Это структурно похоже на DP по графам из прошлой статьи: mask — вершина графа состояний, ребро — “взять число x”.

Ещё один очень типичный формат: минимизация/оптимизация по маске

Например, в Smallest Sufficient Team можно делать:

dp[mask] = минимальная команда (список людей), которая покрывает набор навыков mask.

Это уже “рюкзак по маске”: состояние — не сумма, а покрытые навыки.

DP + монотоническая структура

Иногда DP-переход выглядит так:

dp[i] зависит от максимума/минимума на диапазоне предыдущих dp[j]

Примерный вид:

dp[i] = value[i] + max(dp[j]) для j в окне [i-k, i-1]

Если считать максимум перебором k предыдущих значений, получится и TLE.

Трюк: поддерживать кандидатов на максимум в монотонической очереди (deque).

Пример: Jump Game VI

Задача Jump Game VI: из позиции i можно прыгнуть на i+1..i+k. Нужно максимизировать сумму значений nums по пути до конца.

#### Состояние

dp[i] = максимальная сумма, если мы пришли в i.

#### Переход

В i можно прийти из любой позиции j в диапазоне [i-k, i-1].

Значит:

Пояснение частей формулы:

— лучший результат на позиции i.

— вклад текущей клетки.

— лучший результат на предыдущей позиции j, откуда можно допрыгнуть.

— выбираем, откуда прийти выгоднее.

#### Как ускорить максимум: монотоническая очередь

Будем хранить в деке индексы j так, чтобы:

индексы в деке идут слева направо по времени (возрастают)

значения dp[j] в деке идут слева направо по убыванию

Тогда максимум на окне всегда в начале дека.

Операции на каждом i:

Удалить из начала дека индексы, которые вышли из окна (j < i-k).

Взять dp[deque[0]] как максимум.

Посчитать dp[i].

Пока хвост дека имеет dp[tail] <= dp[i], выкинуть хвост (они больше никогда не станут максимумом).

Добавить i в хвост.

!Как дек поддерживает максимум dp[j на скользящем окне]

#### Реализация

Как узнавать “DP+монотоник” в задачах

Сигналы:

В переходе есть max/min по диапазону j.

Диапазон “двигается” с ростом i (скользящее окно).

В лоб получается или .

Важно различать структуры:

Монотоническая очередь (deque) — когда окно скользит, и нужно выбрасывать устаревшие элементы.

Монотонический стек — когда вам нужен “предыдущий меньший/больший” элемент и однонаправленная обработка.

В этой статье мы сфокусировались на деке, потому что он напрямую ускоряет DP на окне.

Сводная шпаргалка по паттернам

| Паттерн | Тип состояния | Тип перехода | Порядок вычисления | Типичные сложности | |---|---|---|---|---| | Интервальное DP | dp[l][r] | перебор k внутри интервала | по длине интервала | | | Битмаска DP | dp[mask] или f(mask) | добавить/убрать элемент | часто top-down + кэш | | | DP+монотоник | dp[i] + структура | max/min по диапазону | слева направо | или |

Итоги

Интервальное DP почти всегда строится вокруг идеи “выбрать последний шаг внутри интервала”, чтобы разложить задачу на два независимых подинтервала.

DP по битмаске кодирует множество выбранных элементов и особенно полезно при маленьком n, когда важен именно набор, а не позиция.

DP+монотоническая структура ускоряет переходы вида “взять максимум/минимум по скользящему окну” и превращает в .

Эти паттерны продолжают ту же линию курса: успех в DP на LeetCode определяется не “знанием формул”, а дисциплиной формулировки состояния и честным перечислением вариантов последнего шага — после чего остаётся подобрать правильный порядок и оптимизацию.