Minimum cost of reducing Array by merging any adjacent elements repetitively | Python3 program for the above approach ; Function to find the total minimum cost of merging two consecutive numbers ; Find the size of numbers [ ] ; If array is empty , return 0 ; To store the prefix Sum of numbers array numbers [ ] ; Traverse numbers [ ] to find the prefix sum ; dp table to memoised the value ; For single numbers cost is zero ; Iterate for length >= 1 ; Find sum in range [ i . . j ] ; Initialise dp [ i ] [ j ] to _MAX ; Iterate for all possible K to find the minimum cost ; Update the minimum sum ; Return the final minimum cost ; Given set of numbers ; Function call
import sys NEW_LINE def mergeTwoNumbers ( numbers ) : NEW_LINE INDENT n = len ( numbers ) NEW_LINE if ( len ( numbers ) == 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT prefixSum = [ 0 ] * ( n + 1 ) NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT prefixSum [ i ] = ( prefixSum [ i - 1 ] + numbers [ i - 1 ] ) NEW_LINE DEDENT dp = [ [ 0 for i in range ( n + 1 ) ] for j in range ( n + 1 ) ] NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT dp [ i ] [ i ] = 0 NEW_LINE DEDENT for p in range ( 2 , n + 1 ) : NEW_LINE INDENT for i in range ( 1 , n - p + 2 ) : NEW_LINE INDENT j = i + p - 1 NEW_LINE sum = prefixSum [ j ] - prefixSum [ i - 1 ] NEW_LINE dp [ i ] [ j ] = sys . maxsize NEW_LINE for k in range ( i , j ) : NEW_LINE INDENT dp [ i ] [ j ] = min ( dp [ i ] [ j ] , ( dp [ i ] [ k ] + dp [ k + 1 ] [ j ] + sum ) ) NEW_LINE DEDENT DEDENT DEDENT return dp [ 1 ] [ n ] NEW_LINE DEDENT arr1 = [ 6 , 4 , 4 , 6 ] NEW_LINE print ( mergeTwoNumbers ( arr1 ) ) NEW_LINE