题目描述
给定 N,想象一个凸 N 边多边形,其顶点按顺时针顺序依次标记为 A[0], A[i], ..., A[N-1]。
假设您将多边形剖分为 N-2 个三角形。...对于每个三角形,该三角形的值是顶点标记的乘积,三角剖分的分数是进行三角剖分后所有 N-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 块,其中除了 这个三角形外,两外两块多边形仍然满足只有一条内边的性质,所以可以继续用二位状态表示为 和 。
那如果不先找三角形 会怎么样呢。如下图所示:
?