java dp
It is always the matter of modeling.\nIn this problem, the key step is that when we take out any triangle from a polygen, the remain parts of the polygen can be
It is always the matter of modeling.\nIn this problem, the key step is that when we take out any triangle from a polygen, the remain parts of the polygen can be split up to smaller polygen but faces same kind of problems,  which constructs subproblems here.\n\nfrom this point, a top-down version that is easier to understand is generated: \nwhen we pick up a triangle, we can just use the same recursion function to both the left and the right part of the rest polygen. And we do this for every triangle to see which one (together with its subproblems) is the smallest.\n\n\nThe bottom-up version may be harder to get over. First we have to compute the product of every triangle that is formed by continous three numbers. This is the base situation for dp.  \nAfter that, we gradually increase the current searched polygen size in every loop, and for every current polygen, we compute every product for two edge vertices and one node within. and the dp value for current polygen is the min of these products. here we construct the dp for size k.\nBy this means, we can reach polygen from size 3 to n, and get the min for size n, which is the answer.\n\n\n```\nclass Solution {\n    public int minScoreTriangulation(int[] A) {\n        int n = A.length, j;\n        int[][] dp = new int[n][n];\n        for (int d=2;d<n;d++){\n            for (int i=0; i+d<n; i++){\n                j = i+d;\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], A[i]*A[j]*A[k]+\n                                       dp[i][k]+dp[k][j]);\n                }\n            }\n        }\n        return dp[0][n-1];\n    }\n}\n```
[]