Given a list of N integers, the task is to merge all the elements of the list into one with the minimum possible cost. The rule for merging is as follows:
Choose any two adjacent elements of the list with values say X and Y and merge them into a single element with value (X + Y) paying a total cost of (X + Y).
Examples:
Input: arr[] = {1, 3, 7}
Output: 15
All possible ways of merging:
a) {1, 3, 7} (cost = 0) -> {4, 7} (cost = 0+4 = 4) -> 11 (cost = 4+11 = 15)
b) {1, 3, 7} (cost = 0) -> {1, 10} (cost = 0+10= 10) -> 11 (cost = 10+11 = 21)
Thus, ans = 15Input: arr[] = {1, 2, 3, 4}
Output: 19
Approach: This problem can be solved using dynamic programming. Let’s define the states of the DP first. DP[l][r] will be the minimum cost of merging the subarray arr[l…r] into one.
Now, let’s look at the recurrence relation:
DP[l][r] = min(S(l, l) + S(l + 1, r) + DP[l][l] + DP[l + 1][r], S(l, l + 1) + S(l + 2, r) + DP[l][l + 1] + DP[l + 2][r], …, S(l, r – 1) + S(r, r) + DP[l][r – 1] + DP[r][r]) = S(l, r) + min(DP[l][l] + DP[l + 1][r], DP[l][l + 1] + DP[l + 2][r], …, DP[l][r – 1] + DP[r][r])
where S(x, y) is the sum of all the elements of the subarray arr[x…y]
Below is the implementation of the above approach:
CPP
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define N 401// To store the states of DPint dp[N][N];bool v[N][N];// Function to return the minimum merge costint minMergeCost(int i, int j, int* arr){ // Base case if (i == j) return 0; // If the state has been solved before if (v[i][j]) return dp[i][j]; // Marking the state as solved v[i][j] = 1; int& x = dp[i][j]; // Reference to dp[i][j] x = INT_MAX; // To store the sum of all the // elements in the subarray arr[i...j] int tot = 0; for (int k = i; k <= j; k++) tot += arr[k]; // Loop to iterate the recurrence for (int k = i + 1; k <= j; k++) { x = min(x, tot + minMergeCost(i, k - 1, arr) + minMergeCost(k, j, arr)); } // Returning the solved value return x;}// Driver codeint main(){ int arr[] = { 1, 3, 7 }; int n = sizeof(arr) / sizeof(int); cout << minMergeCost(0, n - 1, arr); return 0;} |
Java
// Java implementation of the approachclass GFG{static final int N = 401;// To store the states of DPstatic int [][]dp = new int[N][N];static boolean [][]v = new boolean[N][N];// Function to return the minimum merge coststatic int minMergeCost(int i, int j, int[] arr){ // Base case if (i == j) return 0; // If the state has been solved before if (v[i][j]) return dp[i][j]; // Marking the state as solved v[i][j] = true; int x = dp[i][j]; // Reference to dp[i][j] x = Integer.MAX_VALUE; // To store the sum of all the // elements in the subarray arr[i...j] int tot = 0; for (int k = i; k <= j; k++) tot += arr[k]; // Loop to iterate the recurrence for (int k = i + 1; k <= j; k++) { x = Math.min(x, tot + minMergeCost(i, k - 1, arr) + minMergeCost(k, j, arr)); } // Returning the solved value return x;}// Driver codepublic static void main(String[] args){ int arr[] = { 1, 3, 7 }; int n = arr.length; System.out.print(minMergeCost(0, n - 1, arr));}}// This code is contributed by PrinciRaj1992 |
Python3
# Python3 implementation of the approachimport sysN = 401;# To store the states of DPdp = [[0 for i in range(N)] for j in range(N)];v = [[False for i in range(N)] for j in range(N)];# Function to return the minimum merge costdef minMergeCost(i, j, arr): # Base case if (i == j): return 0; # If the state has been solved before if (v[i][j]): return dp[i][j]; # Marking the state as solved v[i][j] = True; x = dp[i][j]; # Reference to dp[i][j] x = sys.maxsize; # To store the sum of all the # elements in the subarray arr[i...j] tot = 0; for k in range(i, j + 1): tot += arr[k]; # Loop to iterate the recurrence for k in range(i + 1, j + 1): x = min(x, tot + minMergeCost(i, k - 1, arr) + \ minMergeCost(k, j, arr)); # Returning the solved value return x;# Driver codeif __name__ == '__main__': arr = [ 1, 3, 7 ]; n = len(arr); print(minMergeCost(0, n - 1, arr));# This code is contributed by PrinciRaj1992 |
C#
// C# implementation of the approachusing System;class GFG{static readonly int N = 401;// To store the states of DPstatic int [,]dp = new int[N, N];static bool [,]v = new bool[N, N];// Function to return the minimum merge coststatic int minMergeCost(int i, int j, int[] arr){ // Base case if (i == j) return 0; // If the state has been solved before if (v[i, j]) return dp[i, j]; // Marking the state as solved v[i, j] = true; int x = dp[i, j]; // Reference to dp[i,j] x = int.MaxValue; // To store the sum of all the // elements in the subarray arr[i...j] int tot = 0; for (int k = i; k <= j; k++) tot += arr[k]; // Loop to iterate the recurrence for (int k = i + 1; k <= j; k++) { x = Math.Min(x, tot + minMergeCost(i, k - 1, arr) + minMergeCost(k, j, arr)); } // Returning the solved value return x;}// Driver codepublic static void Main(String[] args){ int []arr = { 1, 3, 7 }; int n = arr.Length; Console.Write(minMergeCost(0, n - 1, arr));}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript implementation of the approachvar N = 401// To store the states of DPvar dp = Array.from(Array(N), ()=> Array(N));var v = Array.from(Array(N), ()=> Array(N));// Function to return the minimum merge costfunction minMergeCost(i, j, arr){ // Base case if (i == j) return 0; // If the state has been solved before if (v[i][j]) return dp[i][j]; // Marking the state as solved v[i][j] = 1; var x = dp[i][j]; // Reference to dp[i][j] x = 1000000000; // To store the sum of all the // elements in the subarray arr[i...j] var tot = 0; for (var k = i; k <= j; k++) tot += arr[k]; // Loop to iterate the recurrence for (var k = i + 1; k <= j; k++) { x = Math.min(x, tot + minMergeCost(i, k - 1, arr) + minMergeCost(k, j, arr)); } // Returning the solved value return x;}// Driver codevar arr = [1, 3, 7];var n = arr.length;document.write( minMergeCost(0, n - 1, arr));</script> |
Output
15
Time complexity: O(N^3), where N is the size of the input array. This is because the code uses a recursive approach with overlapping subproblems. Each recursive call can potentially split the array into two subarrays, resulting in a total of N^2 possible subarrays. For each subarray, the code calculates the sum of its elements in O(N) time. Therefore, the overall time complexity is O(N^3).
Auxiliary space: O(N^2). The code uses a 2D array dp of size N x N to store the states of the dynamic programming solution. Additionally, it uses a 2D array v of the same size to mark whether a state has been solved before or not. Hence, the overall auxiliary space complexity is O(N^2).
Efficient approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Step-by-step approach:
- Declare a DP table dp[][] to store the minimum merge cost values.
- Declare a prefixSum[] to store the cumulative sum of elements in the input array.
- The DP table dp[][] is filled diagonally using nested loops. The outer loop iterates over the possible lengths of subarrays to be merged, and the inner loop iterates over the starting index of each subarray.
- Within the inner loop, another loop iterates over the possible split points in the subarray and calculates the cost of merging the two subarrays.
- The minimum merge cost for each subarray is stored in the DP table.
- Finally, return the minimum merge cost at dp[1][n].
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;#define N 401// Function to return the minimum merge costint minMergeCost(int* arr, int n){ // DP table int dp[N][N] = { 0 }; // Calculating the cumulative sum of elements int prefixSum[N] = { 0 }; for (int i = 1; i <= n; i++) prefixSum[i] = prefixSum[i - 1] + arr[i - 1]; // Filling the DP table diagonally for (int len = 2; len <= n; len++) { for (int i = 1; i <= n - len + 1; i++) { int j = i + len - 1; dp[i][j] = INT_MAX; for (int k = i; k < j; k++) { // Calculate the cost of merging the two // subarrays dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + prefixSum[j] - prefixSum[i - 1]); } } } // Returning the minimum merge cost return dp[1][n];}// Driver codeint main(){ int arr[] = { 1, 3, 7 }; int n = sizeof(arr) / sizeof(int); cout << minMergeCost(arr, n); return 0;} |
Java
public class MinimumMergeCost { static final int N = 401; // Function to return the minimum merge cost static int minMergeCost(int[] arr, int n) { // DP table int[][] dp = new int[N][N]; // Calculating the cumulative sum of elements int[] prefixSum = new int[N]; for (int i = 1; i <= n; i++) { prefixSum[i] = prefixSum[i - 1] + arr[i - 1]; } // Filling the DP table diagonally for (int len = 2; len <= n; len++) { for (int i = 1; i <= n - len + 1; i++) { int j = i + len - 1; dp[i][j] = Integer.MAX_VALUE; for (int k = i; k < j; k++) { // Calculate the cost of merging the two subarrays dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + prefixSum[j] - prefixSum[i - 1]); } } } // Returning the minimum merge cost return dp[1][n]; } // Driver code public static void main(String[] args) { int[] arr = { 1, 3, 7 }; int n = arr.length; System.out.println(minMergeCost(arr, n)); }} |
Python3
import sysN = 401# Function to return the minimum merge costdef minMergeCost(arr, n): # DP table dp = [[0] * N for _ in range(N)] # Calculating the cumulative sum of elements prefixSum = [0] * N for i in range(1, n + 1): prefixSum[i] = prefixSum[i - 1] + arr[i - 1] # Filling the DP table diagonally for length in range(2, n + 1): for i in range(1, n - length + 2): j = i + length - 1 dp[i][j] = sys.maxsize for k in range(i, j): # Calculate the cost of merging the two subarrays dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + prefixSum[j] - prefixSum[i - 1]) # Returning the minimum merge cost return dp[1][n]# Driver codearr = [1, 3, 7]n = len(arr)print(minMergeCost(arr, n)) |
C#
using System;class GFG { const int N = 401; // Define the constant N // Function to return the minimum merge cost static int MinMergeCost(int[] arr, int n) { // DP table int[, ] dp = new int[N, N]; // Calculating the cumulative sum of elements int[] prefixSum = new int[N]; for (int i = 1; i <= n; i++) prefixSum[i] = prefixSum[i - 1] + arr[i - 1]; // Filling the DP table diagonally for (int len = 2; len <= n; len++) { for (int i = 1; i <= n - len + 1; i++) { int j = i + len - 1; dp[i, j] = int.MaxValue; for (int k = i; k < j; k++) { // Calculate the cost of merging the two // subarrays dp[i, j] = Math.Min( dp[i, j], dp[i, k] + dp[k + 1, j] + prefixSum[j] - prefixSum[i - 1]); } } } // Returning the minimum merge cost return dp[1, n]; } // Driver code static void Main() { int[] arr = { 1, 3, 7 }; int n = arr.Length; Console.WriteLine(MinMergeCost(arr, n)); }} |
Javascript
// Function to return the minimum merge costfunction minMergeCost(arr, n) { // DP table const dp = new Array(n + 1).fill(0).map(() => new Array(n + 1).fill(0)); // Calculating the cumulative sum of elements const prefixSum = new Array(n + 1).fill(0); for (let i = 1; i <= n; i++) prefixSum[i] = prefixSum[i - 1] + arr[i - 1]; // Filling the DP table diagonally for (let len = 2; len <= n; len++) { for (let i = 1; i <= n - len + 1; i++) { let j = i + len - 1; dp[i][j] = Infinity; for (let k = i; k < j; k++) { // Calculate the cost of merging the two subarrays dp[i][j] = Math.min( dp[i][j], dp[i][k] + dp[k + 1][j] + prefixSum[j] - prefixSum[i - 1] ); } } } // Returning the minimum merge cost return dp[1][n];}// Driver codeconst arr = [1, 3, 7];const n = arr.length;console.log(minMergeCost(arr, n)); |
Output:
15
Time Complexity: O(N3)
Auxiliary Space: O(N2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
