Minimum cost to merge all elements of List | C ++ implementation of the approach ; To store the states of DP ; Function to return the minimum merge cost ; Base case ; If the state has been solved before ; Marking the state as solved ; Reference to dp [ i ] [ j ] ; To store the sum of all the elements in the subarray arr [ i ... j ] ; Loop to iterate the recurrence ; Returning the solved value ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  401 NEW_LINE int dp [ N ] [ N ] ; bool v [ N ] [ N ] ; int minMergeCost ( int i , int j , int * arr ) { if ( i == j ) return 0 ; if ( v [ i ] [ j ] ) return dp [ i ] [ j ] ; v [ i ] [ j ] = 1 ; int & x = dp [ i ] [ j ] ; x = INT_MAX ; int tot = 0 ; for ( int k = i ; k <= j ; k ++ ) tot += arr [ k ] ; for ( int k = i + 1 ; k <= j ; k ++ ) { x = min ( x , tot + minMergeCost ( i , k - 1 , arr ) + minMergeCost ( k , j , arr ) ) ; } return x ; } int main ( ) { int arr [ ] = { 1 , 3 , 7 } ; int n = sizeof ( arr ) / sizeof ( int ) ; cout << minMergeCost ( 0 , n - 1 , arr ) ; return 0 ; }