LeetCode 1039. 多边形三角剖分的最低得分（区间DP）

示例 1：
输入：[1,2,3]
输出：6
解释：多边形已经三角化，唯一三角形的分数为 6。

示例 2：

输入：[3,7,4,5]
输出：144
解释：有两种三角剖分，
可能得分分别为：3*7*5 + 4*5*7 = 245，
或 3*4*5 + 3*4*7 = 144。
最低分数为 144。

示例 3：
输入：[1,3,1,4,1,5]
输出：13
解释：最低分数三角剖分的得分情况为 
1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13。
 
提示：
3 <= A.length <= 50
1 <= A[i] <= 100

class Solution {
public:
    int minScoreTriangulation(vector<int>& A) {
    	int n = A.size(), len, i, j, k;
    	vector<vector<int>> dp(n, vector<int>(n, 0));
    	for(len = 3; len <= n; ++len)
    	{
    		for(i = 0; i < n; ++i)
    		{
    			j = i+len-1;
    			if(j >= n) continue;
    			dp[i][j] = INT_MAX;
    			for(k = i+1; k < j; ++k)
    			{
    				dp[i][j] = min(dp[i][j], dp[i][k]+A[i]*A[k]*A[j]+dp[k][j]);
    			}
    		}
    	}
    	return dp[0][n-1];
    }
};