Finding the Minimum Cost to Reduce the Array by Merging the Adjacent Elements Repetitively

Solution Approach(Dynamic Programming)

The idea is to merge two consecutive numbers into every possible index j, and then recursively solve for the left and right parts of index j. Since many overlapping subproblems can occur, we will optimize it using a memoization table. The algorithm to calculate the minimum cost to reduce the array is: 

(See Dynamic Programming)

Steps of algorithm

1. Create a 2D array dp[N][N].
2. Merge 2 consecutive numbers, then add the result of merging two numbers and store the minimum of them. 
3.  The recurrence relation to find the minimum cost to merge array is given as:
   dp[i][j] = min((sum[i][j]+dp[i][k]+dp[k+1][j]), 
   dp[i][j]) where sum[i][j] is the total sum of the array between the range of i to j, and dp[i][k] represents the minimum cost when we merged the array between indexes i and j, and dp[k+1][j] represents the minimum cost for merging the array between indexes k+1 and j, dp[i][j] is the minimum cost for merging the array between indexes i and j. 
4. Finally, dp[1][N], will give us the minimum cost to reduce the array. 

(Also see, Memoisation v/s Tabulation)

Implementation in C++

// C++ function to find the minimum cost to reduce the array 
#include<bits/stdc++.h>
using namespace std;
void minimumCostToMerge(int *arr,int n){
    // dp array to store the minimum cost
    if(n==0){
        cout << "0" << endl;
        return;
    }
    
    int dp[n+1][n+1];
    // prefixSum array to store the prefix sum of array arr.
    int *prefixSum = new int[n+1];
    memset(prefixSum, 0, sizeof(prefixSum));
    
    for(int i=1;i<=n;i++){
        prefixSum[i] = prefixSum[i-1] + arr[i-1];
    }
    
    // merging the single number, cost to 0.
    for(int i=1;i<=n;i++){
        dp[i][i] = 0;
    }
    
    // checking for each length
    for(int length = 2; length<=n;length++){
        for(int i=1;i<=n-length+1;i++){
            // index that is length ahead of i
            int j = i+length-1;
            
            // calculating sum in the range of [i..j].
            int sum = prefixSum[j]-prefixSum[i-1];
            
            dp[i][j] = INT_MAX;
            for(int k=i;k<j;k++){
                // using the recurrence relation that we have deduced
                // to find the minimum cost of reducing the array
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+sum);
            }
        }
    }
    
    // return the final minimum cost to reduce the array 
    cout << dp[1][n];
}
int main(){
    int arr[] = {1,5,6,4,8};
    minimumCostToMerge(arr,5);
}

You can also try this code with Online C++ Compiler

Run Code

Output: 

54 

Complexity Analysis

Time Complexity: O(N^3)

Explanation: Since we using 3 nested loops, therefore the time complexity is O(N^3).

Space Complexity: O(N^2)

Explanation: We are storing the answer for each row and column in the Dp array of NxN size; therefore, space complexity is O(N^2). 

Check out this array problem - Merge 2 Sorted Arrays

Frequently Asked Questions

What is the Dynamic Programming Approach? 

Dynamic programming is an approach to optimize recursive solutions when recursive calls on the same input repeatedly. The idea is simple, store the result and need to calculate it again and again to use it.  

What is the greedy approach? 

It is an algorithm to get the optimal solution for the problem. In this algorithm, we always choose the next best solution that seems optimal at that step. We build solutions piece by piece to reach the optimal solution. 

What are the different types of dynamic programming approaches? 

There are generally two types of approaches:

Top-Down Approach: In this approach, we break the bigger problem into smaller subproblems. 

Bottom-Up Approach: In this approach, we join the smaller subproblem, to find the solution to a bigger problem.

Conclusion

In this article, we have discussed the problem of finding the minimum cost to reduce the array by merging the adjacent elements repetitively. We discussed the Dp-based optimized solution. We hope you understand the problem and solution properly. Now you can do more similar questions. 

Recommended Problems:

• Maximum Subarray Sum
• Minimum Cost to Buy Oranges
• Minimum Cost Path

Thank you for reading. 

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Until then, Keep Learning and Keep Coding.