package leetcode;

/**
 * https://leetcode.com/problems/minimum-score-triangulation-of-polygon/
 */
public class Problem1039 {
    public int minScoreTriangulation(int[] A) {
        // TODO
        return 0;
    }

    public static void main(String[] args) {
        Problem1039 prob = new Problem1039();
        System.out.println(prob.minScoreTriangulation(new int[]{1, 2, 3})); // 6
        System.out.println(prob.minScoreTriangulation(new int[]{3, 7, 4, 5})); // 144
        System.out.println(prob.minScoreTriangulation(new int[]{1, 3, 1, 4, 1, 5})); // 13
        System.out.println(prob.minScoreTriangulation(new int[]{1, 3, 1, 4, 1, 5, 6})); // 43
        System.out.println(prob.minScoreTriangulation(new int[]{1, 3, 1, 4, 1, 5, 6, 8})); // 91
    }
}

@@ -180,32 +180,122 @@
     
-// TODO%0A        return 0
+Integer%5B%5D%5B%5D memo = new Integer%5BA.length%5D%5BA.length%5D;%0A        return minScoreTriangulation(A, 0, A.length - 1, memo)
 ;%0A  
@@ -308,21 +308,22 @@
    p
-ublic
+rivate
  static 
 void
@@ -322,280 +322,319 @@
 tic 
-void
+int
  m
-a
 in
-(St
+ScoreT
 ri
+a
 ng
-%5B%5D args) %7B%0A        Problem1039 prob = new Problem1039();%0A        System.out.println(prob.minScoreTriangulation(new int%5B%5D%7B1, 2, 3%7D)); // 6%0A        System.out.println(prob.minScoreTriangulation(new int%5B%5D%7B3, 7, 4, 5%7D)); // 144%0A        System.out.println(prob.
+ulation(int%5B%5D array, int i, int j, Integer%5B%5D%5B%5D memo) %7B%0A        if (j - i + 1 %3C 3) %7B%0A            return 0;%0A        %7D%0A        if (memo%5Bi%5D%5Bj%5D != null) %7B%0A            return memo%5Bi%5D%5Bj%5D;%0A        %7D%0A        int min = Integer.MAX_VALUE;%0A        for (int k = i + 1; k %3C j; k++) %7B%0A            int val = (
 minS
@@ -655,77 +655,45 @@
 ion(
-new int%5B%5D%7B1, 3, 1, 4, 1, 5%7D)); // 13%0A        System.out.println(prob.
+array, i, k, memo) +%0A                
 minS
@@ -714,144 +714,173 @@
 ion(
-new int%5B%5D%7B1, 3, 1, 4, 1, 5, 6%7D)); // 43%0A        System.out.println(prob.minScoreTriangulation(new int%5B%5D%7B1, 3, 1, 4, 1, 5, 6, 8%7D)); // 91
+array, k, j, memo)) +%0A                (array%5Bi%5D * array%5Bj%5D * array%5Bk%5D);%0A            min = Math.min(min, val);%0A        %7D%0A        memo%5Bi%5D%5Bj%5D = min;%0A        return min;
 %0A   

Solve problem 1039