LeetCode 1039 这道题我一直觉得是区间 DP 的教科书级入门题目本身长得像计算几何解法却干净利落地落在递归和状态转移上。题面讲的是给一个凸多边形的顶点值数组 values用不相交的对角线把多边形切成若干个三角形每个三角形得分是三个顶点值的乘积求所有三角形得分总和的最小值。如果你最近在刷递归专题大概率会碰上它因为它还有一种更直白的学习姿势不用先想循环怎么写直接写递归函数让记忆化帮你把重复子问题吃掉。我是在刷题第 166 天遇到它的。当时刚整理完递归的常见套路看到多边形三角剖分这个包装第一反应是几何题结果把状态图画出来以后发现这不就是典型的区间 DP 吗递归公式短到让人怀疑人生但边界和循环顺序的坑又足够让初学者摔几个跟头。今天就借这道题把我从看懂题解到能独立 AC的全过程拆开讲包含记忆化搜索、迭代 DP 两种写法还有一些面试里可能追问的变形思路。1. 把几何题翻译成状态先别急着写代码1.1 这道题到底在干什么先要把题目中凸多边形这个词看清楚。凸意味着什么任意两个顶点之间的连线一定在多边形内部你切出来的每一条对角线都不会跑到外面去也不会和别的边相交。这个性质是后面所有 DP 的前提。如果是一个凹多边形两个不相邻顶点之间的连线可能有一部分在外部那三角剖分的定义就要换个标准复杂度完全不一样。所以碰到这种题第一步不是着急推公式而是先确认输入给的是凸多边形。举例 values [3, 7, 4, 5]四个顶点其实就是一个四边形。四边形只有两条对角线可选选择连接顶点 0 和顶点 2会得到三角形 (0,1,2) 和 (0,2,3)分数是 3×7×4 3×4×5 84 60 144。选择连接顶点 1 和顶点 3会得到三角形 (0,1,3) 和 (1,2,3)分数是 3×7×5 7×4×5 105 140 245。所以答案是 144。到这里你会发现n 4 时题目是简单的就是两条对角线比一比。n 变大以后三角形组合的数量非常多比如 n 6 时的剖分方案数已经超过两位数n 10 时增长得更夸张。想让程序处理这种组合爆炸就必须找到重叠子问题也就是 DP 的切入点。1.2 为什么凸多边形能当区间处理我第一眼看到这个题的时候想的是把多边形摊开成一个环然后在环上做 DP。实际上有一个更自然的视角固定一条边作为底边。任意取两个不相邻的顶点 i 和 j连接之后多边形被分成左右两个部分。其中一个部分由顶点 i, i1, ..., j 组成另一个部分由 j, j1, ..., i绕回组成。由于凸多边形的对称性和无自交性质这两个部分互相独立内部怎么切完全不影响外部。孤立地看其中一个部分你会发现它还是凸多边形只是顶点变少了。于是可以从原问题中剥离出一个子问题只用顶点 i 到 j 这一段连续顶点组成的子多边形求它的最小剖分分数。这就是区间的由来。这个抽象是关键把几何上的一部分区域映射成数组上的一段下标几何问题就变成了区间 DP。后面所有的 dp[i][j] 定义全都是从这句话里来的。1.3 状态定义dp[i][j] 代表从i到j这段子多边形所以状态定义写出来就是dp[i][j] 表示由顶点 i, i1, ..., j 围成的子多边形完成三角剖分后所有三角形分数之和的最小值。注意这里的围成并不需要额外的高精度坐标数组中用下标 i 到 j 这一段就代表了一个子多边形。为什么不需要顶点 j1因为底边本身就是 (i, j) 这条弦子多边形内部只有 i 到 j 之间的顶点。边界情况需要单独说明如果 j - i 2也就是这一段里面少于三个顶点那么它不能构成三角形dp[i][j] 0。如果 j - i 2这一段刚好三个点是一个三角形分数应该是 values[i] × values[i1] × values[j]。这个边界不是随便定的后面看递归公式就知道它其实是公式的自然结果。2. 递归转移的推导枚举中间顶点就是枚举切割线2.1 一个三角形的视角如果你已经知道 dp[i][j] 求的是区间内部的最小分数那么下一个问题是怎么从小区间推大区间我学的时候最直观的办法是——盯住三角形 (i, k, j)。这里 i 和 j 是当前区间两个端点k 是区间内部的任意一个顶点。为什么一定是包含底边 (i,j) 的三角形因为任何三角剖分都一定包含一条连接 i 和 j 的弦或者说底边而这条边一定属于某个唯一的三角形。这个三角形的第三个顶点只能是区间 (i, j) 中间的某个 k。三角形 (i, k, j) 一旦画出来它就把子多边形分成了三个区域左边的子多边形 i..k、右边的子多边形 k..j以及当前这个三角形本身。由于剖分不允许对角线相交左边和右边的剖分是彼此独立的互不干扰。于是就有了最关键的递归关系dp[i][j] min_{k ∈ (i1, ..., j-1)} ( dp[i][k] dp[k][j] values[i] × values[k] × values[j] )用大白话讲要算区间 i 到 j 的最小分数你只需要试着把中间每个可能的顶点 k 都拿来当第三个顶点组成三角形 (i, k, j)然后加上左右两个小区间各自的最小值取所有 k 中结果最小的那个。2.2 边界条件的自然推导如果你把边界 j - i 2 看成 dp[i][j] 0那当 j - i 2 时套公式k 只能取 i1于是 dp[i][j] dp[i][i1] dp[i1][j] values[i] × values[i1] × values[j]。dp[i][i1] 对应两个点不能构成三角形按边界给 0dp[i1][j] 同样给 0。最后只剩下乘积项正好就是三角形的分数。这说明什么说明你甚至可以不用单独处理 j - i 2 的情况代码里只要保证所有不足三个点的区间返回 0公式会自动把这个三角形算出来。这个特性在迭代写法里也一样只要初始化 dp 为全 0然后从区间长度 2 开始递推就不会算错。2.3 为什么贪心选最小值不成立刚看到这个公式很多人会想那直接把每个三角形里最小的那个顶点当第三个顶点不就行了选 k 使得 values[k] 最小每次切出分数最小的三角形最后总和说不定也最小。这个贪心是错的而且很容易构造反例。比如 values [1, 100, 1, 100, 1]。如果你在第一个三角形里选最中间的 1可能会把后面的大数全部塞在一个三角形里整体分数反而高反过来选一个暂时难看的 k却能把大数拆开抵消。原因在于三角形分数是三项相乘而不是两项相加你的选择不仅影响当前三角形的分数还决定左右两个子问题分别包含哪些顶点。区间 DP 的本质就是枚举所有可能的分割所以它天然能覆盖贪心看不到的全局解。3. 记忆化搜索实现递归代码与几个关键细节3.1 Python 用 lru_cache 的写法递归加记忆化我的首选写法是直接用 functools.lru_cache不用自己开二维数组做 memo代码短很多from functools import lru_cache from typing import List class Solution: def minScoreTriangulation(self, values: List[int]) - int: n len(values) lru_cache(None) def dfs(i: int, j: int) - int: if j - i 2: return 0 ans float(inf) for k in range(i 1, j): ans min(ans, dfs(i, k) dfs(k, j) values[i] * values[k] * values[j]) return ans return dfs(0, n - 1)整个代码的核心就三行判断边界、枚举 k、取最小值。lru_cache 会自动把每个 (i, j) 的结果缓存下来所以递归虽然从写法上看起来会重复计算很多子问题实际上每个区间只真正计算一次。如果不习惯用 lru_cache也可以自己维护一个 memo 二维数组初值设为 -1遇到 memo[i][j] 0 就直接返回。效果一样只是代码会多几行。3.2 递归参数与循环范围的细节这里有两个容易写错的地方。第一个是 k 的范围必须严格在 i 和 j 之间也就是 range(i 1, j)。如果你写成 range(i, j)k 等于 i 的时候dp[i][i] dp[i][j] values[i]^2 × values[j]这个状态本身还没算完会出现循环依赖而且多出来一个重复顶点语义完全不对。第二个是返回值的上界问题如果一段区间确实无法剖分少于三个顶点直接返回 0。如果忘了这个边界递归会无限往下走比如 dfs(i, i2) 里的 k 只有一个但 dfs(i, k) 如果继续枚举就可能卡在长度为 1 的区间里出不来。所以边界判断必须放在枚举之前。我在本地跑的时候还发现一个细节Python 的 lru_cache 默认能缓存足够多的状态这个题 n 最大到 50状态数是 O(n^2) ≈ 2500 个完全够用不需要手动清理缓存。3.3 复杂度分析为什么 O(n^3) 可以接受状态数有多少i 和 j 的组合数量是 O(n^2)。每个状态内部要枚举 kk 的数量平均是 O(n)所以总时间复杂度是 O(n^3)。对于 n ≤ 50 的题目来说最坏情况大约 12 万多次状态转移在 Python 里也只需要几毫秒到几十毫秒完全不用担心超时。空间复杂度是 O(n^2)lru_cache 内部会存所有 (i, j) 的结果二维存储。记忆化搜索最舒服的一点是你完全不用思考先算哪个长度再算哪个长度。递归天然从大区间向小区间走轮到哪个子问题如果没算过就算算过就直接返回。这种懒加载的思考方式非常适合在面试里快速写出正确解法。4. 改成迭代DP把递归拆栈顺带说说非递归思路4.1 自底向上的区间枚举记忆化写起来舒服但如果你想彻底掌握区间 DP最好再写一遍迭代版本。原因很简单很多区间 DP 题目的状态不是严格递归定义的或者递归深度太深容易爆栈这时候自底向上更稳妥。迭代版本的核心是先算长度短的区间再算长度长的区间。因为 dp[i][j] 依赖的 dp[i][k] 和 dp[k][j] 长度一定比 dp[i][j] 短所以只要按区间长度从小到大枚举就能保证依赖状态先被算出来。from typing import List class Solution: def minScoreTriangulation(self, values: List[int]) - int: n len(values) dp [[0] * n for _ in range(n)] for length in range(2, n): # length j - i for i in range(n - length): j i length dp[i][j] float(inf) for k in range(i 1, j): dp[i][j] min( dp[i][j], dp[i][k] dp[k][j] values[i] * values[k] * values[j] ) return dp[0][n - 1]length 从 2 开始是因为 length 为 0 和 1 的区间都是 0不需要参与递推。到 length 2 的时候k 只有一个左右两边刚好都是长度 1 的区间所以 dp 会自动得到三角形的乘积。4.2 先算小区间再算大区间你可能会有疑问dp 数组初始化是全 0但 dp[i][j] 在计算时如果取 min初始 0 会导致结果永远是 0怎么办答案看你把 dp[i][j] 的初始值设成什么。在上面的代码里我在每个状态开始计算前先赋成 float(inf)然后再做 min。这样第一个候选值会被正常接受。如果你偷懒不赋 inf初始 0 会导致所有 dp[i][j] 都变成 0这是迭代写法最常见的错误。另一个值得注意的点是 length 的取值上限。如果 length 从 2 到 n-1那么最后一个区间是 dp[0][n-1]正好覆盖整个数组。如果你写成 range(2, n1)i 的循环就要缩小范围否则 j 会越界。我一般固定用 length 表示 j - i这样最不容易搞混。4.3 快速排序非递归的类比不是所有递归都要真递归说到把递归改成非递归很容易联想到快速排序的非递归实现。快速排序的经典写法是递归分治但如果你担心栈溢出可以用一个显式栈来模拟递归过程每次压入待排序子区间循环处理。这和这里的区间 DP 思路在很多地方是相通的递归版本依赖调用栈记录还有哪些子问题没算完非递归版本把子问题显式维护起来。不过和快速排序非递归不同的是DP 的迭代版本不只是在模拟递归调用顺序它因为有了先短后长的顺序可以直接用二维数组代替调用栈反而比显式栈更简单。我把这两种思路放在一起的原因是想说递归、记忆化、自底向上 DP、显式栈本质上都是管理子问题的不同手段。遇到一道题你可以先从递归开始找思路然后根据情况选择实现方式。快速排序的非递归也是一样它并没有改变分治的实质只是换了种方式让代码不依赖系统栈。5. 亲手写一遍踩过的坑与对照检查5.1 边界条件必须自己先列出来LeetCode 这类题的隐藏用例总是喜欢在边界上卡人。对于 1039我建议提交前先自己检查这几条n 3 时只有一个三角形答案就是三个值的乘积。n 4 时只有两种剖分方式答案取两种方式中较小者。所有顶点值相同比如 [5,5,5,5,5]那么所有剖分方式分数都相同答案应该是 5×5×5×(n-2)。数组里有很大的数比如 [1, 10000, 1, 10000, 1]要确认你的结果类型不会溢出。Python int 不会溢出C 要小心用 long long。我自己刷的时候n 3 和全相同值这两个用例是最容易暴露问题的因为 n 3 时如果边界返回 0 判断写错会直接返回 0。5.2 为什么一定要用 float(inf) 而不是一个大数有人喜欢用 109 这种大数作为初始化值。这个题的 values[i] 最大是 100n 最大是 50最坏情况下一共不超过 50 个三角形每个三角形最大乘积是 10^6所以总分数上限大概是 5×10^7。初始化成 109 是安全的。但为什么我还是推荐 float(inf)因为写 float(inf) 你永远不需要去估算上界。如果某道题的 values 范围你记错了用大数初始化可能在某组数据下不够大导致 min 取到错误的初始化值。用 inf 就没有这个问题而且 Python 里 float(inf) 和 int 做比较完全正常。唯一的注意点是如果返回值要参与后续运算inf 不会留在最终答案里因为每个 dp[i][j] 只要区间长度 ≥ 2 就一定能枚举到至少一个 k一定会被真实分数替换掉。5.3 本地测试的完整脚本我刷题时习惯写一个本地脚本把主算法和几个手动算过的用例对照确认没问题再提交。可以写一个小的 main 函数跑几个用例if __name__ __main__: s Solution() print(s.minScoreTriangulation([3, 7, 4, 5])) # 144 print(s.minScoreTriangulation([1, 2, 3])) # 6 print(s.minScoreTriangulation([5, 5, 5, 5])) # 250 print(s.minScoreTriangulation([1, 100, 1, 100, 1])) # 200这四个用例分别覆盖四边形、三顶点、全相同值、贪心会出错的反例。如果你写的迭代版本输出 [3,7,4,5] 返回 0多半是没在计算前把 dp[i][j] 置为 inf如果全相同值和你手算不一致多半是 length 循环范围写错了。5.4 优化方向与记忆化函数签名如果追求极致速度可以把 values[i] 的乘积预计算或局部变量缓存。但 n 很小这些优化意义不大。我更想提醒的是模块化写法不要把所有逻辑塞在一个函数里尤其是面试的时候先把 dfs(i, j) 定义清楚再写主流程别人看起来也舒服。这个题的代码本来就短可读性比微优化重要得多。6. 变体题与面试扩展6.1 和 LeetCode 312 戳气球对比区间 DP 的经典题除了 1039最有名的就是 312 戳气球。312 的转移方程长得很像dp[i][j] 表示戳完 (i, j) 之间所有气球能得到的最大硬币数转移式是 dp[i][j] max(dp[i][k] dp[k][j] nums[i] × nums[k] × nums[j])。如果你把 1039 的 min 换成 max把 dp 含义从剖分分数换成戳气球收益两个题的代码结构基本一致。这种相似性不是巧合。它们都属于区间 DP核心是枚举区间内最后一个动作发生的位置 k。在 1039 里k 是包含底边的三角形的第三个顶点在 312 里k 是最后一个被戳破的气球。把这个最后动作想清楚区间 DP 题就成功了一大半。6.2 如果要求输出剖分方案LeetCode 1039 只输出最小值不要求方案。但面试官可能顺手问怎么把最小方案对应的三角形集合输出做法是在 dp 之外加一个二维数组 choice[i][j]记录让 dp[i][j] 取到最小值的那个 k。递推结束后从 (0, n-1) 开始递归输出先输出三角形 (i, choice[i][j], j)然后分别递归输出左右两个子区间。伪代码大概是choice [[-1] * n for _ in range(n)] # 在递推时同步记录 if dp[i][j] dp[i][k] dp[k][j] values[i] * values[k] * values[j]: dp[i][j] dp[i][k] dp[k][j] values[i] * values[k] * values[j] choice[i][j] k def print_triangles(i, j): if j - i 2: return k choice[i][j] print((i, k, j)) print_triangles(i, k) print_triangles(k, j)这个技巧在 312 和其他区间 DP 题里也能复用算是区间 DP 的标配变形。6.3 什么时候该用记忆化什么时候该用迭代我的经验是面试写题优先记忆化因为它最贴近递归思路不容易写错循环边界但是如果你想对 DP 理解更扎实至少要把迭代版本亲手写过一遍。竞赛或者追求性能的时候用迭代 数组避免函数调用和缓存开销。对于 n 到 50 级别的题目两者在常数上的差异可以忽略选自己能一次写对的版本就好。最后补一个我自己的小习惯遇到新的区间 DP先在草稿纸上把长度为 2、3、4 的区间各自用公式手算一遍确认和样例一致再往上写代码。这个步骤花不了两分钟但能帮你建立对边界条件的直觉避免在隐藏用例上栽跟头。