Intuitive Java Solution With Explanation
Few observations needed before discussing the approach.\n First observe that we only stop drawing inner edges, when we cannot form any more triangels. Obviously
Few observations needed before discussing the approach.\n* First observe that we only stop drawing inner edges, when we cannot form any more triangels. Obviously every such triangle has 1 edge from the given polygon or 2 edges. That means, the stop condition is all edges from the polygon are covered.\n*  Also observe that it doesn\'t matter which triangle you are trying first. Ultimately, if it is part of optimal configuration, it will end up in the final solution (i.e. doesn\'t matter which subproblem formed that triangle, this will be more clear with the below pic).\n\n\n**Idea**\nUsing the above facts, for convenience we can fix the edge connecting first and last point and see how many triangles can this edge possible be part of (to begin with). And each of the possibilties divide the problem in two parts (left part and right part) and they can be solved recusrively. To repeat, it doesn\'t matter which edge you fix and try possibilities, the fixed edge will always settle with the optimal triangle irrespective of which edge you fix first but fixing other edges will not play well with array indicies.\n\nIn this pic, we fixed 0-5 edge and shown all 4 possilities.\n![image](https://assets.leetcode.com/users/naveenkothamasu/image_1566360233.png)\n\n\n\n\n**Solution1 (TLE)**\n```\npublic int minScoreTriangulation(int[] a) {\n        return helper(a, 0, a.length-1);\n    }\n    private int helper(int[] a, int i, int j){\n        if( (j-i+1) < 3) return 0;\n        int min = Integer.MAX_VALUE;\n        for(int k=i+1; k < j; k++)\n            min = Math.min(min, helper(a, i, k)+a[i]*a[k]*a[j]+helper(a, k, j));\n        return min;\n    }\n```\n**Solution2 (DP)**\n```\nclass Solution {\n    Integer[][] dp = null;\n    public int minScoreTriangulation(int[] a) {\n        dp = new Integer[a.length][a.length];\n        return helper(a, 0, a.length-1);\n    }\n    private int helper(int[] a, int i, int j){\n        if( (j-i+1) < 3) return 0;\n        if(dp[i][j] != null) return dp[i][j];\n        dp[i][j] = Integer.MAX_VALUE;\n        for(int k=i+1; k < j; k++)\n            dp[i][j] = Math.min(dp[i][j], helper(a, i, k)+a[i]*a[k]*a[j]+helper(a, k, j));\n        return dp[i][j];\n    }\n}\n```
[]