Где применяется
1. Задача
Программа уплотнения логов держит отсортированные сегменты в ряд. Она сливает их по два, пока не останется один. Слияние двух сегментов стоит сумму их размеров: каждую запись из обоих приходится прочитать и записать заново. Есть ограничение. Сливать можно только соседние сегменты, и их порядок менять нельзя.
От порядка слияний зависит общая стоимость. Если первой слить не ту пару, большой сегмент потом пройдёт через лишние слияния. По размерам сегментов нужно найти самую дешёвую общую стоимость, чтобы свести их в один.
Первое, что приходит в голову: каждый раз сливать соседнюю пару с самой маленькой суммой. Здесь это правило иногда проигрывает. Возьми размеры [3, 3, 2, 4]. Самая лёгкая пара это 3 и 2 (сумма 5). После неё остаётся [3, 5, 4], дальше 3 + 5 = 8 и в конце 12. Итого 5 + 8 + 12 = 25. Если начать с 3 + 3 = 6, потом слить 2 + 4 = 6, а в конце 6 + 6 = 12, выйдет 24. Поэтому жадное правило здесь не годится.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитminMergeCost([4, 1, 3, 2])| j=0 | j=1 | j=2 | j=3 | |
|---|---|---|---|---|
| i=0 | 0 | |||
| i=1 | 0 | |||
| i=2 | 0 | |||
| i=3 | 0 |
Сливаем соседние кучи, пока не останется одна. Каждое слияние стоит суммы размеров двух куч. Ищем самый дешёвый порядок.
Как узнать
Эти слова в условии значат этот паттерн
- объединить соседние части с некоторой стоимостью
- лучший способ разбить отрезок на две части
- порядок перемножения цепочки матриц
- стоимость слияния зависит от всего отрезка
- оптимальная расстановка скобок или порядок построения
Похоже, но не то
- Динамическое программирование (1-D) (Dynamic programming (1-D))
Один индекс описывает префикс. Отрезку нужны оба конца.
- DP над подпоследовательностями (LIS / LCS / расстояние редактирования) (DP on subsequences (LIS / LCS / edit distance))
Там два индекса указывают в две разные последовательности. Здесь оба лежат в одной.
- DP на деревьях (DP on trees)
Дерево делится по своим потомкам, и они заданы. Отрезок делится в точке, которую вы выбираете.
- Жадный алгоритм (обменный аргумент) (Greedy (exchange argument))
Жадность выбрала бы порядок и на нём остановилась. Здесь надо перебрать все точки разреза.
n примерно до 500 даёт O(n в кубе). Отрезков n в квадрате, и у каждого n точек разреза.
На LeetCode
Задачи, где ряд сливают, режут или лопают в каком-то порядке, и от порядка зависит стоимость. Для отрезка от i до j перебирай каждую точку разреза k, складывай две половины и цену этого шага и заполняй таблицу по длине отрезка.
Добавь 0 и n к отсортированным разрезам. Каждый разрез стоит длину куска, в который он попал, а таблица идёт по отрезкам между разрезами.
Для стороны от i до j перебирай каждую вершину k между ними как третий угол треугольника и прибавляй два меньших многоугольника.
Выбирай k как шарик внутри от i до j, который лопнет последним, тогда его соседи в этот момент это i минус 1 и j плюс 1.
При k, равном 2, это задача урока. При большем k добавь проверку, что n минус 1 делится на k минус 1, а сливай отрезок в одну кучку, только когда его длина это позволяет.