Minimize cost to reduce array to a single element by replacing K consecutive elements by their sum | Function to find the minimum cost to reduce given array to a single element by replacing consecutive K array elements ; Stores length of arr ; 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
def minimumCostToMergeK ( arr , K ) : NEW_LINE INDENT N = len ( arr ) NEW_LINE if ( N - 1 ) % ( K - 1 ) != 0 : NEW_LINE INDENT return - 1 NEW_LINE DEDENT prefixSum = [ 0 ] * ( N + 1 ) NEW_LINE for i in range ( 1 , N + 1 ) : NEW_LINE INDENT prefixSum [ i ] = ( prefixSum [ i - 1 ] + arr [ i - 1 ] ) NEW_LINE DEDENT dp = [ [ 0 ] * N for _ in range ( N ) ] NEW_LINE for L in range ( K , N + 1 ) : NEW_LINE INDENT for i in range ( N - L + 1 ) : NEW_LINE INDENT j = i + L - 1 NEW_LINE if L > K : NEW_LINE INDENT dp [ i ] [ j ] = ( min ( [ dp [ i ] [ x ] + dp [ x + 1 ] [ j ] for x in range ( i , j , K - 1 ) ] ) ) NEW_LINE DEDENT if ( L - 1 ) % ( K - 1 ) == 0 : NEW_LINE INDENT dp [ i ] [ j ] += ( prefixSum [ j + 1 ] - prefixSum [ i ] ) NEW_LINE DEDENT DEDENT DEDENT return dp [ 0 ] [ N - 1 ] NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 3 , 5 , 1 , 2 , 6 ] NEW_LINE K = 3 NEW_LINE DEDENT print ( minimumCostToMergeK ( arr , K ) ) NEW_LINE