题目描述
给定 N，想象一个凸 N 边多边形，其顶点按顺时针顺序依次标记为 A[0], A[i], ..., A[N-1]。
假设您将多边形剖分为 N-2 个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有 N-2 个三角形的值之和。
返回多边形进行三角剖分后可以得到的最低分。
示例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
题解
可以发现，一刀下去，两个多边形只有一条边是在内部，其他边都是连续的外围的边，如下图所示：
代码
c++
classSolution { public: staticconstintN=55; intdp[N][N]; intminScoreTriangulation(vector<int>&A) { intn=A.size(); memset(dp, 0, sizeofdp); for (intlen=3; len<=n; ++len) { for (inti=0; i<n; ++i) { intj=i+len-1; inttmp=INT_MAX; for (intk=i+1; k<j; ++k) { tmp=min(tmp, A[i]*A[j%n]*A[k%n]+dp[i] [k%n]+dp[k%n][j%n]); } dp[i][j%n] =tmp; } } returndp[0][n-1]; } };
python
classSolution: defminScoreTriangulation(self, A: List[int]) ->int: n=len(A) dp= [[0]*nfor_inrange(n)] forlinrange(3, n+1): foriinrange(n): j=i+l-1tmp=0x3f3f3f3fforkinrange(i+1, j): tmp=min(tmp, A[i]*A[j%n]*A[k%n]+dp[i] [k%n]+dp[k%n][j%n]) dp[i][j%n] =tmpreturndp[0][n-1]
作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~
