Minimize Cost to reduce the Array to a single element by given operations | Java Program for the above approach ; 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 ; Function to generate the cost using Prefix Sum Array technique ; Function to combine the sum of the two subproblems ; Driver Code ; Initialise dp array ; Preprocessing the array
import java . util . * ; public class Main { static int inf = 10000000 ; public static int minCost ( int a [ ] , int i , int j , int k , int [ ] prefix , 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 = Math . min ( best_cost , left + right + ( k * Combine ( prefix , i , j ) ) ) ; } return dp [ i ] [ j ] = best_cost ; } public static int [ ] preprocess ( int [ ] a , int n ) { int p [ ] = new int [ n ] ; p [ 0 ] = a [ 0 ] ; for ( int i = 1 ; i < n ; i ++ ) p [ i ] = p [ i - 1 ] + a [ i ] ; return p ; } public static int Combine ( int [ ] p , int i , int j ) { if ( i == 0 ) return p [ j ] ; else return p [ j ] - p [ i - 1 ] ; } public static void main ( String args [ ] ) { int n = 4 ; int a [ ] = { 4 , 5 , 6 , 7 } ; int k = 3 ; int dp [ ] [ ] = new int [ n + 1 ] [ n + 1 ] ; for ( int i [ ] : dp ) Arrays . fill ( i , - 1 ) ; int prefix [ ] = preprocess ( a , n ) ; System . out . println ( minCost ( a , 0 , n - 1 , k , prefix , dp ) ) ; } }