← вся теориятеория к собесу · Алгоритмы и структуры данных

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

Зачем это спрашивают

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

Типовые формулировки: «минимальное число монет на сумму», «самая длинная общая подпоследовательность», «рюкзак».

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

Когда динамика и из чего состоит ответ

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

Рецепт ответа состоит из пяти пунктов, и их стоит произносить вслух именно в таком порядке. Что такое состояние - минимум информации, полностью описывающий подзадачу. Каков переход - как ответ состояния выражается через меньшие. Что база. В каком порядке считать. Где в итоге лежит ответ.

Разберём на задаче про грабителя, который не может обносить два соседних дома. Состояние: максимум, который можно вынести из первых i домов. Переход: либо пропускаем i-й дом и берём ответ для i−1, либо берём его и прибавляем ответ для i−2. База: для нуля домов ноль, для одного - его стоимость. Порядок: слева направо. Ответ: в последнем состоянии. Пять пунктов названы, задача решена.

// Два стиля с одинаковой сложностью «число состояний, умноженное на работу на один переход». Сверху вниз - рекурсия с кешем, состояние выводится само по параметрам функции. Снизу вверх - таблица, зато полный контроль над порядком и возможностью сжать память.

Классика и сжатие памяти

Одномерная классика: лестница и числа Фибоначчи, тот самый грабитель домов, число путей до клетки. Состояние - одно число, переход смотрит на одно-два предыдущих.

Двумерная классика: LCS (longest common subsequence) и расстояние Левенштейна. Состояние - пара индексов, «сколько символов первой строки и сколько второй мы уже разобрали». Сюда же пути в сетке с препятствиями.

Память сжимается почти всегда, и это дежурный дополнительный вопрос. Если переход смотрит только на предыдущую строку таблицы, хранить всю таблицу незачем - достаточно двух строк, а иногда и одной. Двумерная таблица O(n·m) схлопывается в O(m), и это разница между «влезло в память» и «не влезло».

// LIS (longest increasing subsequence) - типовое усложнение для мидла. Очевидная динамика решает её за O(n²), а хитрое решение с массивом «минимальных хвостов» и бинарным поиском по нему - за O(n log n). Ждать его будут именно как продолжение разговора.

Рюкзак и честность жадности

Рюкзак 0/1: есть предметы с весом и ценностью, есть вместимость, каждый предмет можно взять только целиком и только один раз. Состояние - пара «номер предмета, оставшаяся вместимость», сложность O(n·W).

И вот тут любимая ловушка. O(n·W) выглядит как полином, но W - это ЧИСЛО, а в условие оно записывается своими цифрами, то есть длина записи - логарифм от величины. Прибавь к вместимости один разряд, и таблица вырастет в десять раз. Относительно длины входа это экспонента, поэтому такую сложность называют псевдополиномиальной, а сам рюкзак остаётся NP-трудной задачей - из класса, для которого быстрого алгоритма никто не знает.

Жадность вместо динамики требует доказательства, и это не занудство. Монеты номиналом 1, 3 и 4, набрать надо 6. Жадный алгоритм берёт самую крупную: 4, потом 1, потом 1 - три монеты. Оптимум же 3 плюс 3, то есть две. Красивое жадное решение без обоснования на собесе - мина, которую обязательно подорвут.

// Деталь сжатого рюкзака, на которой валятся при переписывании в одномерный массив: обходить вместимости нужно справа налево. Слева направо тот же предмет успевает взяться дважды, и получается уже другая задача - рюкзак с неограниченным числом копий.

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

Как отвечать: «Как подступаешься к задаче на динамическое программирование?»

По процедуре из пяти шагов. Формулирую состояние - минимум информации, который полностью описывает подзадачу; выписываю переход, то есть как ответ состояния собирается из меньших; базу; порядок вычисления; и где лежит финальный ответ. Начинаю всегда сверху вниз: пишу честную рекурсию и навешиваю на неё кеш по аргументам. Так состояние выводится само, из параметров функции, а не угадывается разглядыванием таблицы - и это сильно надёжнее под давлением на собесе. Если потом жмёт память или нужна скорость, переворачиваю в таблицу и сжимаю её до последних строк. И отдельно проверяю соблазн решить жадно: без доказательства жадность мина, монеты номиналом 1, 3 и 4 на сумме 6 её ломают.

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

На чём валят

−Начинать с таблицы, не сформулировав состояние: надёжнее рекурсия с кешем, состояние выведется само.
−Предложить жадное решение без доказательства: монеты 1, 3, 4 на сумме 6 ломают его сразу.
−Перепутать порядок вычисления снизу вверх: переход читает клетки, которые ещё не посчитаны.
−Обходить сжатый рюкзак 0/1 слева направо: предмет берётся дважды, задача подменяется.
−Считать O(n·W) полиномом: это псевдополином, и рюкзак остаётся NP-трудным.

Проверьте себя

Пять вопросов из банка по этой подтеме. Всего их 12, остальные разбираются в тренажёре.

#dynamic_programming1 / 5
Задачи LCS (наибольшая общая подпоследовательность) и edit distance решают таблицей dp[i][j]. Что это за таблица?
A)Одномерный массив по длине одной из строк, куда пишут промежуточные совпадения символов второй строки
B)Хеш-таблица пар символов
C)Двумерная: dp[i][j] по префиксам длины i и j; ячейка выражается через соседей, сложность O(m·n)
D)Дерево отрезков по символам строки
показать ответ и разбор
+C)Двумерная: dp[i][j] по префиксам длины i и j; ячейка выражается через соседей, сложность O(m·n)
// разбор: Для задач над двумя последовательностями состояние двумерно: dp[i][j] хранит ответ для префиксов длиной i и j. Переход смотрит на соседние ячейки — совпали символы (берём диагональ +1) или нет (лучшее из верхней/левой, для edit distance +1 за операцию). Заполняя таблицу m×n, получаем ответ в углу за O(m·n) времени; память тоже O(m·n), но её часто сжимают до двух строк (rolling).
#dynamic_programming2 / 5
Для размена суммы минимальным числом монет жадность (брать самую крупную) не всегда даёт оптимум. Почему и что помогает?
A)Жадный выбор самой крупной монеты оптимален при произвольных номиналах, так что задача не представляет сложности
B)Крупная монета может отрезать путь к оптимуму (номиналы 1,3,4 на 6: 4+1+1 против 3+3); минимум даёт DP
C)Помогает только сортировка монет по убыванию
D)Задача неразрешима
показать ответ и разбор
+B)Крупная монета может отрезать путь к оптимуму (номиналы 1,3,4 на 6: 4+1+1 против 3+3); минимум даёт DP
// разбор: Жадный размен оптимален лишь для «канонических» систем номиналов (как рубли/доллары). При произвольных номиналах он ломается: взяв самую крупную монету, можно застрять с плохим остатком. Классический контрпример — номиналы {1,3,4}, сумма 6: жадно 4+1+1 (3 монеты), а оптимально 3+3 (2). DP по всем суммам от 0 до целевой (dp[x] = 1 + min по монетам dp[x−монета]) гарантирует минимум за O(сумма·число_номиналов).
#dynamic_programming3 / 5
Задачу о рюкзаке 0/1 решают за O(n·W) DP-таблицей. Почему это не «полиномиальный» алгоритм в строгом смысле?
A)Дело исключительно в памяти: таблица размера n·W не помещается в кэш, хотя по времени алгоритм полиномиален
B)Потому что алгоритм на самом деле экспоненциален по времени
C)Псевдополиномиальность: полином от ЗНАЧЕНИЯ W, а не от размера входа в битах; при большом W неподъёмно
D)Потому что DP здесь неприменимо и ответ неверен
показать ответ и разбор
+C)Псевдополиномиальность: полином от ЗНАЧЕНИЯ W, а не от размера входа в битах; при большом W неподъёмно
// разбор: Время O(n·W) выглядит полиномиальным, но W — это значение вместимости, а размер входа — число битов для его записи (log W). Сложность, полиномиальная от значения, но экспоненциальная от длины записи, называют псевдополиномиальной. Поэтому при огромном W (не помещающемся в разумную таблицу) метод не масштабируется, что согласуется с NP-трудностью 0/1-рюкзака. Для больших W берут приближённые схемы (FPTAS).
#dynamic_programming4 / 5
Наибольшая возрастающая подпоследовательность (LIS): чем отличаются решения за O(n²) и O(n log n)?
A)Обе версии — это буквально один и тот же алгоритм, а разница в записи сложности возникла лишь исторически
B)O(n log n) требует предварительной сортировки, что меняет ответ
C)O(n²) сравнивает со всеми предыдущими; O(n log n) ведёт массив хвостов и бинарный поиск по нему
D)O(n²) даёт неверный результат, поэтому берут O(n log n)
показать ответ и разбор
+C)O(n²) сравнивает со всеми предыдущими; O(n log n) ведёт массив хвостов и бинарный поиск по нему
// разбор: Прямое DP за O(n²): для каждого i берём лучший ответ среди всех j<i с меньшим значением. Ускорение до O(n log n): поддерживаем массив tails, где tails[k] — минимально возможный последний элемент возрастающей подпоследовательности длины k+1. Для очередного элемента бинарным поиском находим позицию замены — это держит массив отсортированным и даёт длину LIS. Оба дают верную длину, второй быстрее на больших n.
#dynamic_programming5 / 5
Когда DP-решение можно сжать по памяти с O(n) (или O(n·m)) до меньшего?
A)Память DP сокращать нет смысла: таблица переходов всё равно нужна целиком до самого конца вычисления
B)Когда переход зависит лишь от нескольких последних состояний — хранят их, а не весь массив (rolling)
C)Только если все значения одинаковы
D)Память сжимается автоматически сборщиком мусора
показать ответ и разбор
+B)Когда переход зависит лишь от нескольких последних состояний — хранят их, а не весь массив (rolling)
// разбор: Если рекуррентность обращается лишь к нескольким недавним состояниям, всю таблицу хранить незачем. Для fib достаточно двух переменных вместо массива. Для двумерного DP, где dp[i][*] зависит только от dp[i−1][*], хватает двух строк (или даже одной при аккуратном порядке) — приём rolling array снижает память с O(n·m) до O(m). Платой обычно становится потеря возможности восстановить само решение (только его стоимость).

дальше

Теорию прочитали. Навык ставится повторением

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

Открыть тренажёр Вся тема: Алгоритмы и структуры данных