Thursday, August 11, 2022
HomeSoftware DevelopmentDivide and Conquer Optimization in Dynamic Programming

# Divide and Conquer Optimization in Dynamic Programming

Dynamic programming (DP) is arguably crucial device in a aggressive programmer’s repertoire. There are a number of optimizations in DP that scale back the time complexity of ordinary DP procedures by a linear issue or extra, equivalent to Knuth’s optimization, Divide and Conquer optimization, the Convex Hull Trick, and so on. They’re, of paramount significance for superior aggressive programming, equivalent to on the degree of olympiads. On this article, we’ll uncover the divide and conquer optimization, NOT to be confused with the divide and conquer algorithm to resolve issues.

## Divide and Conquer Optimization Standards:

The divide and conquer optimization can be utilized for issues with a dp transition of the next kind –

dp[i][j] = min1≤ok<j (dp[i-1][k-1] + price[k][j])

Additional, the associated fee operate should fulfill the quadrangle inequality (QI), i.e.,

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

## Divide and Conquer Optimization Approach:

The sub-optimal strategy to resolve any downside with a dynamic programming transition of the shape given above would iterate by means of all potential values of ok < j for every transition. Then, if the issue constraints give 1 ≤ i ≤ m and 1 ≤ j ≤ n, the algorithm will take O(mn2) time.

The important thing to the optimization is the next:

• Like in Knuth’s optimization, outline the operate choose(i, j), the minimal (or most, doesn’t matter) worth of ok for which dp[i][j] takes its minimal worth. Then, we’ve got the next relation:

choose[i][j] ≤ choose[i][j+1], the place

choose[i][j] = argminok<j(dp[i-1][k] + price[k][j])

Now, suppose we compute choose[i][j] for some i and j. Then, we additionally know that choose[i][p] ≤ choose[i][j] for all p < j. The sub-optimal answer would contain looping for every j, by means of all potential values of ok for any fastened i. The optimization itself is as follows:

• Loop by means of the values of i, and first compute dp[i][j] and choose[i][j] for j = n/2, for the present i.  That is potential as on the time of processing, we all know all of the values within the dp desk for dp[i-1][k] for all ok ≤ n, because of the construction of the loop.
• Now, calculate dp[i][n/4] and dp[i][3n/4], realizing that choose[i][n/4] ≤ choose[i][n/2] and choose[i][n/2] ≤ choose[i][3n/4]
• We recursively name this clear up operate, maintaining observe of the decrease and higher bounds for choose[i][j] for some i and the present j. As an example, when calculating dp[i][5n/8], we all know that choose[i][n/2] ≤ choose[i][5n/8] ≤ choose[i][3n/4]

The algorithm is quicker by a linear issue as we don’t should loop by means of all values of ok, and a logarithmic issue is added because of the recursive nature of this algorithm. The time complexity is thus O(m * n * (log n)).

The generic code for this strategy is given beneath It makes use of a recursive strategy, which is the best to implement given the construction of the answer.

## C++

 ` `  `#embrace ` `utilizing` `namespace` `std;` ` `  `const` `int` `MAX_M = 10005;` `const` `int` `MAX_N = 1005;` `int` `N, M, dp[MAX_M][MAX_N], price[MAX_M][MAX_M];` ` `  `void` `divide(``int` `l, ``int` `r, ``int` `optl, ` `            ``int` `optr, ``int` `i) ` `{` `    ``if` `(l > r)  ` `      ``return``;` ` `  `    ` `    ``int` `mid = (l + r) >> 1;` `   `  `    ` `    ``pair<``int``, ``int``> greatest = {INT_MAX, -1};` ` `  `    ` `    ``for` `(``int` `ok = optl; ok < min(mid, optr); ok++) ` `        ``greatest = min(greatest, {(ok ? dp[i-1][k] : 0) ` `                          ``+ price[k][mid], ok}); ` ` `  `    ` `    ``dp[i][mid] = greatest.first;` `    ``int` `choose = greatest.second;` ` `  `    ` `    ` `    ``divide(l, mid - 1, optl, choose, i);` `    ``divide(mid + 1, r, choose, optr, i);` `}` ` `  ` `  `void` `clear up() ` `{` `    ` `    ` `    ` `    ``for` `(``int` `i = 0; i < N; i++)` `        ``dp[0][i] = price[0][i];` ` `  `    ` `    ` `    ``for` `(``int` `i = 1; i < M; i++) ` `        ``divide(0, N - 1, 0, N - 1, i);` ` `  `    ``cout << dp[M-1][N-1] << endl;` `}` ` `  `int` `major() ` `{` `    ` `    ``clear up();` `    ``return` `0;` `}`

## Proof of Correctness of Divide and Conquer Optimization:

To show the correctness of this algorithm, we solely have to show the inequality –

choose[i][j] ≤ choose[i][j+1]

Comply with the beneath part for proof of correctness:

Assumptions: If price(i, j) satisfies the Quadrangle Inequality, then dp[i][j] additionally satisfies the inequality.
Now, contemplate the next setup –

• Now we have some indices 1 ≤ p ≤ q ≤ j and a separate fastened i
• Let dpok[i][j] = price[k][i] + dp[k-1][j-1].

If we are able to present that –

dpp[i][j] ≥ dpq[i][j] ⇒ dpp[i][j+1] ≥ dpq[i][j+1]

then setting q = choose[i][j], it will likely be clear that choose[i][j+1] shall be at the least as a lot as choose[i][j], because of the implication of the above inequality for all indices p lower than choose[i][j]. It will show that choose[i][j-1] ≤ choose[i][j].

Prrof:

From the Quadrangle inequality on the dp array we get –

price(p, j) + price(q, j+1) ≤ price(p, j+1) + price(q, j)
⇒ (dp[i-1, p] + price(p, j)) + (dp[i-1, q] + price(q, j+1)) ≤ (dp[i-1, p] + price(p, j+1)) + (dp[j-1, q] + price(q, j))
⇒ dpp[i][j] + dpq[i][j+1] ≤ dpp[i][j+1] + dpq[i][j]
⇒ dpp[i][j] – dpq[i][j] ≤ dpp[i][j+1] – dpq[i][j+1]

dpp[i][j] ≥ dpq[i][j]
⇒ 0 ≤ dpp[i][j] – dpq[i][j] ≤ dpp[i][j+1] – dpq[i][j+1]
⇒ dpp[i][j+1] ≥ dpq[i][j+1]

This completes the proof dpp[i][j] ≥ dpq[i][j] ⇒ dpp[i][j+1] ≥ dpq[i][j+1]

## Examples to Present Working of Divide and Conquer Optimization:

Given an array arr[] of N components, the duty is to divide it into Ok subarrays, such that the sum of the squares of the subarray sums is minimized.

Examples:

Enter: arr []= {1, 3, 2, 6, 7, 4}, Ok = 3.
Output: 193
Rationalization: The optimum division into subarrays is [1, 3, 2], [6] and [7, 4],
Giving a complete sum of (1 + 3 + 2)2 + (6)2 + (7 + 4)2 = 193.
That is the minimal potential sum for this explicit array and Ok.

Enter: arr[] = {1, 4, 2, 3}, Ok = 2
Output: 50
Rationalization: Divide it into subarrays {1, 4} and {2, 3}.
The sum is (1+4)2 + (2 + 3)2 = 52 + 52 = 50.
That is the minimal potential sum.

Suboptimal answer: The issue will be solved primarily based on the next concept:

• If first j-1 components are divided into i-1 teams then the minimal price of dividing first j components into i teams is identical because the minimal worth amongst all potential mixture of dividing first k-1 (i ≤ ok ≤ j) components into i-1 teams and the price of the ith group shaped by taking components from okth to jth indices.
• Let dp[i][j] be the minimal sum obtainable by dividing the primary j components into i subarrays.
So the dp-transition shall be –

dp[i][j] = mini≤ok≤j (dp[i-1][k-1] + price[k][i])

the place price[k][i] denotes the sq. of the sum of all components within the subarray arr[k, k+1 . . . i]

Comply with the steps talked about beneath for fixing the issue:

• The associated fee operate will be calculated in fixed time by preprocessing utilizing a prefix sum array:
• Calculate prefix sum (say saved in pref[] array).
• So price(i, j) will be calculated as (pref[j] – pref[i-1]).
• Traverse from i = 1 to M:
• Traverse from j = i to N:
• Traverse utilizing ok and kind the dp[][] desk utilizing the above dp remark.
• The worth at dp[M-1][N-1] is the required reply.

Beneath is the implementation of the above strategy.

## C++

 ` `  `#embrace ` `utilizing` `namespace` `std;` ` `  `int` `clear up(``int` `arr[], ``int` `N, ``int` `M)` `{` `    ``int` `pref[N + 1], dp[M + 1][N + 1];` ` `  `    ` `    ``pref[0] = 0;` `    ``for` `(``int` `i = 0; i < N; i++)` `        ``pref[i + 1] = pref[i] + arr[i];` ` `  `    ` `    ``for` `(``int` `i = 0; i < N; i++)` `        ``dp[0][i] = pref[i + 1] * pref[i + 1];` ` `  `    ` `    ``for` `(``int` `i = 1; i < M; i++) {` `        ``for` `(``int` `j = i; j < N; j++) {` `            ``dp[i][j] = INT_MAX;` `            ``for` `(``int` `ok = 1; ok <= j; ok++) {` `                ``int` `price ` `                    ``= (pref[j + 1] - pref[k])` `                    ``* (pref[j + 1] - pref[k]);` ` `  `                ` `                ``dp[i][j] = min(dp[i][j],` `                               ``dp[i - 1][k - 1] ` `                               ``+ price);` `            ``}` `        ``}` `    ``}` ` `  `    ``return` `dp[M - 1][N - 1];` `}` ` `  `int` `major()` `{` `    ``int` `N, M = 3;` `    ``int` `arr[] = { 1, 3, 2, 6, 7, 4 };` `    ``N = ``sizeof``(arr) / ``sizeof``(arr[0]);` ` `  `    ` `    ``cout << clear up(arr, N, M);` `    ``return` `0;` `}`

Time Complexity: O(M * N2)
Auxiliary Area: O(M * N)

Optimum Resolution (Utilizing Divide and Conquer Optimization):

This downside follows the quadrangle We are able to, nevertheless, discover that the associated fee operate satisfies the quadrangle inequality

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

The next is the proof:

Let sum(p, q) denote the sum of values in vary [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)

Utilizing this notation, the quadrangle inequality turns into

(x + y)2 + (x + z)2 ≤ (x + y + z)2 + x2
which is equal to 0 ≤ 2yz.

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

• There’s yet one more layer of optimization within the house complexity that we are able to do. To calculate the dp[][] states for a sure worth of j, we solely want the values of the dp state for j-1
• Thus, sustaining 2 arrays of size N and swapping them after the dp[][] array has been crammed for the present worth of j removes an element of Ok from the house complexity.

Observe: This optimization can be utilized for all implementations of the divide and conquer DP speedup.

Comply with the steps talked about beneath to implement the thought:

• The associated fee operate will be calculated utilizing prefix sum as within the earlier strategy.
• Now for every fastened worth of i (variety of subarrays during which the array is split):
• Traverse the entire array to seek out the minimal potential sum for i divisions.
• The worth saved in dp[M%2][N-1] is the required reply.

Beneath is the implementation of the above strategy.

## C++

 ` `  `#embrace ` `utilizing` `namespace` `std;` ` `  `void` `divide(``int` `l, ``int` `r, ``int` `optl, ``int` `optr, ` `            ``int` `i, vector> &dp, ` `            ``int` `pref[]) ` `{` `    ``if` `(l > r)  ` `        ``return``;` ` `  `    ` `    ``int` `mid = (l + r) >> 1;` `   `  `    ` `    ``pair<``int``, ``int``> greatest = {INT_MAX, -1};` ` `  `    ` `    ``for` `(``int` `ok = optl; ok <= min(mid, optr); ` `         ``ok++) {` `        ``int` `price = (pref[mid+1] - pref[k]) ` `            ``* (pref[mid+1] - pref[k]);` `        ``greatest = min(greatest, ` `                   ``{(ok ? dp[(i+1)%2][k-1] : 0) ` `                    ``+ price, ok}); ` `    ``}         ` ` `  `    ` `    ``dp[i][mid] = greatest.first;` `    ``int` `choose = greatest.second;` ` `  `    ` `    ` `    ``divide(l, mid - 1, optl, choose, i, dp, pref);` `    ``divide(mid + 1, r, choose, optr, i, dp, pref);` `}` ` `  `int` `clear up(``int` `arr[], ``int` `N, ``int` `M) ` `{` `    ``vector> dp(2, vector<``int``>(N));` `     `  `    ` `    ``int` `pref[N + 1];` `    ``pref[0] = 0;` `    ``for` `(``int` `i = 0; i < N; i++) ` `        ``pref[i + 1] = pref[i] + arr[i];` `     `  `      ` `    ``for` `(``int` `i = 0; i < N; i++)` `        ``dp[1][i] = pref[i + 1] * pref[i + 1];` ` `  `    ` `    ` `    ``for` `(``int` `i = 2; i <= M; i++) ` `        ``divide(0, N - 1, 0, N - 1, ` `               ``(ipercent2), dp, pref);` ` `  `    ``return` `dp[M%2][N-1];` `}` ` `  `int` `major() ` `{` `    ``int` `N, M = 3;` `    ``int` `arr[] = { 1, 3, 2, 6, 7, 4 };` `    ``N = ``sizeof``(arr) / ``sizeof``(arr[0]);` `   `  `    ` `    ``cout << clear up(arr, N, M);` `    ``return` `0;` `}`

Time Complexity: O(M * N * logN)
Auxiliary Area: O(N)

RELATED ARTICLES