Minimize Cost to reduce the Array to a single element by given operations | JavaScript 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
var inf = 10000000 ; function preprocess ( a , n ) { var p = Array ( n ) ; p [ 0 ] = a [ 0 ] ; for ( var i = 1 ; i < n ; i ++ ) { p [ i ] = p [ i - 1 ] + a [ i ] ; } return p ; } function Combine ( p , i , j ) { if ( i == 0 ) return p [ j ] ; else return p [ j ] - p [ i - 1 ] ; } function minCost ( a , i , j , k , prefix , dp ) { if ( i >= j ) return 0 ; if ( dp [ i ] [ j ] != - 1 ) return dp [ i ] [ j ] ; var best_cost = inf ; for ( var pos = i ; pos < j ; pos ++ ) { var left = minCost ( a , i , pos , k , prefix , dp ) ; var right = minCost ( a , pos + 1 , j , k , prefix , dp ) ; best_cost = Math . min ( best_cost , left + right + ( k * Combine ( prefix , i , j ) ) ) ; } return dp [ i ] [ j ] = best_cost ; } var n = 4 ; var a = [ 4 , 5 , 6 , 7 ] ; var k = 3 ; var dp = Array . from ( Array ( n + 1 ) , ( ) => Array ( n + 1 ) . fill ( - 1 ) ) ; var prefix = preprocess ( a , n ) ; document . write ( minCost ( a , 0 , n - 1 , k , prefix , dp ) )