Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Solution Approach(Dynamic Programming)
3.1.
Steps of algorithm
3.2.
Implementation in C++
3.3.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What is the Dynamic Programming Approach? 
4.2.
What is the greedy approach? 
4.3.
What are the different types of dynamic programming approaches? 
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

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

gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up
Array

Introduction

Array is one of the most common and beginner-friendly topics in Data Structures. Mastery of arrays can help to solve a number of different problems plus the concepts learned from arrays can be applied across various different data structures such as strings etc. In this article we are going to take a look at one of the most popular problems involving arrays. We will be moving from a most intuitive solution to a most optimal one discussing their limitations and advantages. Let's get right to it. 

Also Read, Byte Array to String

Problem Statement

The problem states we are given an Array, and we need to merge its adjacent element until we are left with one element only. The cost of merging any two adjacent elements is the sum of the two values we are merging. Find the minimum cost at which we can merge the array.  

Sample Examples

Example 1:

Input:
Arr[] = {4,6,4,6}

Output: 40
Illustration

Example 2:

Input:
Arr[] = {1,5,6,4,8}

Output: 54

The minimum cost to reduce the array is 54.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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);
}

 

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 ComplexityO(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:


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.

Previous article
Minimum Count of Prefixes and Suffixes of a String Required to Form Given String
Next article
Maximum size of rectangle in a binary matrix
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass