动态规划这张网里，除了最长上升子序列、背包问题这些常客，还有一类结构别致的问题——凸多边形最优三角剖分。我第一次见到这个题时，觉得它像个几何题，结果发现本质是一道非常纯粹的区间DP。如果你已经熟悉矩阵链乘法或者石子合并，这题对你来说几乎是无缝衔接；如果你刚接触动态规划，想找一个“区间DP入门后必须练手”的经典模型，它也特别合适。这篇博文我会把这题的思路从零拆到底，包括状态定义、转移推导、代码实现、常见坑以及扩展方向，尽量让我当年踩过坑的地方，你一个都踩不上。
1. 问题拆解：什么是凸多边形最优三角剖分
1.1 从“多边形”到“三角形”的几何直觉
先说结论：凸多边形最优三角剖分要解决的问题是，给定一个凸多边形，如何用不相交的对角线把它切成若干个三角形，使得所有三角形的某种“权值和”最小。
为什么要切三角形？因为三角形是最简单的多边形，任何多边形都能被三角剖分覆盖，而凸多边形又有个好性质：任意两点之间的连线都在多边形内部。这就保证了我们不管怎么连接顶点，只要连线不相交，最终一定能得到合法的三角形集合，不需要额外判断一条对角线是否会穿过多边形外部。凸性在这里是算法有效性的基石，你换成凹多边形，问题复杂度立刻就不一样了，这个我后面单独讲。
一个 n 个顶点的凸多边形做三角剖分，最终一定会得到 n-2 个三角形，并且需要 n-3 条互不相交的对角线。你可以画一个四边形试试：四条边围一个四边形，必须连一条对角线才能分成两个三角形，三角形数量是 4-2=2，对角线数量是 4-3=1。五边形则需要两条对角线、三个三角形。这个数量关系是固定的，不管你怎么剖。
那“最优”二字落在哪里？关键在于你以什么标准衡量剖分的好坏。这正是权重函数要解决的问题。
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 的取值范围是 i+1 到 j-1，枚举所有 k 就枚举了所有“跨过边 (i, j) 的三角形”的可能性，恰好与所有合法剖分一一对应。
2. 动态规划设计思路：状态、转移、边界
2.1 状态定义：dp[i][j] 到底代表什么
我建议把这个题的状态定义成：dp[i][j] 表示由连续顶点 i, i+1, ..., j 组成的子多边形进行最优三角剖分的最小代价。
这里“连续”两个字特别重要。凸多边形的顶点是一个环，但我们可以先固定一条起始边，按照一个方向（比如顺时针）给顶点编号，那么在状态转移时只考虑编号递增的区间 [i, j] 就行。这个区间内的顶点在原多边形上是连续的，它们围成的形状仍然是一个凸多边形，不过不一定是完整的原多边形，而是一个子多边形。
有人会困惑：为什么不用 dp[i][j] 表示“顶点 i 到顶点 j 之间的所有顶点”而要说“围成的多边形”？你画一下就明白了。取编号 1 到 4 四个顶点，它们围成四边形；再取编号 1 到 3 三个顶点，它们围成三角形。注意，当 j - i 比较小时，这个“子多边形”可能退化成一条边或一个点。这时候的代价是多少？答案是 0。因为一条边或一个点不需要剖分，或者说剖分不出任何三角形，代价为 0。
这个退化情况的处理是整个 DP 初始化环节里最容易被忽略的地方，但恰恰也是边界条件正确的关键。我见过不少同学把 dp[i][i] 或 dp[i][i+1] 设成“极大值”，结果整个 DP 表全是错的。这一步理解了，后面就是水到渠成。
2.2 转移方程推导：枚举三角形、划分子问题
有了状态定义，转移方程就呼之欲出了。对于区间 [i, j]，其中 j - i >= 2（至少三个顶点才可能形成三角形），我们枚举第三个顶点 k，k 的取值范围是 i+1 到 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。取 k=3 时，意思是三角形 (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[k+1][j] + p[i-1]*p[k]*p[j])，区别只在于 k 的范围和合并代价的取法。理解了这个对应关系，你以后遇到类似的区间划分类题目，都能很快找到状态设计的方向。
2.3 边界情况与初始化细节
初始化是这种区间 DP 题最容易翻车的地方，我在这里翻过一次车之后，每次都会刻意检查边界。
先明确两点：当区间内只有 1 个顶点时，dp[i][i] = 0；当区间内只有 2 个顶点时，dp[i][i+1] = 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²)，每个状态要枚举 k，k 的数量也是 O(n)，所以总时间复杂度是 O(n³)。空间复杂度则是 O(n²)，因为你只需要一个二维 DP 表。
n=100 时，100³ 是 100 万，完全是小意思；n=1000 时，10 亿次运算就比较有压力了，不过如果权重计算很简单，也能勉强压着时限跑。在实际竞赛或刷题场景中，n 一般不超过 500，O(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][i+2] 就是三角形自身的权重；当 length 逐渐增大，子问题的解就已经在表里了。注意循环范围：i 从 1 到 n - length，确保 j = i + length 不超过 n。
这段代码里有个细节：为什么 length 从 2 开始？因为 length=0 或 1 时，dp 值就是 0，不需要进入转移计算。length=2 时，k 只有 i+1 一个选择，可以直接算出三角形权重。
我建议你手动模拟一遍五边形的情况，把 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 开始对应）。权重函数是三角形三个顶点权值的乘积。
用上面的迭代代码跑一遍。先算 length=2 的三角形权重：dp[1][3] = 345 = 60；dp[2][4] = 452 = 40；dp[3][5] = 526 = 60。然后 length=3，比如 dp[1][4]，k 可以取 2 和 3：
- k=2：dp[1][2]（0）+ dp[2][4]（40）+ 342（24）= 64
- k=3：dp[1][3]（60）+ dp[3][4]（0）+ 352（30）= 90
所以 dp[1][4] = 64，最优决策点是 k=2。同理算 dp[2][5]：
- k=3：0 + 60 + 456 = 180
- k=4：40 + 0 + 426 = 88
所以 dp[2][5] = 88，最优决策点是 k=4。
最后 dp[1][5]，k 取 2、3、4：
- k=2：dp[1][2]（0）+ dp[2][5]（88）+ 346（72）= 160
- k=3：dp[1][3]（60）+ dp[3][5]（60）+ 356（90）= 210
- k=4：dp[1][4]（64）+ dp[4][5]（0）+ 326（36）= 100
所以最优总代价是 100，决策点是 k=4。对应的剖分是先取三角形 (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。这个坑我当年在水题时踩过一次，排查了半小时才发现是初始化的问题。
另外，如果题目要求答案可能很大，通常会在描述里提醒“答案对 1e9+7 取模”，这时权重计算过程也要边乘边取模，或者用一个大整数类型先算出结果再取模。取模版本里 INF 的取值要小心，不能直接设成 int 的最大值，否则取 min 时会出问题。
5. 扩展：从理论到更广的应用场景
5.1 和矩阵链乘法、石子合并的关系
如果你刷题够多，会发现最优三角剖分、矩阵链乘法、石子合并这三类问题是区间 DP 的“三件套”。它们的共性都是：把一个大区间拆成两个小区间，再加一个合并代价。
矩阵链乘法的状态转移是 dp[i][j] = min(dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j])，石子合并是 dp[i][j] = min(dp[i][k] + dp[k+1][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 时，不需要遍历 i+1 到 j-1，只需要遍历一个更窄的范围 [opt[i][j-1], opt[i+1][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 里能明显减少运行时间，我实测过，n=500 时速度差个 20% 到 30% 是有的。
我做这个题时最大的体会是：不要被“凸多边形”“三角剖分”这些几何名词唬住。只看状态定义和转移方程，它就是一个非常标准的区间 DP。你真正要训练的，是把问题描述翻译成状态的能力。先把小规模例子手算清楚，再动手写代码，最后再用题目数据自测，这一套流程走下来，同类题基本都能拿下。
最后再分享一个我在输出剖分方案时常用的小技巧：如果题目只要求输出最优代价，不要求具体方案，就别开 choice 数组了，省点空间也少写点代码。如果要求输出方案，不要等到最后再用某个变量临时存三角形，而是老老实实开二维决策表，最后递归回溯，这样代码结构最清晰，也最容易调试。我在早期贪图省事，直接用全局列表在更新 dp 时乱 append，结果回溯时顺序全乱了，排查起来比多写一个数组痛苦得多。
