pattern heroPT–23LeetCode Extension

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

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

Вариант
P21 Динамическое программирование (DP)Одномерный массив · 1×

Пример задачи: больше всего денег из домов [3, 7, 3, 2, 6, 8, 6, 1], если нельзя грабить соседние дома.

домаbest0317233246586671
этот шагзаполненоберём отсюдане грабимответ

Пустая таблица, по ячейке на дом

best = [–, –, –, –, –, –, –, –]i = –skip = –take = –
01/28
сначала · назад · пуск · шаг
Скорость
1function rob(money):
2 best = new array of size len(money)
3 best[0] = money[0]
4 best[1] = max(money[0], money[1])
5 for i from 2 to len(money) - 1:
6 skip = best[i - 1]
7 take = best[i - 2] + money[i]
8 best[i] = max(skip, take)
9 return best[len(money) - 1]

← → шаг · пробел — пауза

Как узнать

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

Как решать такие задачи

  1. Сформулируй, что значит одна ячейка: best[i] — ответ для первых i + 1 элементов.
  2. Запиши, как ячейка получается из прежних, глядя на последний выбор.
  3. Заполни базовые случаи, потом ячейки в таком порядке, чтобы всё, что ячейка читает, уже было готово.
  4. Возьми ответ из последней ячейки. Чтобы сэкономить память, храни только те ячейки, которые ещё читаешь.

Вариант: Двумерная таблица

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

  1. Сформулируй, что значит одна клетка: dp[r][c] — ответ для части сетки, которая кончается в (r, c).
  2. Найди базовые случаи: первая строка и первый столбец, куда ведёт только один ход.
  3. Запиши переход по последнему ходу: здесь dp[r][c] = dp[r - 1][c] + dp[r][c - 1].
  4. Заполняй таблицу в таком порядке, чтобы всё, что клетка читает, было готово: по строкам слева направо.
  5. Возьми ответ из последней клетки. Клетка читает только свою строку и строку над ней, так что хватит одной строки, обновляемой на месте.

Вариант: Лучший подмассив

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

  1. Храни два числа: here — лучшая сумма отрезка, который кончается в текущем индексе, и best — наибольшее here на данный момент.
  2. На каждом числе выбирай большее: продлить отрезок (here + x) или начать новый с x.
  3. Обновляй best после каждого шага и верни его в конце.
  4. Кольцевой массив: ответ — либо обычный отрезок, либо сумма всех чисел минус самый маленький отрезок, который ищется так же, только через min. Если все числа отрицательные, бери обычный.
  5. Одна покупка и продажа акции — та же идея: храни самую низкую цену на данный момент и проверяй прибыль, если продать сегодня.

Вариант: Две строки

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

  1. Заведи таблицу: строка на каждый префикс первой строки, столбец на каждый префикс второй, пустой префикс тоже считается.
  2. Заполни края: чтобы превратить префикс в пустую строку или наоборот, нужно столько правок, сколько в нём букв.
  3. Для остальных клеток сравни последние буквы и посмотри на диагональ, клетку сверху и клетку слева.
  4. Ответ — в правой нижней клетке. Пройди по стрелкам назад, чтобы восстановить сами правки.
  5. Наибольшая общая подпоследовательность (LCS) и Interleaving String решаются той же таблицей префиксов, меняется только правило для клетки.

Вариант: Состояния

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

  1. Перечисли состояния, в которых можно оказаться в конце дня, и что переводит из одного в другое.
  2. Для каждого состояния храни одно число: лучшие деньги, какие можно иметь в нём после этого дня.
  3. Каждый день состояние берёт большее из двух: остаться прежним или прийти из предыдущего состояния по сегодняшней цене.
  4. Не больше k сделок: храни массивы buy[1..k] и sell[1..k] и обновляй их так же, это O(n·k) по времени.
  5. Сделок сколько угодно: всего два состояния, hold и free. hold = max(hold, free - p), free = max(free, hold + p).

Где встречается

  • Переносы строк в TeX. TeX выбирает, где разорвать строки, сразу для всего абзаца: для каждого возможного места разрыва он запоминает лучший способ до него дойти.
  • Сравнение ДНК. Алгоритмы Нидлмана — Вунша и Смита — Ватермана выравнивают две последовательности ДНК по таблице, где каждая клетка — лучший ответ для начал двух последовательностей. В пакете EMBOSS это программы needle и water.
  • Мобильная связь и Wi-Fi. Алгоритм Витерби расшифровывает сигнал с помехами: на каждом шаге он хранит лучший путь до каждого состояния, а не перебирает все цепочки.