Examples to Show Working of Divide and Conquer Optimization

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

Examples:

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.

Suboptimal solution: The problem can be solved based on the following idea:

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]

Follow the steps mentioned below for solving the problem:

The cost function can be calculated in constant time by preprocessing using a prefix sum array:
- Calculate prefix sum (say stored in pref[] array).
- So cost(i, j) can be calculated as (pref[j] – pref[i-1]).
Traverse from i = 1 to M:
- Traverse from j = i to N:
- Traverse using k and form the dp[][] table using the above dp observation.
The value at dp[M-1][N-1] is the required answer.

Below is the implementation of the above approach.

C++

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum sum
int solve(int arr[], int N, int M)
{
    int pref[N + 1], dp[M + 1][N + 1];
 
    // Prefix sum array
    pref[0] = 0;
    for (int i = 0; i < N; i++)
        pref[i + 1] = pref[i] + arr[i];
 
    // Initialize the dp array
    for (int i = 0; i < N; i++)
        dp[0][i] = pref[i + 1] * pref[i + 1];
 
    // Fill in the dp array
    for (int i = 1; i < M; i++) {
        for (int j = i; j < N; j++) {
            dp[i][j] = INT_MAX;
            for (int k = 1; k <= j; k++) {
                int cost 
                    = (pref[j + 1] - pref[k])
                    * (pref[j + 1] - pref[k]);
 
                // dp transition
                dp[i][j] = min(dp[i][j],
                               dp[i - 1][k - 1] 
                               + cost);
            }
        }
    }
 
    return dp[M - 1][N - 1];
}
 
// Driver code
int main()
{
    int N, M = 3;
    int arr[] = { 1, 3, 2, 6, 7, 4 };
    N = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    cout << solve(arr, N, M);
    return 0;
}

Java

// Java code to implement the approach
import java.io.*;
 
class GFG {
    // Function to find the minimum sum
    public static int solve(int arr[], int N, int M)
    {
        int pref[] = new int[N + 1];
        int dp[][] = new int[M + 1][N + 1];
 
        // Prefix sum array
        pref[0] = 0;
        for (int i = 0; i < N; i++)
            pref[i + 1] = pref[i] + arr[i];
 
        // Initialize the dp array
        for (int i = 0; i < N; i++)
            dp[0][i] = pref[i + 1] * pref[i + 1];
 
        // Fill in the dp array
        for (int i = 1; i < M; i++) {
            for (int j = i; j < N; j++) {
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = 1; k <= j; k++) {
                    int cost = (pref[j + 1] - pref[k])
                               * (pref[j + 1] - pref[k]);
 
                    // dp transition
                    dp[i][j] = Math.min(
                        dp[i][j], dp[i - 1][k - 1] + cost);
                }
            }
        }
 
        return dp[M - 1][N - 1];
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N, M = 3;
        int arr[] = { 1, 3, 2, 6, 7, 4 };
        N = arr.length;
 
        // Function call
        System.out.print(solve(arr, N, M));
    }
}
 
// This code is contributed by Rohit Pradhan

Python3

import sys
# Function to find the minimum sum
def solve(arr, N, M) :
     
    pref = [0] * (N + 1)
    dp = [[0] * (N + 1) ] * (M+1)
 
    # Prefix sum array
    pref[0] = 0
    for i in range(N) :
        pref[i + 1] = pref[i] + arr[i]
 
    # Initialize the dp array
    for i in range(N) :
        dp[0][i] = pref[i + 1] * pref[i + 1]
 
    # Fill in the dp array
    for i in range(1, M) :
        for j in range(i, N) :
            dp[i][j] = -193
            for k in range(1, j+1) :
                cost = ((pref[j + 1] - pref[k])
                    * (pref[j + 1] - pref[k]))
 
                # dp transition
                dp[i][j] = min(dp[i][j],
                               dp[i - 1][k - 1] 
                               + cost);
             
    return (-dp[M - 1][N - 1])
 
# Driver code
if __name__ == "__main__":
     
    N = 3
    M = 3
    arr = [ 1, 3, 2, 6, 7, 4 ]
    N = len(arr) 
 
    # Function call
    print(solve(arr, N, M))
 
    # This code is contributed by sanjoy_62.

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
    // Function to find the minimum sum
    static int solve(int[] arr, int N, int M)
    {
        int[] pref = new int[N + 1];
        int[,] dp = new int[M + 1, N + 1];
 
        // Prefix sum array
        pref[0] = 0;
        for (int i = 0; i < N; i++)
            pref[i + 1] = pref[i] + arr[i];
 
        // Initialize the dp array
        for (int i = 0; i < N; i++)
            dp[0, i] = pref[i + 1] * pref[i + 1];
 
        // Fill in the dp array
        for (int i = 1; i < M; i++) {
            for (int j = i; j < N; j++) {
                dp[i, j] = Int32.MaxValue;
                for (int k = 1; k <= j; k++) {
                    int cost = (pref[j + 1] - pref[k])
                               * (pref[j + 1] - pref[k]);
 
                    // dp transition
                    dp[i, j] = Math.Min(
                        dp[i, j], dp[i - 1, k - 1] + cost);
                }
            }
        }
 
        return dp[M - 1, N - 1];
    }
 
// Driver Code
public static void Main(String[] args)
{
        int N, M = 3;
        int[] arr = { 1, 3, 2, 6, 7, 4 };
        N = arr.Length;
 
        // Function call
        Console.WriteLine(solve(arr, N, M));
}
}
 
// This code is contributed by code_hunt.

Javascript

// Javascript code to implement the approach
 
// Function to find the minimum sum
const solve = (arr, N, M) => {
    let pref = new Array(N + 1).fill(0);
    let dp = new Array(M + 1).fill(0).map(() => new Array(N + 1).fill(0));
     
    // Prefix sum array
    pref[0] = 0;
    for (let i = 0; i < N; i++) {
        pref[i + 1] = pref[i] + arr[i];
    }
    // Initialize the dp array
    for (let i = 0; i < N; i++) {
        dp[0][i] = pref[i + 1] * pref[i + 1];
    }
     
    // Fill in the dp array
    for (let i = 1; i < M; i++) {
        for (let j = i; j < N; j++) {
            dp[i][j] = -193;
            for (let k = 1; k < j + 1; k++) {
                let cost = (pref[j + 1] - pref[k]) * (pref[j + 1] - pref[k]);
                 
                // dp transition
                dp[i][j] = Math.min(dp[i][j], dp[i - 1][k - 1] + cost);
            }
        }
    }
 
    return -dp[M - 1][N - 1];
}
 
// Driver Code
let N = 3;
let M = 3;
let arr = [1, 3, 2, 6, 7, 4];
N = arr.length;
 // Function call
console.log(solve(arr, N, M));
 
// This code is contributed by ishankhandelwals.

Output

Time Complexity: O(M * N²)
Auxiliary Space: O(M * N)

Optimal Solution (Using Divide and Conquer Optimization):

This problem follows the quadrangle We can, however, notice that the cost function satisfies the quadrangle inequality

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

The following is the proof:

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.

There is one more layer of optimization in the space complexity that we can do. To calculate the dp[][] states for a certain value of j, we only need the values of the dp state for j-1.
Thus, maintaining 2 arrays of length N and swapping them after the dp[][] array has been filled for the current value of j removes a factor of K from the space complexity.

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

Follow the steps mentioned below to implement the idea:

The cost function can be calculated using prefix sum as in the previous approach.
Now for each fixed value of i (number of subarrays in which the array is divided):
- Traverse the whole array to find the minimum possible sum for i divisions.
The value stored in dp[M%2][N-1] is the required answer.

Below is the implementation of the above approach.

C++

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to implement the 
// divide and conquer optimization
void divide(int l, int r, int optl, int optr, 
            int i, vector<vector<int>> &dp, 
            int pref[]) 
{
    if (l > r)  
        return;
 
    // Find middle value
    int mid = (l + r) >> 1;
   
    // Store the minimum cost and opt(i, j)
    pair<int, int> best = {INT_MAX, -1};
 
    // Find value of the best cost and opt(i, j)
    for (int k = optl; k <= min(mid, optr); 
         k++) {
        int cost = (pref[mid+1] - pref[k]) 
            * (pref[mid+1] - pref[k]);
        best = min(best, 
                   {(k ? dp[(i+1)%2][k-1] : 0) 
                    + cost, k}); 
    }         
 
    // Store the minimum cost in the dp array
    dp[i][mid] = best.first;
    int opt = best.second;
 
    // Recursively call the divide function 
    // to fill the other dp states
    divide(l, mid - 1, optl, opt, i, dp, pref);
    divide(mid + 1, r, opt, optr, i, dp, pref);
}
 
// Function to solve the problem
int solve(int arr[], int N, int M) 
{
    vector<vector<int>> dp(2, vector<int>(N));
     
    // Prefix sum array
    int pref[N + 1];
    pref[0] = 0;
    for (int i = 0; i < N; i++) 
        pref[i + 1] = pref[i] + arr[i];
     
      // Initialize the dp array
    for (int i = 0; i < N; i++)
        dp[1][i] = pref[i + 1] * pref[i + 1];
 
    // Fill in the dp array 
    // with the divide function
    for (int i = 2; i <= M; i++) 
        divide(0, N - 1, 0, N - 1, 
               (i%2), dp, pref);
 
    return dp[M%2][N-1];
}
 
// Driver code
int main() 
{
    int N, M = 3;
    int arr[] = { 1, 3, 2, 6, 7, 4 };
    N = sizeof(arr) / sizeof(arr[0]);
   
    // Function call
    cout << solve(arr, N, M);
    return 0;
}

Java

// Java code to implement the approach
 
import java.io.*;
import java.util.*;
 
// Pair class to store a pair of values
class Pair {
    int first;
    int second;
    public Pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}
 
class GFG {
 
    // Function to implement the
    // divide and conquer optimization
    public static void divide(int l, int r, int optl,
                              int optr, int i, int[][] dp,
                              int[] pref)
    {
        if (l > r)
            return;
 
        // Find middle value
        int mid = (l + r) >> 1;
 
        // Store the minimum cost and opt(i, j)
        Pair best = new Pair(Integer.MAX_VALUE, -1);
 
        // Find value of the best cost and opt(i, j)
        for (int k = optl; k <= Math.min(mid, optr); k++) {
            int cost = (pref[mid + 1] - pref[k])
                       * (pref[mid + 1] - pref[k]);
            best = min(
                best,
                new Pair(
                    (k != 0 ? dp[(i + 1) % 2][k - 1] : 0)
                        + cost,
                    k));
        }
 
        // Store the minimum cost in the dp array
        dp[i][mid] = best.first;
        int opt = best.second;
 
        // Recursively call the divide function
        // to fill the other dp states
        divide(l, mid - 1, optl, opt, i, dp, pref);
        divide(mid + 1, r, opt, optr, i, dp, pref);
    }
 
    // Function to solve the problem
    public static int solve(int[] arr, int N, int M)
    {
        int[][] dp = new int[2][N];
 
        // Prefix sum array
        int[] pref = new int[N + 1];
        pref[0] = 0;
        for (int i = 0; i < N; i++)
            pref[i + 1] = pref[i] + arr[i];
 
        // Initialize the dp array
        for (int i = 0; i < N; i++)
            dp[1][i] = pref[i + 1] * pref[i + 1];
 
        // Fill in the dp array
        // with the divide function
        for (int i = 2; i <= M; i++)
            divide(0, N - 1, 0, N - 1, (i % 2), dp, pref);
 
        return dp[M % 2][N - 1];
    }
 
    // Function to return the minimum of two pairs
    public static Pair min(Pair a, Pair b)
    {
        if (a.first < b.first) {
            return a;
        }
        return b;
    }
 
    public static void main(String[] args)
    {
        int N, M = 3;
        int[] arr = { 1, 3, 2, 6, 7, 4 };
        N = arr.length;
 
        // Function call
        System.out.println(solve(arr, N, M));
    }
}
 
// This code is contributed by lokesh.

Python3

# Python code to implement the approach
from typing import List, Tuple
 
# Function to implement the 
# divide and conquer optimization
def divide(l: int, r: int, optl: int, optr: int, 
            i: int, dp: List[List[int]], 
            pref: List[int]) -> None:
    if l > r:  
        return
   
    # Find middle value
    mid = (l + r) >> 1
   
    # Store the minimum cost and opt(i, j)
    best = (float("inf"), -1)
 
    # Find value of the best cost and opt(i, j)
    for k in range(optl, min(mid, optr) + 1):
        cost = (pref[mid+1] - pref[k]) * (pref[mid+1] - pref[k])
        if (k and dp[(i+1)%2][k-1]) + cost < best[0]:
            best = ((k and dp[(i+1)%2][k-1]) + cost, k)
   
    # Store the minimum cost in the dp array
    dp[i][mid] = best[0]
    opt = best[1]
 
    # Recursively call the divide function 
    # to fill the other dp states
    divide(l, mid - 1, optl, opt, i, dp, pref)
    divide(mid + 1, r, opt, optr, i, dp, pref)
 
# Function to solve the problem
def solve(arr: List[int], N: int, M: int) -> int:
    dp = [[0] * N for i in range(2)]
     
    # Prefix sum array
    pref = [0] * (N + 1)
    pref[0] = 0
    for i in range(N): 
        pref[i + 1] = pref[i] + arr[i]
     
    # Initialize the dp array
    for i in range(N):
        dp[1][i] = pref[i + 1] * pref[i + 1]
 
    # Fill in the dp array 
    # with the divide function
    for i in range(2, M+1): 
        divide(0, N - 1, 0, N - 1, (i%2), dp, pref)
 
    return dp[M%2][N-1]
 
# Driver code
if __name__ == '__main__':
    N = 6
    M = 3
    arr = [1, 3, 2, 6, 7, 4]
   
    # Function call
    print(solve(arr, N, M))
     
# This code is contributed by ik_9

C#

// C# code for the above approach
using System;
 
// Pair class to store a pair of values
public class Pair {
  public int first;
  public int second;
  public Pair(int first, int second)
  {
    this.first = first;
    this.second = second;
  }
}
 
public class GFG {
 
  // Function to implement the
  // divide and conquer optimization
  public static void divide(int l, int r, int optl,
                            int optr, int i, int[][] dp,
                            int[] pref)
  {
    if (l > r)
      return;
 
    // Find middle value
    int mid = (l + r) >> 1;
 
    // Store the minimum cost and opt(i, j)
    Pair best = new Pair(int.MaxValue, -1);
 
    // Find value of the best cost and opt(i, j)
    for (int k = optl; k <= Math.Min(mid, optr); k++) {
      int cost = (pref[mid + 1] - pref[k])
        * (pref[mid + 1] - pref[k]);
      best = min(
        best,
        new Pair(
          (k != 0 ? dp[(i + 1) % 2][k - 1] : 0)
          + cost,
          k));
    }
 
    // Store the minimum cost in the dp array
    dp[i][mid] = best.first;
    int opt = best.second;
 
    // Recursively call the divide function
    // to fill the other dp states
    divide(l, mid - 1, optl, opt, i, dp, pref);
    divide(mid + 1, r, opt, optr, i, dp, pref);
  }
 
  // Function to solve the problem
  public static int solve(int[] arr, int N, int M)
  {
    int[][] dp = new int[2][];
    for (int i = 0; i < 2; i++)
      dp[i] = new int[N];
 
    // Prefix sum array
    int[] pref = new int[N + 1];
    pref[0] = 0;
    for (int i = 0; i < N; i++)
      pref[i + 1] = pref[i] + arr[i];
 
    // Initialize the dp array
    for (int i = 0; i < N; i++)
      dp[1][i] = pref[i + 1] * pref[i + 1];
 
    // Fill in the dp array
    // with the divide function
    for (int i = 2; i <= M; i++)
      divide(0, N - 1, 0, N - 1, (i % 2), dp, pref);
 
    return dp[M % 2][N - 1];
  }
 
  // Function to return the minimum of two pairs
  public static Pair min(Pair a, Pair b)
  {
    if (a.first < b.first) {
      return a;
    }
    return b;
  }
 
  static public void Main()
  {
 
    // Code
    int N, M = 3;
    int[] arr = { 1, 3, 2, 6, 7, 4 };
    N = arr.Length;
 
    // Function call
    Console.WriteLine(solve(arr, N, M));
  }
}
 
// This code is contributed by lokeshmvs21.

Javascript

// JavaScript code to implement the approach
 
// Function to implement the
// divide and conquer optimization
function divide(l, r, optl, optr, i, dp, pref) {
if (l > r) return;
 
// Find middle value
let mid = (l + r) >> 1;
 
// Store the minimum cost and opt(i, j)
let best = [Infinity, -1];
 
// Find value of the best cost and opt(i, j)
for (let k = optl; k <= Math.min(mid, optr); k++) {
let cost = (pref[mid + 1] - pref[k]) * (pref[mid + 1] - pref[k]);
if ((k && dp[(i + 1) % 2][k - 1]) + cost < best[0]) {
best = [(k && dp[(i + 1) % 2][k - 1]) + cost, k];
}
}
 
// Store the minimum cost in the dp array
dp[i][mid] = best[0];
let opt = best[1];
 
// Recursively call the divide function
// to fill the other dp states
divide(l, mid - 1, optl, opt, i, dp, pref);
divide(mid + 1, r, opt, optr, i, dp, pref);
}
 
// Function to solve the problem
function solve(arr, N, M) {
let dp = Array(2);
for (let i = 0; i < 2; i++) dp[i] = Array(N).fill(0);
 
// Prefix sum array
let pref = Array(N + 1).fill(0);
pref[0] = 0;
for (let i = 0; i < N; i++) {
pref[i + 1] = pref[i] + arr[i];
}
 
// Initialize the dp array
for (let i = 0; i < N; i++) {
dp[1][i] = pref[i + 1] * pref[i + 1];
}
 
// Fill in the dp array
// with the divide function
for (let i = 2; i <= M; i++) {
divide(0, N - 1, 0, N - 1, (i % 2), dp, pref);
}
 
return dp[M % 2][N - 1];
}
 
// Driver code
let N = 6;
let M = 3;
let arr = [1, 3, 2, 6, 7, 4];
 
// Function call
document.write(solve(arr, N, M));

Output

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

Examples to Show Working of Divide and Conquer Optimization

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Divide and Conquer Optimization in Dynamic Programming

Categories

Contact US

Examples to Show Working of Divide and Conquer Optimization

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Divide and Conquer Optimization in Dynamic Programming

Similar Reads

Categories

Contact US