Minimum cost to merge all elements of List | Java 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
class GFG { static final int N = 401 ; static int [ ] [ ] dp = new int [ N ] [ N ] ; static boolean [ ] [ ] v = new boolean [ N ] [ N ] ; static int minMergeCost ( int i , int j , int [ ] arr ) { if ( i == j ) return 0 ; if ( v [ i ] [ j ] ) return dp [ i ] [ j ] ; v [ i ] [ j ] = true ; int x = dp [ i ] [ j ] ; x = Integer . MAX_VALUE ; int tot = 0 ; for ( int k = i ; k <= j ; k ++ ) tot += arr [ k ] ; for ( int k = i + 1 ; k <= j ; k ++ ) { x = Math . min ( x , tot + minMergeCost ( i , k - 1 , arr ) + minMergeCost ( k , j , arr ) ) ; } return x ; } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 3 , 7 } ; int n = arr . length ; System . out . print ( minMergeCost ( 0 , n - 1 , arr ) ) ; } }