时间轴

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] 表示第 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
#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];
  }
};