https://leetcode.com/problems/minimum-score-triangulation-of-polygon/
题意：给定一个凸的N边形(N<=50)，每个顶点有一个权值A[i]，把它分为N-2个三角形，每个三角形的val等于三个顶点的权值的乘积，问划分之后图形的val总和最小为多少。
一开始想到了，问题可以转换为求解子问题，由于没有想到如何进行状态转换，并且感觉贪心可行，
如下图1，将当前图形可以构成的三角形找出（红线为底边），从中找到val最小的三角形如图2，然后将其割除如图3，再将新的两个三角形找出。
然而这个思路并不可行，这个思路的局部最优并不能得到全局最优，按照上面的思路的策略如下图，得到结果40，而最优解是24。
贪心不可行，每次找到最优的三角形，最终全局未必最优。
然后，想到很可能是动态规划，但是想不出来，问题如何分解，状态如何表示。。。
参考别人的思路和代码（看了两个大佬的代码，思路几乎一样）
对于多边形上的任意一条边，它只能出现在一个三角形中，
dp[i][j]：从第i个点到第j个点的最小值。dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]+A[i]*A[j]*A[k])。
如下图：此时求dp[0][5]，以（0,5）为边，在（0,5）之间遍历三角形的顶点，构成的每个三角形将原图形分为三部分：三角形，子图形1，子图形2。
class Solution { public: int minScoreTriangulation(vector<int>& A) { int dp[50][50]; memset(dp,0,sizeof(dp)); int numofnode = A.size(); for(int len=3; len<=numofnode; len++) for(int i=0; i+len-1<numofnode; i++) { int j=i+len-1; dp[i][j]=INT_MAX; for(int k=i+1; k<j; k++) dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j]+A[i]*A[j]*A[k]); } return dp[0][A.size()-1]; } };