Minimum cost to merge all elements of List | Javascript 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
var N = 401 var dp = Array . from ( Array ( N ) , ( ) => Array ( N ) ) ; var v = Array . from ( Array ( N ) , ( ) => Array ( N ) ) ; function minMergeCost ( i , j , arr ) { if ( i == j ) return 0 ; if ( v [ i ] [ j ] ) return dp [ i ] [ j ] ; v [ i ] [ j ] = 1 ; var x = dp [ i ] [ j ] ; x = 1000000000 ; var tot = 0 ; for ( var k = i ; k <= j ; k ++ ) tot += arr [ k ] ; for ( var k = i + 1 ; k <= j ; k ++ ) { x = Math . min ( x , tot + minMergeCost ( i , k - 1 , arr ) + minMergeCost ( k , j , arr ) ) ; } return x ; } var arr = [ 1 , 3 , 7 ] ; var n = arr . length ; document . write ( minMergeCost ( 0 , n - 1 , arr ) ) ;