Merge Elements | Dynamic Programming | InterviewBit Solution | C++ | Java |

 

Problem Description

Given an integer array A of size N. You have to merge all the elements of the array into one with the minimum possible cost.

The rule for merging is as follows:

Choose any two adjacent elements of the array with values say X and Y and merge them into a single element with value (X + Y) paying a total cost of (X + Y).

Return the minimum possible cost of merging all elements.

Problem Constraints

1 <= N <= 200

1 <= A[i] <= 103

Input Format

First and only argument is an integer array A of size N.

Output Format

Return an integer denoting the minimum cost of merging all elements.

Example Input

Input 1:

 A = [1, 3, 7]

Input 2:

 A = [1, 2, 3, 4]

Example Output

Output 1:

 15

Output 2:

 19

Example Explanation

Explanation 1:

 All possible ways of merging:
 a) {1, 3, 7} (cost = 0) -> {4, 7} (cost = 4) -> {11} (cost = 4+11 = 15)
 b) {1, 3, 7} (cost = 0) -> {1, 10} (cost = 10) -> {11} (cost = 10+11 = 21)
 Thus, ans = 15

Approach: The problem can be solved using Dynamic Programming. Below are the steps: 

1. The idea is to merge 2 consecutive numbers into every possible index i and then solve recursively for left and right parts of index i.
2. Add the result of merging two numbers in above steps and store the minimum of them.
3. Since there are many subproblems that are repeating, hence we use memoization to store the values in a NxN matrix.
4. The recurrence relation for the above problem statement is given as: 
   

   dp[i][j] = min(dp[i][j], (sum[i][j] + dp[i][k] + dp[k + 1][j])), for every (i ≤ k lt; j) 

5. Now dp[1][N] will give the minimum total cost of merging all the numbers.

Below is the implementation of the above approach:

Problem Solution in C++ Programming Language:

code:

int Solution::solve(vector<int> &A) 

{

    int n = A.size();

    if(n==0) return 0;

    vector<vector<int>> dp(n,vector<int>(n,0));

    vector<int> prefix_sum(n,0);

    prefix_sum[0] = A[0];

    for(int i=1;i<n;i++) prefix_sum[i] = prefix_sum[i-1] + A[i];

    for(int len=1;len<n;len++){

        for(int i=0;i<n-len;i++){

            int j = i+len;

            int add = INT_MAX;

            for(int k=i;k<j;k++)

                add = min(add,dp[i][k] + dp[k+1][j]);

            dp[i][j] = (prefix_sum[j]-((i==0)? 0 : prefix_sum[i-1])) + add;

        }

    }

    return dp[0][n-1];

}

Problem Solution in Java Programming Language:

code:

public class Solution {

    

    public int cal(int arr[],int i,int j,int dp[][])

    {

        if(i==j)

        {

            return 0;

        }

        

        if(dp[i][j] != 0)

        {

            return dp[i][j] ;

        }

        

        int x = Integer.MAX_VALUE;

        int tot = 0;

        

        for(int k=i;k<=j;k++)

        {

            tot += arr[k];

        }

        

        

        for(int k=i+1;k<=j;k++)

        {

            x = Math.min(x, tot +  cal(arr,i,k-1,dp)  + cal(arr,k,j,dp) );

        }

        dp[i][j]  = x;

        return x;

    }

    

    public int solve(int[] A) {

        int dp[][] = new int[A.length+1][A.length+1];

        return cal(A,0,A.length-1,dp);

    }

}

Thank you for reading.

For any questions, feedback and query comment below.

Keep coding!.

Open to suggestions please comment below:))