Где применяется
1. Задача
На билд-ферме (группе серверов, которые собирают код) n машин и n заданий. Каждая машина выполняет каждое задание со своей скоростью, поэтому cost[i][t] это оценка в минутах, за сколько машина i выполнит задание t. Нужно раздать задания так, чтобы каждая машина получила ровно одно, а суммарное время было наименьшим.
Перебор всех расстановок это n! вариантов, а n! растёт очень быстро: при n = 12 это уже 479 001 600. Жадный способ тоже не годится: «каждая машина по очереди берёт самое быстрое из свободных заданий». Возьми cost = [[1, 2], [1, 9]]. Машина 0 берёт задание 0 за 1 минуту, машине 1 остаётся задание 1 за 9 минут, итого 10. А если машина 0 возьмёт задание 1 (2 минуты), машина 1 возьмёт задание 0 (1 минута), итого 3. Дешёвый ранний выбор заставил сделать дорогой поздний.
Выручает то, что n здесь маленькое: машин в стойке, скажем, десяток. Когда элементов мало, можно компактно хранить ответ на вопрос «какие задания уже заняты».
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитКак узнать
Эти слова в условии значат этот паттерн
- лучшее/максимум/минимум, заканчивающееся в позиции i
- число способов дойти, подняться или замостить
- нельзя брать два соседних элемента
- минимальная стоимость пути по сетке
- повторяющиеся подзадачи, одно и то же состояние считается заново
Похоже, но не то
- Рекурсия с мемоизацией (Recursion with memoization)
Мемоизация заполняет ту же таблицу сверху и по требованию. Здесь она заполняется снизу в заданном порядке.
- Жадный алгоритм (обменный аргумент) (Greedy (exchange argument))
Жадность выбирает один вариант на шаг. Динамика держит все варианты до конца.
- Рекурсия (Recursion)
Рекурсия показывает, каким будет переход. Скорость даёт именно таблица.
- DP над подпоследовательностями (LIS / LCS / расстояние редактирования) (DP on subsequences (LIS / LCS / edit distance))
Там состояние это пара позиций в двух последовательностях. Здесь хватает одного индекса.
n состояний по O(1) работы дают O(n). Память падает до O(1), когда важны только последние состояния.
На LeetCode
Задачи на распределение и обход до примерно 15 элементов, где состояние это набор уже использованных. dp[mask] хранит лучший ответ для этого набора, а число единичных битов в маске говорит, чья очередь.
Задача урока с максимумом вместо минимума. Студенты это работники, наставники это задачи, а очки это число совпавших ответов.
Каждое число из nums1 берёт своё число из nums2, а цена это их XOR, так что это задача урока с n до 14.
dp[mask] считает расстановки чисел из маски. Следующая позиция равна числу битов маски плюс 1, и она должна делить следующее число или делиться на него.
dp[mask] хранит, насколько заполнена текущая корзина после чисел из маски, а число подходит, только если не переполняет её.
Состояние это вершина плюс маска посещённых вершин, и BFS по таким парам находит самый короткий обход всех.