刷题刷到第166天碰到LeetCode-1039这道题。说实话第一眼看到多边形三角剖分六个字我是有点懵的但把题目拆开之后发现它其实是区间动态规划里非常经典的一个变体而且和递归的关系特别深——不管是递归记忆化的写法还是改成迭代式DP都值得好好捋一遍。这道题在很多大厂面试里会作为DP的进阶题出现适合正在刷动态规划、准备算法面试或者想系统理解递归与非递归关系的朋友。下面从题目本身开始一步一步拆。题目很短给定一个凸多边形每个顶点有一个数值把多边形三角剖分后每个三角形三个顶点数值相乘得到一个得分所有三角形得分加起来是总得分求所有剖分方案里总得分的最小值。这里有个前提凸多边形意味着任意一条对角线都在多边形内部所以剖分这件事不会出现弯弯绕绕的情况。我先把这道题的最优解思路讲清楚然后给两版代码一版是递归记忆化一版是迭代填表最后聊聊我在调试过程中踩过的坑尤其是非递归这个话题——最近讨论快速排序非递归的人很多这两件事放在一起看会有意外的收获。1. 先搞懂题目在说什么多边形、三角形和剖分得分1.1 题目翻译成人话把凸多边形想象成一块需要切开的披萨顶点就是披萨边缘上的点每个点标了一个数字。三角剖分的规则是每一刀都必须连接两个顶点切出来的每一块都必须是三角形最后整个披萨被切成若干三角形小块。每一块三角形的得分是三个顶点数字的乘积。比如三个顶点分别是3、7、4那这块的得分就是84。整道题要求的是所有切法里所有三角形得分总和的最小值。拿一个最简单的四边形举例顶点分别是[3, 7, 4, 5]。四边形只有两种剖分方式选对角线(0,2)得到三角形(0,1,2)的得分3×7×484加上三角形(0,2,3)的得分3×4×560总分144或者选对角线(1,3)得到三角形(0,1,3)的得分3×7×5105加上三角形(1,2,3)的得分7×4×5140总分245。所以答案是144。这个例子能直观说明一件事贪心在这里行不通。你不能说先找个三点乘积最小的三角形因为三角形之间是共享边的你选了某个三角形会直接影响旁边子多边形的形状和后续得分。局部最优拼不出全局最优必须把问题整体纳入考量。1.2 为什么递归是这道题的第一直觉来看剖分过程的一个关键性质任取一个三角形(i, k, j)其中i、k、j都是多边形的顶点如果它在最终的剖分方案里那么它会把这整个多边形切成三块三角形本身、顶点i到k之间的子多边形、顶点k到j之间的子多边形。关键在于三角形(i,k,j)一旦确定左右两块的剖分方案是完全独立的互不影响。这就是典型的子问题结构。如果我定义f(i, j)为从顶点i到顶点j这一块子多边形的最小得分那么选定了中间顶点k之后最小值就是f(i, k) f(k, j) values[i] * values[k] * values[j]然后枚举所有可能的k取最小值。这种自顶向下的递归思路几乎是题面直接翻译过来的。我第一次看题的时候脑子里冒出来的就是这个形式完全没想DP先写递归再说。当然纯递归直接写会超时因为不同剖分路径会反复计算同一块子区域。解决办法也很标准加一个缓存也就是记忆化。把已经算过的(i, j)记下来下次直接查表。这一步做完递归版和迭代版的底层状态数量是一样的都是O(n^2)个子问题。2. 递归加记忆化最接近思维的写法2.1 状态定义与转移方程先用一句话定义清楚f(i, j)它表示由顶点i、i1、...、j以及边(j, i)围成的子多边形的三角剖分最小得分。这里的边(j, i)不是原始多边形边上的连线而是从顶点j连回顶点i的那条对角线或者当i和j本来就是相邻顶点时它就是图形边缘的原始边。有了这个定义转移方程就很清晰f(i, j) min( f(i, k) f(k, j) values[i] * values[k] * values[j] )其中k从i1到j-1。为什么k严格在i和j之间因为k如果取端点三角形就退化成了边没有意义。这个枚举过程就是在问这一块子多边形最后切出来的那个三角形是哪三个顶点组成的确定之后剩下的交给更小的两块区域。边界条件也非常顺当j - i 2时这块只有一个三角形都无法构成实际上是一条边或者一个点得分定为0。你可以理解为一条退化多边形不产生任何得分。当j - i 2时i、i1、j正好构成一个三角形此时唯一的k就是i1转移方程自然算出values[i] * values[i1] * values[j]不需要额外特判。我见过很多人在这道题里单独写一个 if j - i 2: return values[i]*values[i1]*values[j] 的分支其实没必要让转移方程自己算就行结果一模一样代码还能少几行。2.2 代码实现与边界处理直接上Python的递归记忆化版本from functools import lru_cache class Solution: def minScoreTriangulation(self, values: List[int]) - int: n len(values) lru_cache(None) def dfs(i: int, j: int) - int: # 少于3个顶点无法构成三角形得分为0 if j - i 2: return 0 best float(inf) for k in range(i 1, j): best min( best, dfs(i, k) dfs(k, j) values[i] * values[k] * values[j] ) return best return dfs(0, n - 1)代码非常短短到有点不像一道LeetCode中等偏难的题。核心逻辑全在dfs函数里。lru_cache负责记忆化把(f(i, j))的结果缓存下来避免重复递归计算。有同学可能会问递归深度的问题。这道题递归最深的情况发生在每次k都取i1或者j-1导致区域只缩小一个顶点所以最大递归深度大约是O(n)。LeetCode上n最大50递归深度也就是50层左右完全在Python默认递归上限1000以下根本不用担心栈溢出。复杂度方面状态数是O(n^2)每个状态要枚举k单次枚举O(n)所以总时间复杂度是O(n^3)空间O(n^2)。对于n50来说这个复杂度小意思。实际上如果按组合数算程序内部所有枚举的(i, k, j)三元组恰好就是从n个顶点里任选3个的组合也就是C(50,3)19600次非常轻松。2.3 一个容易忽略的小优化这个优化其实不是性能上的而是思维上的递归的边界到底应该写几个分支。我第一次写的时候老老实实写了两个分支if j - i 2: return values[i] * values[i1] * values[j] if j - i 2: return 0写完之后发现第二个分支其实已经涵盖了第一个分支的情况因为当j - i 2时for循环里只有一个k i 1此时dfs(i, i1)和dfs(i1, i2)都返回0最后best就是三个值的乘积。所以第一个分支是多余的。把多余的判断删掉之后代码变得更统一而且理解上反而更接近本质一切靠转移方程说话边界只处理不足以构成三角形的情况。这个习惯在后面写迭代DP时也有帮助因为迭代版本的初始化和边界处理思路是同一个道理。3. 从递归到非递归别急着用栈先想清楚依赖3.1 快速排序非递归带来的启示最近看到很多人在讨论快速排序非递归的写法这个热词放在这道题下面特别有意思。经典的快速排序非递归做法是用一个显式的栈保存待处理的(l, r)区间把系统递归调用栈搬到我们自己的代码里stack [(0, n - 1)] while stack: l, r stack.pop() if l r: continue pivot partition(arr, l, r) stack.append((l, pivot - 1)) stack.append((pivot 1, r))这个思路没有问题但它本质上属于用显式栈模拟系统栈代码是从递归版直接翻译过来的计算顺序并没有变化。对于快排这种DFS性质很强、没有固定计算顺序要求的算法这种模拟是合理的。但如果你是单纯想把递归算法改成非递归先别急着写栈应该问自己一个问题递归调用隐式遵循的顺序到底是什么如果子问题之间存在明确的拓扑序比如先算小区域、再算大区域那么把计算顺序反过来从底向上填表才是更彻底、也更优雅的非递归化。多边形三角剖分正好就是这种情况。dfs(i, j)依赖的是更短的区间dfs(i, k)和dfs(k, j)所以只要保证枚举区间长度len从小到大的时候长度短的子区间一定先被计算完毕那么迭代填表自然就是合法的。这才是这道题最值得体会的地方。3.2 按区间长度填表的迭代DP迭代版本的实现可以直接照搬转移方程但遍历顺序要格外小心。最外层循环必须是区间长度从3到n第二层循环是起点i第三层循环枚举中间顶点k。写成代码是这样class Solution: def minScoreTriangulation(self, values: List[int]) - int: n len(values) # dp[i][j] 表示顶点 i 到 j 之间的子多边形最小得分 dp [[0] * n for _ in range(n)] # length 表示子多边形的顶点个数 for length in range(3, n 1): for i in range(n - length 1): j i length - 1 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]这里dp[i][j]初始化为0的语义是当i和j相邻时dp[i][i1] 0表示退化成一条边不构成多边形得分为0。当区间长度为3时比如dp[0][2]唯一的k1转移会算出values[0] * values[1] * values[2]因为dp[0][1]和dp[1][2]都是0。这就是为什么2.3里说递归版不需要特判长度为3迭代版天然也继承了这一点。外层为什么一定是长度而不是起点i因为dp[i][j]依赖的dp[i][k]中k j所以区间长度一定比当前长度小同理dp[k][j]的长度也小于当前长度。如果外层先枚举i内层再枚举j很可能在算dp[i][j]的时候dp[i][k]或dp[k][j]还没有被计算过拿到的就是默认值0整个答案就错了。这是区间DP最容易踩的坑后面第4章还会细说。3.3 两种实现对比把递归记忆化和迭代DP放在一起看它们共享同一个状态定义和同一个转移方程差别在于执行顺序和缓存方式。维度递归 记忆化迭代 DP按长度填表思维方式自顶向下直接翻译题面自底向上需要先规划遍历顺序代码量更短天然贴合转移方程略长但结构明确缓存方式lru_cache 字典哈希二维数组直接下标访问栈开销有递归栈但n50时无压力无额外栈开销推荐场景快速验证思路追求稳定可控、避免递归深度的场景实际刷题的时候我的习惯是先写递归记忆化版本跑通样例之后再改成迭代版本。因为递归版接近人类直觉不容易在写转移方程的时候搞错边界。迭代版则更接近生产环境的代码形态没有递归深度风险也方便在调试器里观察整个dp表的填充过程。4. 调试经验与常见坑4.1 初始化的问题迭代版里dp数组初始化为全0这在区间长度3之后会被转移覆盖所以看起来没什么问题。但如果你在算法题面试里手撕代码建议养成显式初始化的习惯在计算dp[i][j]之前先把它设为float(inf)再进入k的循环去取min。这样写的好处是逻辑更严谨避免依赖默认0值这种隐式约定万一面试官追问你可以把长度为2的区间是0分这个语义讲得更清楚。递归版同样有一个隐蔽初始化陷阱如果dfs里忘了给best赋float(inf)或者把best初始化为0那min运算就会永远返回0答案直接变成0。这题因为答案都是正整数所以很容易出现还以为代码很聪明结果全是0的尴尬情况。我在本地调试时第一次就跑出了这种错误排查了半天才发现是best初始值的问题。4.2 遍历顺序错误这是区间DP最大的坑。我见过不少人在迭代版里写成这样# 错误的遍历顺序示例 for i in range(n): for j in range(i 2, n): 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])这个写法在n4的时候可能碰巧还能得到正确结果因为dp区间长度很小依赖的子区间基本都被计算过了。但n一大就乱了。比如算dp[3][6]的时候它依赖dp[4][6]这个区间的起点4比3大很可能还没有被计算。所以判断遍历顺序是否正确有一个很实用的检查方法看转移方程里依赖的区间长度是不是都严格小于当前区间长度。如果是就按长度从小到大作为外层循环。这个判断方法对几乎所有的区间DP都成立不只是这一题。4.3 多边形的退化理解在做这道题之前很多人是先刷过矩阵链乘法Matrix Chain Multiplication的。两道题确实很像都是一样的区间DP框架。但有个关键区别值得单独说说。在矩阵链乘法里dp[i][j]表示第i个矩阵到第j个矩阵的最小乘法次数当j i时表示单个矩阵乘法次数是0在转移中一般用dp[i][k] dp[k1][j] p[i-1]*p[k]*p[j]这样的形式左右需要两个非空部分。而本题中dp[i][j]对应的是顶点i到j包的子多边形退化成一条边时得分为0转移枚举的k在(i1, j-1)之间左右两块各自可以退化成边所以公式里直接用dp[i][k]和dp[k][j]就可以了没有dp[k1]这种偏移。这两者的区别本质上是线性区间和环形区间带来的差异。矩阵链是线性拼接剖分问题是环形闭合理解了这个区别以后看任何区间DP题先判断它依赖的子区间边界是(i, k)还是(k1, j)就能少走很多弯路。还有一个小技巧我在纸上调试时特别喜欢用把多边形的顶点按顺序标成一个圆每算一个dp[i][j]就用笔把这个子多边形圈出来再看看枚举的k把这块分成了哪两个子多边形。一旦你在图上看到了k把i到j切成两段这个真实几何过程转移方程就永远不会记错。这个画图调试法在遇到复杂的区间DP时比打印dp表好用得多。5. 写在最后的实操体会这类剖分求最低/最高得分的题做得多了以后会形成肌肉记忆看到剖分两个字第一反应就是区间DP看到N不超过50这种约束立刻判断O(n^3)复杂度可行看到递归版跑通之后再顺手改成迭代版。这套流程我一直在用基本能覆盖90%的区间DP题目。具体到LeetCode-1039我个人还有一个很深的心得递归记忆化与迭代DP不是二选一而是互补的。递归版用来在脑内模拟和验证思路最快迭代版用来做最终提交和保证性能更稳。你不需要在两种写法之间站队而是要把它们都变成肌肉记忆面试时根据需求灵活切换。如果你正在刷区间DP建议把这道题和矩阵链乘法、戳气球LeetCode-312放在一起做对比练习。它们共享同一个骨架但边界条件和转移细节各有不同。做完之后你对递归如何转化为非递归的理解会比刷十道模板题都深刻。这道题不算难但值得反复做。