Minimize Cost to reduce the Array to a single element by given operations | C ++ program for the above approach ; Function to generate the cost using Prefix Sum Array technique ; Function to combine the sum of the two subproblems ; Function to minimize the cost to add the array elements to a single element ; Check if the value is already stored in the array ; Compute left subproblem ; Compute left subproblem ; Calculate minimum cost ; Store the answer to avoid recalculation ; Driver code ; Initialise dp array ; Preprocessing the array
#include <bits/stdc++.h> NEW_LINE using namespace std ; int inf = 10000000 ; vector < int > preprocess ( vector < int > a , int n ) { vector < int > p ( n ) ; p [ 0 ] = a [ 0 ] ; for ( int i = 1 ; i < n ; i ++ ) { p [ i ] = p [ i - 1 ] + a [ i ] ; } return p ; } int Combine ( vector < int > p , int i , int j ) { if ( i == 0 ) return p [ j ] ; else return p [ j ] - p [ i - 1 ] ; } int minCost ( vector < int > a , int i , int j , int k , vector < int > prefix , vector < vector < int > > dp ) { if ( i >= j ) return 0 ; if ( dp [ i ] [ j ] != -1 ) return dp [ i ] [ j ] ; int best_cost = inf ; for ( int pos = i ; pos < j ; pos ++ ) { int left = minCost ( a , i , pos , k , prefix , dp ) ; int right = minCost ( a , pos + 1 , j , k , prefix , dp ) ; best_cost = min ( best_cost , left + right + ( k * Combine ( prefix , i , j ) ) ) ; } return dp [ i ] [ j ] = best_cost ; } int main ( ) { int n = 4 ; vector < int > a = { 4 , 5 , 6 , 7 } ; int k = 3 ; vector < vector < int > > dp ; dp . resize ( n + 1 , vector < int > ( n + 1 ) ) ; for ( int i = 0 ; i < n + 1 ; i ++ ) { for ( int j = 0 ; j < n + 1 ; j ++ ) { dp [ i ] [ j ] = -1 ; } } vector < int > prefix = preprocess ( a , n ) ; cout << minCost ( a , 0 , n - 1 , k , prefix , dp ) << endl ; return 0 ; }