题目简介

1039. 多边形三角剖分的最低得分

难度：中等

给定 N，想象一个凸 N 边多边形，其顶点按顺时针顺序依次标记为 A[0], A[i], ..., A[N-1]。

假设您将多边形剖分为 N-2 个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有 N-2 个三角形的值之和。

返回多边形进行三角剖分后可以得到的最低分。

示例1：

1
2
3
输入：[1,2,3]
输出：6
解释：多边形已经三角化，唯一三角形的分数为 6。

示例2：

1.png

1
2
3
输入：[3,7,4,5]
输出：144
解释：有两种三角剖分，可能得分分别为：3*7*5 + 4*5*7 = 245，或 3*4*5 + 3*4*7 = 144。最低分数为 144。

示例3：

1
2
3
输入：[1,3,1,4,1,5]
输出：13
解释：最低分数三角剖分的得分情况为 1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13。

解法

时间与内存双百：

2.png

核心的动态规划推导式：dp[i][j]= dp[i][k] + dp[k][j] + values[i] * values[k] * values[j]。

其中k为介于i到j之间的数。

以六边形为例，先初始化一个6*6的dp矩阵，初始值为0。

dp[i][j]代表在第i个顶点和第j个顶点之间最小的总和。

首先，对于i < j-2以及j > n-3的情况（即下图中的空白格子）是没有意义的，不需要处理。

对于i == j-2的情况（即下图中内有三角形的格子），其本身就是一个三角形，直接按照values[i] * values[i+1] * values[i+2]计算即可。

对于其他情况，使用推导式dp[i][k] + dp[k][j] + values[i] * values[k] * values[j]，其中k为介于i到j之间的数。将多边形i到j分割为一个三角形ijk和两个小多边形。两个小多边形再继续分割求解。最终此格内的值为所有k情况的最小值。即dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + values[i] * values[k] * values[j])。此处由于Go语言切片初始化值为0，无法直接使用上式，故引入一个极大数作为临时值，求解完后再赋值给dp[i][j]。由于求解时需要使用下方格子以及左方格子的值（如下图中黑色和褐色箭头所示），我们需要i逆向j正向依次进行计算。

3.png

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
func minScoreTriangulation(values []int) int {
    n := len(values)
    dp := make([][]int, n, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, n, n)
	}
    for i := n-3; i >= 0; i-- {
        for j := i+2; j < n; j++ {
            if j - i == 2 {
                dp[i][j] = values[i] * values[i+1] * values[i+2]
            } else {
                temp := 2000000000
                for k := i+1; k < j; k++ {
                    temp = min(temp, dp[i][k] + dp[k][j] + values[i] * values[k] * values[j])
                }
                dp[i][j] = temp
            }
        }
    }
    return dp[0][n-1]
}

func min(i, j int) int {
    if i <= j {
        return i
    } else {
        return j
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def minScoreTriangulation(self, values: List[int]) -> int:
        n = len(values)
        dp = [[float('inf') for _ in range(n)] for _ in range(n)]

        for i in range(n-1):
            dp[i][i+1] = 0

        for d in range(2, n):
            for i in range(0, n - d):
                j = i + d
                for k in range(i+1, j):
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + values[i] * values[k] * values[j])
                    
        return dp[0][n - 1]