动态规划这张网里除了最长上升子序列、背包问题这些常客还有一类结构别致的问题——凸多边形最优三角剖分。我第一次见到这个题时觉得它像个几何题结果发现本质是一道非常纯粹的区间DP。如果你已经熟悉矩阵链乘法或者石子合并这题对你来说几乎是无缝衔接如果你刚接触动态规划想找一个“区间DP入门后必须练手”的经典模型它也特别合适。这篇博文我会把这题的思路从零拆到底包括状态定义、转移推导、代码实现、常见坑以及扩展方向尽量让我当年踩过坑的地方你一个都踩不上。1. 问题拆解什么是凸多边形最优三角剖分1.1 从“多边形”到“三角形”的几何直觉先说结论凸多边形最优三角剖分要解决的问题是给定一个凸多边形如何用不相交的对角线把它切成若干个三角形使得所有三角形的某种“权值和”最小。为什么要切三角形因为三角形是最简单的多边形任何多边形都能被三角剖分覆盖而凸多边形又有个好性质任意两点之间的连线都在多边形内部。这就保证了我们不管怎么连接顶点只要连线不相交最终一定能得到合法的三角形集合不需要额外判断一条对角线是否会穿过多边形外部。凸性在这里是算法有效性的基石你换成凹多边形问题复杂度立刻就不一样了这个我后面单独讲。一个 n 个顶点的凸多边形做三角剖分最终一定会得到 n-2 个三角形并且需要 n-3 条互不相交的对角线。你可以画一个四边形试试四条边围一个四边形必须连一条对角线才能分成两个三角形三角形数量是 4-22对角线数量是 4-31。五边形则需要两条对角线、三个三角形。这个数量关系是固定的不管你怎么剖。那“最优”二字落在哪里关键在于你以什么标准衡量剖分的好坏。这正是权重函数要解决的问题。1.2 权重函数的引入剖分优劣怎么算动态规划解决的是“最优”问题“最优”必然依赖一个具体的代价衡量标准。在凸多边形最优三角剖分里每个剖分出来的三角形都会带一个权重总代价就是所有三角形权重之和我们要找的是使总代价最小的剖分方式。权重函数怎么定义最常见的题型有两种第一种三角形顶点权值乘积之和。给每个顶点一个实数权三角形的权就是三个顶点权值的乘积整个剖分的总代价是各三角形权值乘积的累加。第二种三角形周长或面积。每个三角形的权可以用该三角形的周长、面积等几何量表示目标是最小化所有三角形周长的总和或面积的总和。我当年练习的版本是第一种也就是顶点权值乘积形式因为它和矩阵链乘法问题简直是一个模子刻出来的。矩阵链乘法的代价是相邻矩阵相乘的乘法次数这里的代价是三个顶点权值相乘的结果。结构上都是“枚举中间分界点把一个大区间拆成两个小区间再加上一个合并代价”。只不过这里“合并”换成了“由分界点构成的三角形权重”。如果你拿到的是周长或面积版本思路完全一致只是把合并代价的公式换掉。所以不要被题目描述里的几何术语吓住剥开壳核心依旧是区间DP那一套。1.3 为什么这题能动态规划最优子结构的观察有人可能会问剖分方式那么多怎么保证枚举所有情况时不重不漏答案是利用最优子结构递归地定义大问题的最优解。考虑凸多边形的一个子多边形由连续的若干顶点构成比如从顶点 i 到顶点 j 这条连续序列围成的多边形。这个子多边形的任意一个三角剖分中必然存在一个三角形以边 (i, j) 为一边。这是关键观察。因为 (i, j) 是子多边形的最外层边最终剖分时它一定属于某个三角形而这个三角形的第三个顶点 k 必须在 i 和 j 之间也就是 i k j。一旦确定了三角形 (i, k, j)整个子多边形就被这个三角形分成了左右两个更小的子多边形一个是顶点 i 到 k 围成的区域另一个是 k 到 j 围成的区域。这两个子区域的剖分相互独立问题规模缩小了而且它们的结构还是同样的凸多边形子问题。这就是最优子结构大问题的最优解 三角形 (i, k, j) 的代价 左边子问题最优解 右边子问题最优解对所有可能的 k 取最小值。注意这里必须保证子问题之间不重叠、不遗漏。因为 k 是三角形 (i, j) 边上的第三个顶点而 k 的取值范围是 i1 到 j-1枚举所有 k 就枚举了所有“跨过边 (i, j) 的三角形”的可能性恰好与所有合法剖分一一对应。2. 动态规划设计思路状态、转移、边界2.1 状态定义dp[i][j] 到底代表什么我建议把这个题的状态定义成dp[i][j] 表示由连续顶点 i, i1, ..., j 组成的子多边形进行最优三角剖分的最小代价。这里“连续”两个字特别重要。凸多边形的顶点是一个环但我们可以先固定一条起始边按照一个方向比如顺时针给顶点编号那么在状态转移时只考虑编号递增的区间 [i, j] 就行。这个区间内的顶点在原多边形上是连续的它们围成的形状仍然是一个凸多边形不过不一定是完整的原多边形而是一个子多边形。有人会困惑为什么不用 dp[i][j] 表示“顶点 i 到顶点 j 之间的所有顶点”而要说“围成的多边形”你画一下就明白了。取编号 1 到 4 四个顶点它们围成四边形再取编号 1 到 3 三个顶点它们围成三角形。注意当 j - i 比较小时这个“子多边形”可能退化成一条边或一个点。这时候的代价是多少答案是 0。因为一条边或一个点不需要剖分或者说剖分不出任何三角形代价为 0。这个退化情况的处理是整个 DP 初始化环节里最容易被忽略的地方但恰恰也是边界条件正确的关键。我见过不少同学把 dp[i][i] 或 dp[i][i1] 设成“极大值”结果整个 DP 表全是错的。这一步理解了后面就是水到渠成。2.2 转移方程推导枚举三角形、划分子问题有了状态定义转移方程就呼之欲出了。对于区间 [i, j]其中 j - i 2至少三个顶点才可能形成三角形我们枚举第三个顶点 kk 的取值范围是 i1 到 j-1。状态转移为dp[i][j] min { dp[i][k] dp[k][j] w(i, k, j) }其中 w(i, k, j) 是由顶点 i、k、j 构成的三角形的权重。这个方程看起来很简单但我强烈建议你不要只是背它而是自己画图走一遍。拿五边形举例子编号 1 到 5。要算 dp[1][5]k 可以取 2、3、4。取 k3 时意思是三角形 (1,3,5) 把五边形分成了左边子多边形 (1,2,3) 和右边子多边形 (3,4,5)。这两个子多边形分别有 3 个顶点各自就是一个三角形剖分代价为 0所以 dp[1][5] 在这一种 k 选择下的代价就是 w(1,3,5)。如果你定义权重为顶点权值乘积那 w(1,3,5) v[1]*v[3]*v[5]。当多边形更大时左边和右边子问题不再退化为三角形就需要继续递归往下拆。整个过程很像给一个大区间找分割点然后把左右两个区间分别交给子问题处理。写代码时如果采用记忆化递归这个方程甚至能原封不动地翻译成函数如果采用迭代填表核心就是控制区间长度的循环。你还会发现这个方程和矩阵链乘法的经典转移几乎完全一样矩阵链乘法是 dp[i][j] min(dp[i][k] dp[k1][j] p[i-1]*p[k]*p[j])区别只在于 k 的范围和合并代价的取法。理解了这个对应关系你以后遇到类似的区间划分类题目都能很快找到状态设计的方向。2.3 边界情况与初始化细节初始化是这种区间 DP 题最容易翻车的地方我在这里翻过一次车之后每次都会刻意检查边界。先明确两点当区间内只有 1 个顶点时dp[i][i] 0当区间内只有 2 个顶点时dp[i][i1] 0。因为 1 个顶点不是多边形2 个顶点只是条线段它们都不需要三角剖分代价自然是 0。那如果区间长度大于等于 3 呢初始化时应该设置成什么这里要说一个常见误区。有些同学喜欢把所有 dp 值先初始化成 0然后转移时取 min结果发现答案总是 0因为 dp[i][k] 和 dp[k][j] 都是 0只要 w 是非负的取 min 也只会取到最小的那个三角形权重完全不是想要的答案。正确做法是先把长度大于等于 3 的区间初始化为无穷大也就是一个非常大的数比如 INF在代码里可以用 1e9 甚至更大。这样取 min 时才会被真正计算出的值覆盖。具体代码循环时通常先枚举区间长度 len从 2 开始到 n-1再枚举左端点 i计算右端点 j i len。如果 len 小于等于 1 就跳过因为那些区间答案是 0不需要转移。然后枚举 k更新 dp[i][j]。把这个顺序写对整个填表过程就会很顺。2.4 时间复杂度与空间复杂度分析这个问题的复杂度非常标准。状态数量是 O(n²)每个状态要枚举 kk 的数量也是 O(n)所以总时间复杂度是 O(n³)。空间复杂度则是 O(n²)因为你只需要一个二维 DP 表。n100 时100³ 是 100 万完全是小意思n1000 时10 亿次运算就比较有压力了不过如果权重计算很简单也能勉强压着时限跑。在实际竞赛或刷题场景中n 一般不超过 500O(n³) 足够用。如果是更大的规模可以考虑四边形不等式优化这个我放到后面扩展部分细说。这里顺便提一个细节如果你用记忆化搜索空间占用也是 O(n²) 的二维表但因为递归栈的存在常数会比迭代填表大n 大时可能会有爆栈风险。所以我个人建议训练时先用记忆化搜索理清思路实际提交或工程实现时再用迭代版本。3. 代码实现从伪代码到可运行程序3.1 记忆化递归版本写起来最不容易错我先写记忆化递归版本因为它的代码结构和转移方程一一对应最不容易出错特别适合第一次接触这个问题的人。def solve(v): n len(v) - 1 # 顶点编号从1到n dp [[-1] * (n 1) for _ in range(n 1)] def weight(i, k, j): return v[i] * v[k] * v[j] def dfs(i, j): # 少于三个顶点不需要剖分 if j - i 2: return 0 if dp[i][j] ! -1: return dp[i][j] res float(inf) for k in range(i 1, j): res min(res, dfs(i, k) dfs(k, j) weight(i, k, j)) dp[i][j] res return res return dfs(1, n)这里 dp 初始化为 -1 用来标记“还没计算过”因为代价非负-1 不会和合法答案混淆。递归终止条件是 j - i 2也就是区间内少于 3 个顶点时返回 0。记忆化递归的好处是你不用关心循环顺序只需要信任递归会自底向上地解决子问题。坏处是递归调用有一些常数开销而且 Python 的递归深度默认是 1000如果 n 很大比如超过 1000可能触发递归深度限制需要手动调大递归深度或者改用迭代版本。不过对于一般刷题场景n 在几百以内完全没问题。3.2 自底向上填表版本性能最优迭代填表版本是我实际最常用的。它按区间长度从小到大计算保证计算 dp[i][j] 时所有更短区间的值都已经算好了。def solve(v): n len(v) - 1 dp [[0] * (n 1) for _ in range(n 1)] # len是区间长度区间[1, n]长度为n-1 for length in range(2, n): # length j - i for i in range(1, n - length 1): j i length dp[i][j] float(inf) for k in range(i 1, j): cost dp[i][k] dp[k][j] v[i] * v[k] * v[j] if cost dp[i][j]: dp[i][j] cost return dp[1][n]这里 length 表示区间长度即 j - i。当 length 2 时区间内有 3 个顶点dp[i][i2] 就是三角形自身的权重当 length 逐渐增大子问题的解就已经在表里了。注意循环范围i 从 1 到 n - length确保 j i length 不超过 n。这段代码里有个细节为什么 length 从 2 开始因为 length0 或 1 时dp 值就是 0不需要进入转移计算。length2 时k 只有 i1 一个选择可以直接算出三角形权重。我建议你手动模拟一遍五边形的情况把 dp 表的填写过程写出来。这个过程能帮你彻底理解区间 DP 的填表顺序以后遇到类似的题都会有底气。3.3 如何输出具体的剖分方案回溯记录有些题不只要最优代价还要输出具体的剖分方案比如给你一个凸多边形要你输出每条切开的对角线。这时光有 dp 表不够还需要额外的决策数组来记录每个状态的最优分界点 k。思路和背包问题输出方案一模一样的套路在转移取最小值时如果发现新的 cost 更小就把当前的 k 记下来。存到 choice[i][j] 里。def solve_with_solution(v): n len(v) - 1 dp [[0] * (n 1) for _ in range(n 1)] choice [[0] * (n 1) for _ in range(n 1)] for length in range(2, n): for i in range(1, n - length 1): j i length dp[i][j] float(inf) for k in range(i 1, j): cost dp[i][k] dp[k][j] v[i] * v[k] * v[j] if cost dp[i][j]: dp[i][j] cost choice[i][j] k def trace(i, j): if j - i 2: return [] k choice[i][j] return [(i, k, j)] trace(i, k) trace(k, j) cuts trace(1, n) return dp[1][n], cutstrace 函数递归地输出每个三角形。以 (i, k, j) 为单位输出三角形的三个顶点或者只输出对角线 (i, k) 和 (k, j)取决于题目要求。如果题目要求输出对角线记得不要重复输出公共边需要根据需求过滤。这种“dp表 决策表”的组合几乎是所有区间DP输出方案题的通用解法我用过很多次值回票价。3.4 一个可以动手跑的完整示例为了让你有更直观的感受我构造一个完整的小例子。假设凸五边形的顶点 1 到 5 的权值分别为 [3, 4, 5, 2, 6]下标从 1 开始对应。权重函数是三角形三个顶点权值的乘积。用上面的迭代代码跑一遍。先算 length2 的三角形权重dp[1][3] 345 60dp[2][4] 452 40dp[3][5] 526 60。然后 length3比如 dp[1][4]k 可以取 2 和 3k2dp[1][2]0 dp[2][4]40 34224 64k3dp[1][3]60 dp[3][4]0 35230 90所以 dp[1][4] 64最优决策点是 k2。同理算 dp[2][5]k30 60 456 180k440 0 426 88所以 dp[2][5] 88最优决策点是 k4。最后 dp[1][5]k 取 2、3、4k2dp[1][2]0 dp[2][5]88 34672 160k3dp[1][3]60 dp[3][5]60 35690 210k4dp[1][4]64 dp[4][5]0 32636 100所以最优总代价是 100决策点是 k4。对应的剖分是先取三角形 (1,4,5)然后左边子问题 (1,2,3,4) 再取三角形 (1,2,4)整个剖分是三角形 (1,2,4) 和 (1,4,5)。两个三角形刚好把五边形剖完。这个例子我建议你动手验一遍把每一步 dp 值都自己算出来接下来理解转移方程和填表顺序会通透很多。很多同学看公式觉得懂了一上手就懵本质上是缺少这种手动模拟的积累。4. 常见问题与排查技巧实录4.1 顶点序号是顺时针还是逆时针有影响吗这个问题很多初学者都会纠结顶点编号方向不同结果会变吗答案是完全不影响。凸多边形最优三角剖分关注的是顶点之间的相对拓扑关系只要顶点编号按顺序统一顺时针或统一逆时针排列顶点之间的邻接关系就确定了DP 结果只跟权值有关不跟几何方向有关。换句话说你把顶点编号整体旋转一个起点甚至反过来编号只要对应关系一致最优剖分的结构是等价的。如果题目给出了顶点坐标而权重是顶点坐标相关的几何量比如三角形面积或边长那确实跟坐标有关但编号方向仍然不影响最优性只是具体坐标值参与计算而已。4.2 权重函数怎么写才符合题意权重函数是整个题目最活的地方。我见过不少变体题权重不是简单的顶点乘积而是根据顶点坐标算三角形面积或者根据三角形边长算周长甚至是给定的一个权值矩阵 w[i][j]表示边 (i, j) 的代价。拿三角形面积举例面积为 s(i,k,j)转移方程就变成 dp[i][j] min(dp[i][k] dp[k][j] s(i,k,j))。这里有一个容易踩的坑面积需要用叉积计算公式是 0.5 * |(x_k - x_i)(y_j - y_i) - (x_j - x_i)(y_k - y_i)|而且要注意绝对值。如果你忘了取绝对值负面积会把 dp 值拉低最终答案就是错的。如果权重函数是边权矩阵 w[i][j]那三角形的权重可能就是 w[i][k] w[k][j] w[j][i]具体要看题目怎么定义。我的经验是每次做题先花一分钟把权重函数写成明确的数学公式再开始写代码省得在转移方程里纠结半天。4.3 凸多边形 vs 非凸多边形的区别题目特意强调“凸多边形”不是没有原因的。凸多边形里任意两顶点连线都在多边形内部所以不需要检查对角线合法性而凹多边形中某些对角线会穿过外部区域或者剖分后会产生非法三角形问题会复杂很多。如果给你一个普通简单多边形要做最优三角剖分通常需要先做耳朵裁剪ear clipping之类的预处理或者用更复杂的动态规划加入对角线可见性判断。那种题就不是这个 O(n³) 的经典模板能直接搞定的。所以做题时先看题干的“凸”字它有就放心套区间 DP没有的话先确认是不是有特殊的限制条件比如顶点都按极角排序且保证多边形是凸的。没有凸性保证的三角剖分是另一个层次的问题。4.4 大数溢出与初始化问题如果顶点权值很大比如权值范围到 1e9那么三个权值相乘就达到 1e27远超 32 位整数的范围甚至超过 64 位整数的上限9e18。这种情况下必须用 Python 的任意精度整数或者 C 里用 __int128 甚至高精度或者改用 double 类型注意精度损失。还有前面提过的初始化问题我再强调一次只有长度小于 2 的区间初始化为 0长度大于等于 3 的区间必须铺一个很大的 INF 值。如果你偷懒把所有 dp 都初始化为 0那 dp[i][j] 永远不会被更大的值覆盖最后答案全是 0。这个坑我当年在水题时踩过一次排查了半小时才发现是初始化的问题。另外如果题目要求答案可能很大通常会在描述里提醒“答案对 1e97 取模”这时权重计算过程也要边乘边取模或者用一个大整数类型先算出结果再取模。取模版本里 INF 的取值要小心不能直接设成 int 的最大值否则取 min 时会出问题。5. 扩展从理论到更广的应用场景5.1 和矩阵链乘法、石子合并的关系如果你刷题够多会发现最优三角剖分、矩阵链乘法、石子合并这三类问题是区间 DP 的“三件套”。它们的共性都是把一个大区间拆成两个小区间再加一个合并代价。矩阵链乘法的状态转移是 dp[i][j] min(dp[i][k] dp[k1][j] p[i-1]*p[k]*p[j])石子合并是 dp[i][j] min(dp[i][k] dp[k1][j] sum[i][j])而三角剖分是 dp[i][j] min(dp[i][k] dp[k][j] w(i,k,j))。区别只在于拆分方式矩阵链和石子合并是“分成两个独立区间”三角剖分也是分两个区间但两个区间共享分界点 k这个细微差异对 k 的边界范围和下标控制有影响。我个人的学习建议是把这三个题放在一起做互相比较状态方程、循环顺序和边界条件。你会发现它们的代码框架几乎可以通用只需要改一改合并代价的计算函数。5.2 四边形不等式优化当权重函数满足四边形不等式时最优决策点具有单调性也就是 dp 转移中的最优 k 会随着区间右端点增加而向右移动。可以利用这一点优化在枚举 k 时不需要遍历 i1 到 j-1只需要遍历一个更窄的范围 [opt[i][j-1], opt[i1][j]]这样总复杂度可以从 O(n³) 降到 O(n²)。不过要注意这个优化不是所有权重函数都适用需要用四边形不等式去验证。如果权重函数是顶点权值乘积的形式我并不建议盲目套用优化很多时候需要先通过数学验证才能放心用。做题时先写 O(n³) 的朴素版本确认正确性之后再根据规模决定是否加优化这才是稳妥的节奏。5.3 实际场景中的三角剖分抛开刷题最优三角剖分在真实工程里到处都有影子。三维建模软件需要把多边形网格化为三角形网格这是 GPU 渲染的基础有限元计算中复杂几何区域先剖分成三角形单元才能做数值计算路径规划里的凸包处理、图像处理中的多边形裁剪也会用到类似思路。在这些场景里权重函数经常是三角形面积、边长之和的最小化目标是让剖分结果更均匀、更利于后续处理。比如做三维模型三角化时希望生成的三角形尽量接近等边三角形避免过于狭长的三角形导致渲染和计算出现不稳定。这时候你用的仍然是最优三角剖分的算法框架只是权重函数变成了“三角形质量”相关的指标。如果你感兴趣可以去搜一下 Delaunay 三角剖分它在很多情况下被用来生成质量较高的三角网格思路也和“最优”有关不过是另一种优化目标。了解之后你会发现课本上的动态规划题和真实的图形学工程问题直接接轨的地方比你想象的要多得多。5.4 记忆化递归与迭代填表的选型心法我个人会按这个标准选型思路不熟时用记忆化递归写完就能验证思路清晰但性能敏感时用迭代填表如果是 ACM 或者竞赛环境迭代填表往往是标准答案。记忆化递归还有一个好处就是它天然只计算需要的状态而迭代填表会计算所有状态如果某些区间因为权重函数的限制其实用不到递归能省一点常数但这个优化在 O(n³) 面前意义不大。另外递归版本在 Python 里有一个必须注意的问题递归深度限制。如果 n 到 500 以上递归调用深度最多也是 500 层默认 1000 的限制是够的但如果你用递归函数同时进行大量局部变量赋值栈帧可能变大极端情况下还是会栈溢出。稳妥做法是用 sys.setrecursionlimit 调高限制或者干脆用迭代版本。迭代版本还有一个很多人都忽略的细节循环里计算 v[i] * v[k] * v[j] 时如果每个顶点权值访问很频繁可以提前把 v 转成局部变量列表或者直接用索引访问避免在多重循环里重复做属性查找。这个优化在 Python 里能明显减少运行时间我实测过n500 时速度差个 20% 到 30% 是有的。我做这个题时最大的体会是不要被“凸多边形”“三角剖分”这些几何名词唬住。只看状态定义和转移方程它就是一个非常标准的区间 DP。你真正要训练的是把问题描述翻译成状态的能力。先把小规模例子手算清楚再动手写代码最后再用题目数据自测这一套流程走下来同类题基本都能拿下。最后再分享一个我在输出剖分方案时常用的小技巧如果题目只要求输出最优代价不要求具体方案就别开 choice 数组了省点空间也少写点代码。如果要求输出方案不要等到最后再用某个变量临时存三角形而是老老实实开二维决策表最后递归回溯这样代码结构最清晰也最容易调试。我在早期贪图省事直接用全局列表在更新 dp 时乱 append结果回溯时顺序全乱了排查起来比多写一个数组痛苦得多。
