Minimum cost to merge all elements of List | Python3 implementation of the approach ; To store the states of DP ; Function to return the minimum merge cost ; Base case ; If the state has been solved before ; Marking the state as solved ; Reference to dp [ i ] [ j ] ; To store the sum of all the elements in the subarray arr [ i ... j ] ; Loop to iterate the recurrence ; Returning the solved value ; Driver code
import sys NEW_LINE N = 401 ; NEW_LINE dp = [ [ 0 for i in range ( N ) ] for j in range ( N ) ] ; NEW_LINE v = [ [ False for i in range ( N ) ] for j in range ( N ) ] ; NEW_LINE def minMergeCost ( i , j , arr ) : NEW_LINE INDENT if ( i == j ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT if ( v [ i ] [ j ] ) : NEW_LINE INDENT return dp [ i ] [ j ] ; NEW_LINE DEDENT v [ i ] [ j ] = True ; NEW_LINE x = dp [ i ] [ j ] ; NEW_LINE x = sys . maxsize ; NEW_LINE tot = 0 ; NEW_LINE for k in range ( i , j + 1 ) : NEW_LINE INDENT tot += arr [ k ] ; NEW_LINE DEDENT for k in range ( i + 1 , j + 1 ) : NEW_LINE INDENT x = min ( x , tot + minMergeCost ( i , k - 1 , arr ) + minMergeCost ( k , j , arr ) ) ; NEW_LINE DEDENT return x ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 3 , 7 ] ; NEW_LINE n = len ( arr ) ; NEW_LINE print ( minMergeCost ( 0 , n - 1 , arr ) ) ; NEW_LINE DEDENT