package leetcode;

/**
 * https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/
 */
public class Problem1130 {
    public int mctFromLeafValues(int[] arr) {
        return mctFromLeafValues(arr, 0, arr.length - 1).sum;
    }

    private static MaxSum mctFromLeafValues(int[] array, int start, int end) {
        if (start == end) {
            return new MaxSum(array[start], 0);
        }
        int max = 0;
        int sum = Integer.MAX_VALUE;
        for (int i = start; i < end; i++) {
            MaxSum left = mctFromLeafValues(array, start, i);
            MaxSum right = mctFromLeafValues(array, i + 1, end);
            max = Math.max(max, Math.max(left.max, right.max));
            sum = Math.min(sum, left.sum + right.sum + left.max * right.max);
        }
        return new MaxSum(max, sum);
    }

    private static class MaxSum {
        private final int max;
        private final int sum;

        public MaxSum(int max, int sum) {
            this.max = max;
            this.sum = sum;
        }
    }

    public static void main(String[] args) {
        Problem1130 prob = new Problem1130();
        System.out.println(prob.mctFromLeafValues(new int[]{6, 2, 4})); // 32
        System.out.println(prob.mctFromLeafValues(new int[]{6, 2, 4, 5})); // 58
        System.out.println(prob.mctFromLeafValues(new int[]{6, 2})); // 12
        System.out.println(prob.mctFromLeafValues(new int[]{6, 2, 4, 1, 7})); // 78
    }
}

@@ -217,16 +217,52 @@
 ngth - 1
+, new MaxSum%5Barr.length%5D%5Barr.length%5D
 ).sum;%0A 
@@ -338,24 +338,41 @@
 art, int end
+, MaxSum%5B%5D%5B%5D memo
 ) %7B%0A        
@@ -441,32 +441,119 @@
 , 0);%0A        %7D%0A
+        if (memo%5Bstart%5D%5Bend%5D != null) %7B%0A            return memo%5Bstart%5D%5Bend%5D;%0A        %7D%0A
         int max 
@@ -697,16 +697,22 @@
 start, i
+, memo
 );%0A     
@@ -768,16 +768,22 @@
 + 1, end
+, memo
 );%0A     
@@ -929,38 +929,47 @@
       %7D%0A        
-return
+MaxSum answer =
  new MaxSum(max,
@@ -975,16 +975,74 @@
 , sum);%0A
+        memo%5Bstart%5D%5Bend%5D = answer;%0A        return answer;%0A
     %7D%0A%0A 
@@ -1254,423 +1254,7 @@
    %7D
-%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem1130 prob = new Problem1130();%0A        System.out.println(prob.mctFromLeafValues(new int%5B%5D%7B6, 2, 4%7D)); // 32%0A        System.out.println(prob.mctFromLeafValues(new int%5B%5D%7B6, 2, 4, 5%7D)); // 58%0A        System.out.println(prob.mctFromLeafValues(new int%5B%5D%7B6, 2%7D)); // 12%0A        System.out.println(prob.mctFromLeafValues(new int%5B%5D%7B6, 2, 4, 1, 7%7D)); // 78%0A    %7D
 %0A%7D%0A

Solve problem 1130