题目描述
给定 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
题解
一个凸 边多边形,不停切割下去,最终一定是能切割成 个三角形。那么按照什么顺序切割才能方便求解呢?
可以发现,一刀下去,两个多边形只有一条边是在内部,其他边都是连续的外围的边,如下图所示:
所以右边的多边形我们可以用 二维状态来表示。
那么继续切割下去,例如切割左边那块多边形,我们应该先把 这条边对应的三角形给找出来,那就是在 之间找到第三个点 ,如下图所示:
这样右边多边形就被划分为了 3 块,其中除了 这个三角形外,两外两块多边形仍然满足只有一条内边的性质,所以可以继续用二位状态表示为 和 。
那如果不先找三角形 会怎么样呢。如下图所示:
这样的话,多边形 就会出现两条内边,那么这种多边形就很难用简单的二维状态来表示了,程序中很难实现。
最后就能用二维动态规划来递归求解了。用 表示多边形 ,其中只有 是内边。设 表示多边形 切割后最小得分,那么只需要找到上面所说的切割点 就行了,转移方程为:
代码
c++
class Solution { public: static const int N = 55; int dp[N][N]; int minScoreTriangulation(vector<int>& A) { int n = A.size(); memset(dp, 0, sizeof dp); for (int len = 3; len <= n; ++len) { for (int i = 0; i < n; ++i) { int j = i + len - 1; int tmp = INT_MAX; for (int k = 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; } } return dp[0][n-1]; } };
python
class Solution: def minScoreTriangulation(self, A: List[int]) -> int: n = len(A) dp = [[0]*n for _ in range(n)] for l in range(3, n+1): for i in range(n): j = i + l - 1 tmp = 0x3f3f3f3f for k in range(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] = tmp return dp[0][n-1]