时间轴

2025-09-29

init

题目：

P1039 多边形三角剖分的最低得分

https://leetcode.cn/problems/minimum-score-triangulation-of-polygon/description/?envType=daily-question&envId=2025-09-29

该题显然存在子问题，可以向动态规划考虑。假定从 i 到 k 区间的顶点，k 处于 i 到 k 之间但不等于 i 或 k,那么该问题等于 i 到 k 的多变形最小剖分分数+k 到 j 的多边形最小剖分分数+i,j,k 组成的多边形面积，因为不论怎么划分，i 和 j 必定要和其区间的一个顶点组成一个三角形。由此可列出状态转移方程：

dp[i][j]=min(dp[i][k]+dp[k][j]+values[i]∗values[j]∗values[k])dp[i][j] =min( dp[i][k] + dp[k][j] + values[i] *values[j] *values[k])

dp[i][j] 表示第 i 个顶点到第 j 个顶点的凸多边形的最小三角形剖分分数，k 为 i~j 内任意一个顶点不包括 i 和 j

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
30
31
32
33
34
#include <climits>
#include <vector>
using std::vector;

class Solution {
    public:
        // dp[i][j] 第i个顶点到第j个顶点的凸多边形的最小三角形剖分分数
        // k为i~j内任意一个顶点不包括i和j
        // dp[i][j] =min k{ dp[i][k] + dp[k][j]+ values[i] *values[j] *values[k]}
        int minScoreTriangulation(vector<int> &values)
        {
                int vertex; // i~j共有多少个顶点
                int i, j, k;
                int n;

                n = values.size();

                vector<vector<int> > dp(n, vector<int>(n, 0));

                for (vertex = 2; vertex < n; vertex++) {
                        for (i = 0; i + vertex < n; i++) {
                                j = i + vertex;
                                dp[i][j] = INT_MAX;
                                for (k = i + 1; k < j; k++) {
                                        dp[i][j] =
                                                std::min(dp[i][j],
                                                         dp[i][k] + dp[k][j] +
                                                                 values[i] * values[j] * values[k]);
                                }
                        }
                }
                return dp[0][n - 1];
        }
};