Minimize cost to reduce array to a single element by replacing K consecutive elements by their sum | Java program to implement the above approach ; Function to find the minimum cost to reduce given array to a single element by replacing consecutive K array elements ; If ( N - 1 ) is not multiple of ( K - 1 ) ; Store prefix sum of the array ; Iterate over the range [ 1 , N ] ; Update prefixSum [ i ] ; dp [ i ] [ j ] : Store minimum cost to merge array elements interval [ i , j ] ; L : Stores length of interval [ i , j ] ; Iterate over each interval [ i , j ] of length L in in [ 0 , N ] ; Stores index of last element of the interval [ i , j ] ; If L is greater than K ; Update dp [ i ] [ j ] ; If ( L - 1 ) is multiple of ( K - 1 ) ; Update dp [ i ] [ j ] ; Return dp [ 0 ] [ N - 1 ] ; Driver Code ; Function Call
import java . util . * ; class GFG { static int minimumCostToMergeK ( int arr [ ] , int K , int N ) { if ( ( N - 1 ) % ( K - 1 ) != 0 ) { return - 1 ; } int [ ] prefixSum = new int [ N + 1 ] ; for ( int i = 1 ; i < ( N + 1 ) ; i ++ ) { prefixSum [ i ] = ( prefixSum [ i - 1 ] + arr [ i - 1 ] ) ; } int [ ] [ ] dp = new int [ N ] [ N ] ; for ( int L = K ; L < ( N + 1 ) ; L ++ ) { for ( int i = 0 ; i < ( N - L + 1 ) ; i ++ ) { int j = i + L - 1 ; if ( L > K ) { int temp = Integer . MAX_VALUE ; for ( int x = i ; x < j ; x += K - 1 ) { temp = Math . min ( temp , dp [ i ] [ x ] + dp [ x + 1 ] [ j ] ) ; } dp [ i ] [ j ] = temp ; } if ( ( L - 1 ) % ( K - 1 ) == 0 ) { dp [ i ] [ j ] += ( prefixSum [ j + 1 ] - prefixSum [ i ] ) ; } } } return dp [ 0 ] [ N - 1 ] ; } public static void main ( String [ ] args ) { int arr [ ] = { 3 , 5 , 1 , 2 , 6 } ; int K = 3 ; int N = arr . length ; System . out . print ( minimumCostToMergeK ( arr , K , N ) ) ; } }