题目
给定 N,想象一个凸 N 边多边形,其顶点按顺时针顺序依次标记为 A[0], A[i], ..., A[N-1]。
假设您将多边形剖分为 N-2 个三角形。...对于每个三角形,该三角形的值是顶点标记的乘积,三角剖分的分数是进行三角剖分后所有 N-2 个三角形的值之和。
返回多边形进行三角剖分后可以得到的最低分。...示例 1:
输入:[1,2,3]
输出:6
解释:多边形已经三角化,唯一三角形的分数为 6。
示例 2:
?...示例 3:
输入:[1,3,1,4,1,5]
输出:13
解释:最低分数三角剖分的得分情况为
1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13。...叶值的最小代价生成树(区间DP/单调栈贪心)
dp[i][j] 表示区间 [i,j] 所有组成的三角形得分之和的最小值
区间长度从 3 开始往上变大
状态转移方程为dp[i][j]=min(dp[i][