Minimum cost of reducing Array by merging any adjacent elements repetitively | C ++ program for the above approach ; Function to find the total minimum cost of merging two consecutive numbers ; Find the size of numbers [ ] ; If array is empty , return 0 ; To store the prefix Sum of numbers array numbers [ ] ; Traverse numbers [ ] to find the prefix sum ; dp table to memoised the value ; For single numbers cost is zero ; Iterate for length >= 1 ; Find sum in range [ i . . j ] ; Initialise dp [ i ] [ j ] to INT_MAX ; Iterate for all possible K to find the minimum cost ; Update the minimum sum ; Return the final minimum cost ; Driver Code ; Given set of numbers ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int mergeTwoNumbers ( vector < int > & numbers ) { int len , i , j , k ; int n = numbers . size ( ) ; if ( numbers . size ( ) == 0 ) { return 0 ; } vector < int > prefixSum ( n + 1 , 0 ) ; for ( int i = 1 ; i <= n ; i ++ ) { prefixSum [ i ] = prefixSum [ i - 1 ] + numbers [ i - 1 ] ; } vector < vector < int > > dp ( n + 1 , vector < int > ( n + 1 ) ) ; for ( int i = 1 ; i <= n ; i ++ ) { dp [ i ] [ i ] = 0 ; } for ( len = 2 ; len <= n ; len ++ ) { for ( i = 1 ; i <= n - len + 1 ; i ++ ) { j = i + len - 1 ; int sum = prefixSum [ j ] - prefixSum [ i - 1 ] ; dp [ i ] [ j ] = INT_MAX ; for ( k = i ; k < j ; k ++ ) { dp [ i ] [ j ] = min ( dp [ i ] [ j ] , dp [ i ] [ k ] + dp [ k + 1 ] [ j ] + sum ) ; } } } return dp [ 1 ] [ n ] ; } int main ( ) { vector < int > arr1 = { 6 , 4 , 4 , 6 } ; cout << mergeTwoNumbers ( arr1 ) << endl ; return 0 ; }