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

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

Разделяй и властвуй Критерии оптимизации:

Оптимизацию «разделяй и властвуй» можно использовать для задач с переходом dp следующего вида:

dp[i][j] = min_1≤k<j (dp[i-1][k-1] + cost[k][j])

Кроме того, функция стоимости должна удовлетворять четырехугольному неравенству (QI), т. е.

cost(a, c) + cost(b, d) ≤ cost(a, d) + cost(b, c) for all a ≤ b ≤ c ≤ d.

Техника оптимизации «разделяй и властвуй»:

Неоптимальный подход к решению любой проблемы с переходом динамического программирования в приведенной выше форме будет перебирать все возможные значения k < j . для каждого перехода. Тогда, если ограничения задачи дают 1 ≤ i ≤ m и 1 ≤ j ≤ n , алгоритм займет O(mn ² ) времени.

Ключом к оптимизации является следующее:

• Как и в оптимизации Кнута , определите функцию opt(i, j) , минимальное (или максимальное, не имеет значения) значение k , для которого dp[i][j] принимает минимальное значение. Тогда имеем следующее соотношение:

opt[i][j] ≤ opt[i][j+1], where

opt[i][j] = argmin_k<j(dp[i-1][k] + cost[k][j])

Теперь предположим, что мы вычисляем opt[i][j] для некоторых i и j . Тогда мы также знаем, что opt[i][p] ≤ opt[i][j] для всех p < j . Субоптимальное решение будет включать цикл для каждого j по всем возможным значениям k для любого фиксированного i . Сама оптимизация выглядит следующим образом:

• Переберите значения i и сначала вычислите dp[i][j] и opt[i][j] для j = n/2 для текущего i . Это возможно, так как во время обработки мы знаем все значения в таблице dp для dp[i-1][k] для всех k ≤ n из - за структуры цикла.
• Теперь вычислите dp[i][n/4] и dp[i][3n/4] , зная, что opt[i][n/4] ≤ opt[i][n/2] и opt[i][n/2] ≤ opt[i][3n/4] .
• Мы рекурсивно вызываем эту функцию решения, отслеживая нижнюю и верхнюю границы для opt[i][j] для некоторого i и текущий j . Например, при вычислении dp[i][5n/8] мы знаем, что opt[i][n/2] ≤ опт[i][5n/8] ≤ опт[i][3n/4] .

Алгоритм быстрее в линейном множителе, так как нам не нужно перебирать все значения k , а логарифмический множитель добавляется из-за рекурсивного характера этого алгоритма. Таким образом, временная сложность составляет O(m * n * (log n)) .

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

Доказательство правильности оптимизации «разделяй и властвуй»:

Чтобы доказать правильность этого алгоритма, нам нужно только доказать неравенство –

opt[i][j] ≤ opt[i][j+1] 

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

Assumptions: If cost(i, j) satisfies the Quadrangle Inequality, then dp[i][j] also satisfies the inequality.  
Now, consider the following setup – 

• We have some indices 1 ≤ p ≤ q ≤ j and a separate fixed i. 
• Let dp_k[i][j] = cost[k][i] + dp[k-1][j-1]. 

If we can show that – 

dp_p[i][j] ≥ dp_q[i][j] ⇒ dp_p[i][j+1] ≥ dp_q[i][j+1] 

then setting q = opt[i][j], it will be clear that opt[i][j+1] will be at least as much as opt[i][j], due to the implication of the above inequality for all indices p less than opt[i][j]. This will prove that opt[i][j-1] ≤ opt[i][j].

Prrof:

From the Quadrangle inequality on the dp array we get –

cost(p, j) + cost(q, j+1) ≤ cost(p, j+1) + cost(q, j)
⇒ (dp[i-1, p] + cost(p, j)) + (dp[i-1, q] + cost(q, j+1)) ≤ (dp[i-1, p] + cost(p, j+1)) + (dp[j-1, q] + cost(q, j))
⇒ dp_p[i][j] + dp_q[i][j+1] ≤ dp_p[i][j+1] + dp_q[i][j]
⇒ dp_p[i][j] – dp_q[i][j] ≤ dp_p[i][j+1] – dp_q[i][j+1]

dp_p[i][j] ≥ dp_q[i][j] 
⇒ 0 ≤ dp_p[i][j] – dp_q[i][j] ≤ dp_p[i][j+1] – dp_q[i][j+1] 
⇒ dp_p[i][j+1] ≥ dp_q[i][j+1] 

This completes the proof dp_p[i][j] ≥ dp_q[i][j] ⇒ dp_p[i][j+1] ≥ dp_q[i][j+1]

Примеры, демонстрирующие работу оптимизации «разделяй и властвуй»:

Дан массив arr[] из N элементов, задача состоит в том, чтобы разбить его на K подмассивов так, чтобы сумма квадратов сумм подмассивов была минимальной.

Примеры:

Input: arr []= {1, 3, 2, 6, 7, 4}, K = 3. 
Output: 193
Explanation: The optimal division into subarrays is [1, 3, 2], [6] and [7, 4], 
Giving a total sum of (1 + 3 + 2)² + (6)² + (7 + 4)² = 193.  
This is the minimum possible sum for this particular array and K.

Input: arr[] = {1, 4, 2, 3}, K = 2
Output: 50
Explanation: Divide it into subarrays {1, 4} and {2, 3}.
The sum is (1+4)² + (2 + 3)² = 5² + 5² = 50.
This is the minimum possible sum.

Субоптимальное решение: проблема может быть решена на основе следующей идеи:

• If first j-1 elements are divided into i-1 groups then the minimum cost of dividing first j elements into i groups is the same as the minimum value among all possible combination of dividing first k-1 (i ≤ k ≤ j) elements into i-1 groups and the cost of the ith group formed by taking elements from k^th to j^th indices.
• Let dp[i][j] be the minimum sum obtainable by dividing the first j elements into i subarrays. 
  So the dp-transition will be – 

dp[i][j] = min_i≤k≤j (dp[i-1][k-1] + cost[k][i])

where cost[k][i] denotes the square of the sum of all elements in the subarray arr[k, k+1 . . . i]

Для решения проблемы выполните шаги, указанные ниже:

• Функцию стоимости можно рассчитать за постоянное время путем предварительной обработки с использованием массива сумм префиксов:
  • Вычислить сумму префикса (скажем, сохраненную в массиве pref[]).
  • Таким образом, стоимость (i, j) может быть рассчитана как (pref[j] – pref[i-1]).
• Переход от i = 1 до M:
  • Переход от j = i к N:
  • Перейдите, используя k , и сформируйте таблицу dp[][] , используя приведенное выше наблюдение dp.
• Значение в dp[M-1][N-1] является требуемым ответом.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(M * N ² )
Вспомогательное пространство: O(M * N)

Оптимальное решение (с использованием оптимизации «разделяй и властвуй»):

Эта задача следует за четырехугольником. Однако мы можем заметить, что функция стоимости удовлетворяет неравенству четырехугольника

cost(a, c) + cost(b, d) ≤ cost(a, d) + cost(b, c). 

Вот доказательство:

Let sum(p, q) denote the sum of values in range [p, q] (sub-array of arr[[]), and let x = sum(b, c), y = sum(a, c) − sum(b, c), and z = sum(b, d) − sum(b, c). 

Using this notation, the quadrangle inequality becomes 

(x + y)² + (x + z)² ≤ (x + y + z)² + x², 
which is equivalent to 0 ≤ 2yz. 

Since y and z are nonnegative values, this completes the proof. We can thus use the divide and conquer optimization. 

• Есть еще один уровень оптимизации пространственной сложности, который мы можем сделать. Чтобы вычислить состояния dp[][] для определенного значения j , нам нужны только значения состояния dp для j-1 .
• Таким образом, поддерживая 2 массива длины N и замена их после заполнения массива dp[][] текущим значением j удаляет фактор K из пространственной сложности.

Примечание. Эту оптимизацию можно использовать для всех реализаций ускорения DP по принципу «разделяй и властвуй».

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

• Функция стоимости может быть рассчитана с использованием суммы префиксов, как и в предыдущем подходе.
• Теперь для каждого фиксированного значения i (количество подмассивов, на которые разбит массив):
  • Пройдите весь массив, чтобы найти минимально возможную сумму для i делений.
• Значение, хранящееся в dp[M%2][N-1] , является требуемым ответом.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O (M * N * logN)
Вспомогательное пространство: O(N)