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

发表于 分类于 阅读次数： Waline： 本文字数： 1.1k 阅读时长 ≈ 4 分钟

考点

  • 区间DP

思路

一、问题描述

给定一个凸多边形，其顶点按顺序编号为 \[ 0, 1, 2, \dots, n-1 \] 第 \(i\) 个顶点有权值 \(values[i]\)。

需要将该多边形划分为若干个不相交的三角形（即三角剖分）， 每个三角形 \((i,j,k)\) 的代价定义为： \[ values[i] \cdot values[j] \cdot values[k] \] 目标是：最小化所有三角形代价之和。

二、问题建模：区间 DP 的视角

2.1 几何结构到区间结构的转化

由于多边形是凸的，且顶点按照顺序给出， 任意一条合法的对角线都会把多边形划分为两个更小的凸多边形。

因此，可以将问题转化为：

对一个由连续顶点区间构成的子多边形，求其最小三角剖分代价。

2.2 状态定义

定义二维动态规划数组： \[ f[i][j] = \text{由顶点 } i, i+1, \dots, j \text{ 构成的子多边形的最小三角剖分代价} \] 这里需要注意：

  • 当 \(j \le i+1\) 时，顶点数不足 3，无法构成三角形： \[ f[i][j] = 0 \]

  • 当 \(j \ge i+2\) 时，该区间对应一个合法的子多边形。

三、核心思想：枚举“最后一个三角形”

3.1 最后一步法（Last Step Principle）

设想已经得到了区间 \([i,j]\) 的一个最优三角剖分方案。

在这个方案中，必然存在一个最后被确定的三角形， 该三角形一定满足：

  • 使用边 \((i,j)\) 作为其中一条边；

  • 第三个顶点为某个 \(k\)，满足： \[ i < k < j \]

即最后一个三角形为： \[ (i, k, j) \]

3.2 子问题的独立性

当三角形 \((i,k,j)\) 被确定后：

  • 左侧剩余部分：顶点区间 \([i,k]\)
  • 右侧剩余部分：顶点区间 \([k,j]\)

这两个子多边形：

  • 顶点集合互不交叉；
  • 三角剖分方式互不影响；

因此可以独立求最优解。

四、状态转移方程

根据上述分析，状态转移方程可写为： \[ f[i][j] = \min_{\, i < k < j \,} \Big( f[i][k] + f[k][j] + values[i] \cdot values[k] \cdot values[j] \Big) \] 含义解释：

  • \(f[i][k]\)：左侧子多边形的最小代价；
  • \(f[k][j]\)：右侧子多边形的最小代价；
  • \(values[i] \cdot values[k] \cdot values[j]\)：最后一个三角形的代价。

五、动态规划顺序

为了保证转移时子问题已经计算完成，需要：

  • 按区间长度从小到大进行枚举；
  • 区间长度至少为 3 才能形成三角形。

遍历顺序如下：

  1. 枚举区间长度 len = 3 ... n
  2. 枚举右端点 j
  3. 计算左端点 i = j - len + 1
  4. 枚举分割点 k

六、算法复杂度分析

  • 状态数：\(O(n^2)\)
  • 每个状态枚举 \(k\)：\(O(n)\)

总时间复杂度： \[ O(n^3) \] 空间复杂度： \[ O(n^2) \] 在 \(n \le 50\) 的限制下完全可行。

七、AC代码

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
35
36
37
class Solution {
public:
    int minScoreTriangulation(vector<int>& values) {
        int n = values.size();

        // f[i][j] 表示由顶点 i..j 构成的子多边形的最小三角剖分代价
        int f[55][55] = {};

        // 枚举区间长度，至少为 3 才能形成三角形
        for (int len = 3; len <= n; ++len) {
            // 枚举区间右端点 j
            for (int j = len - 1; j <= n - 1; ++j) {
                // 计算左端点 i
                int i = j - len + 1;

                // 初始化为一个极大值
                int mi = INT_MAX >> 1;

                // 枚举最后一个三角形的第三个顶点 k
                // 三角形为 (i, k, j)
                for (int k = j - 1; k > i; --k) {
                    mi = min(
                        mi,
                        f[i][k] + f[k][j] +
                        values[i] * values[j] * values[k]
                    );
                }

                // 得到区间 [i, j] 的最优解
                f[i][j] = mi;
            }
        }

        // 整个多边形的最小三角剖分代价
        return f[0][n - 1];
    }
};

八、总结

  • 本题是经典的区间 DP + 最后一步法模型；
  • 核心在于：
    • 将凸多边形问题转化为连续区间子多边形问题；
    • 枚举“最后一个三角形”作为分治切入点；
  • 状态转移方程结构与：
    • 切棍子（Minimum Cost to Cut a Stick）
    • 区间合并类问题
    • 多边形最优剖分 完全一致。

一旦建立了“最后一步 + 子问题独立”的视角， 该类区间 DP 问题几乎可以模板化处理。