Java Top Down solution, Beats 99.56%
This is an example of dynamic programming problem of finding the answer for left part and right part and then combining the solutions.\n\nhttps://leetcode.com/d
This is an example of dynamic programming problem of finding the answer for left part and right part and then combining the solutions.\n\nhttps://leetcode.com/discuss/general-discussion/458695/dynamic-programming-patterns#Merging-Intervals\n\n```\nclass Solution {\n    public int minScoreTriangulation(int[] A) {\n        int[][] cache = new int[A.length][A.length];\n        return helper(A,0,A.length-1,cache);\n    }\n    private int helper(int[] A,int i,int j,int[][] cache){\n        // if number of vertices is less than 2, you can\'t do anything\n        if(j-i<2)\n            return 0;\n        // if number of vertices is equal to 3, then you can easily find the answer by\n        //multiplying the vertices value\n        if(j-i == 2)\n            return A[i]*A[i+1]*A[j];\n        \n        if(cache[i][j]!=0)\n            return cache[i][j];\n        int min = Integer.MAX_VALUE;\n        //sol(i,j) = sol(i,k)+sol(k,j)+A[i]*A[k]*A[j];\n        for(int k = i+1 ; k<j;k++){\n            min = Math.min(min,helper(A,i,k,cache)+helper(A,k,j,cache)+A[i]*A[k]*A[j]);\n        }\n        cache[i][j] = min;\n        return min;\n        \n    }\n}\n```
[]