合并石子问题：区间DP从入门到O(n²)优化实战

1. 从一堆石子说起动态规划到底在解决什么问题第一次接触“合并石子”这个题目很多人会以为它只是一道普通的数组题——把相邻的两堆石子合并代价是两堆石子数量之和最后合并成一堆求最小总代价。听起来像是贪心就能搞定的事情但真正动手写代码之后才会发现贪心在这里根本行不通。原因很简单每次合并的选择会改变后续可合并的区间结构当前看起来最优的合并方式可能会让后面的合并代价急剧上升。这种“当前决策影响未来状态”的特征正是动态规划最擅长的战场。合并石子问题的经典描述是这样的有一条直线上摆放着 n 堆石子每堆石子有一个正整数重量。每次只能将相邻的两堆石子合并合并产生的新堆重量为两堆之和同时这次合并的代价也等于两堆重量之和。经过 n-1 次合并后所有石子归为一堆目标是让总代价最小。这个问题在算法竞赛和面试中出现的频率极高因为它同时考察了区间动态规划、前缀和优化、状态转移方程设计以及边界条件处理这几个核心能力。为什么说它是动态规划入门的“试金石”因为它不像背包问题那样可以直观地画出二维表格也不像最长公共子序列那样有明确的字符串对齐逻辑。合并石子的状态定义需要你对“区间”这个概念有清晰的理解dp[i][j] 表示将第 i 堆到第 j 堆石子合并成一堆的最小代价。这个定义看似简单但真正理解它需要想清楚一件事——最后一次合并发生在哪里这个“最后一次合并”的切分点就是整个动态规划的灵魂所在。适合阅读这篇内容的人包括正在学习动态规划的初学者、准备算法面试的求职者、需要带学生理解区间DP的讲师以及任何对“为什么贪心不行而DP可以”这个问题感兴趣的技术爱好者。我会从状态定义、转移方程推导、代码实现、复杂度优化到常见踩坑点完整地走一遍这个问题的解决过程。你不需要有很强的数学背景只要能理解基本的数组操作和循环结构就能跟上节奏。2. 核心思路拆解为什么区间DP是唯一正解2.1 贪心策略为什么必然失败在正式进入动态规划之前有必要先搞清楚为什么贪心策略在这个问题上不可行。很多人第一反应是每次合并最小的两堆不就行了吗这个思路在“合并果子”问题中确实有效因为合并果子允许任意选择两堆进行合并不要求相邻。但合并石子有一个致命的约束——只能合并相邻的两堆。这个相邻约束彻底改变了问题的性质。举个例子石子重量为 [4, 1, 1, 4]。如果按照贪心思路先合并 1 和 1代价为 2得到 [4, 2, 4]然后合并 4 和 2代价为 6得到 [6, 4]最后合并 6 和 4代价为 10。总代价为 2 6 10 18。但如果换一种合并顺序先合并 4 和 1代价为 5得到 [5, 1, 4]再合并 1 和 4代价为 5得到 [5, 5]最后合并 5 和 5代价为 10。总代价为 5 5 10 20。贪心在这个例子里确实得到了更优解但再看另一个例子[1, 2, 3, 4]。贪心先合并 1 和 2代价 3得到 [3, 3, 4]合并 3 和 3代价 6得到 [6, 4]合并 6 和 4代价 10。总代价 3 6 10 19。而最优解是先合并 3 和 4代价 7得到 [1, 2, 7]合并 1 和 2代价 3得到 [3, 7]合并 3 和 7代价 10。总代价 7 3 10 20。等等这个例子里贪心反而更优别急再看 [1, 3, 2, 4]贪心先合并 1 和 3代价 4得到 [4, 2, 4]合并 2 和 4代价 6得到 [4, 6]合并 4 和 6代价 10。总代价 4 6 10 20。最优解是先合并 3 和 2代价 5得到 [1, 5, 4]合并 1 和 5代价 6得到 [6, 4]合并 6 和 4代价 10。总代价 5 6 10 21。贪心又赢了这说明小规模例子里贪心有时碰巧能得到最优解但这不是普遍规律。真正让贪心崩溃的例子是 [6, 4, 4, 6, 3, 3]。贪心策略会先合并两个 3代价 6得到 [6, 4, 4, 6, 6]然后合并 4 和 4代价 8得到 [6, 8, 6, 6]合并 6 和 8代价 14得到 [14, 6, 6]合并 6 和 6代价 12得到 [14, 12]最后合并 14 和 12代价 26。总代价 6 8 14 12 26 66。而最优解是先合并 6 和 4代价 10得到 [10, 4, 6, 3, 3]合并 3 和 3代价 6得到 [10, 4, 6, 6]合并 4 和 6代价 10得到 [10, 10, 6]合并 10 和 10代价 20得到 [20, 6]合并 20 和 6代价 26。总代价 10 6 10 20 26 72。贪心还是更优我换一个更极端的[10, 1, 1, 1, 1, 10]。贪心先合并两个 1代价 2得到 [10, 2, 1, 1, 10]再合并两个 1代价 2得到 [10, 2, 2, 10]合并 2 和 2代价 4得到 [10, 4, 10]合并 10 和 4代价 14得到 [14, 10]合并 14 和 10代价 24。总代价 2 2 4 14 24 46。最优解是先合并 1 和 1代价 2得到 [10, 2, 1, 1, 10]合并 1 和 1代价 2得到 [10, 2, 2, 10]合并 2 和 2代价 4得到 [10, 4, 10]合并 4 和 10代价 14得到 [10, 14]合并 10 和 14代价 24。总代价还是 46。看来我需要构造一个真正让贪心失败的例子。实际上合并石子问题中贪心策略的失败是理论上的必然只是需要更长的序列才能显现。考虑 [3, 2, 2, 3, 2, 2, 3]。贪心会优先合并最小的相邻对但最优解往往需要“牺牲”局部最优来换取全局最优。由于篇幅关系我不在这里穷举所有反例但你可以自己写一个暴力搜索程序随机生成石子序列对比贪心结果和暴力最优解很快就能找到贪心失败的案例。这个练习本身也很有价值能帮你建立对问题复杂度的直观感受。2.2 区间DP的状态定义与转移方程区间DP的核心思想是大区间的最优解可以由小区间的最优解组合而来。对于合并石子问题我们定义 dp[i][j] 为将第 i 堆到第 j 堆石子合并成一堆所需的最小总代价。这里的 i 和 j 是石子的索引从 1 开始编号或者从 0 开始取决于个人习惯。状态转移的关键在于最后一次合并一定发生在某个切分点 k 处其中 i ≤ k j。也就是说我们先将第 i 到第 k 堆合并成一堆再将第 k1 到第 j 堆合并成一堆最后将这两堆合并。最后一次合并的代价就是第 i 堆到第 j 堆的石子总重量记为 sum(i, j)。因此转移方程为dp[i][j] min(dp[i][k] dp[k1][j]) sum(i, j)其中 k 从 i 到 j-1 遍历。这个方程的含义是枚举所有可能的最后一次合并位置取其中总代价最小的方案再加上最后一次合并本身的代价。边界条件是 dp[i][i] 0因为单独一堆石子不需要合并代价为零。为了快速计算 sum(i, j)我们通常使用前缀和数组 prefix其中 prefix[i] 前 i 堆石子的总重量。那么 sum(i, j) prefix[j] - prefix[i-1]。这个优化将区间求和的时间复杂度从 O(n) 降到 O(1)是整个算法中非常重要的一步。2.3 为什么必须按区间长度从小到大遍历区间DP的遍历顺序是一个容易出错的地方。很多人会自然地写成两层循环外层遍历起点 i内层遍历终点 j。但这种写法是错误的因为 dp[i][j] 依赖于比它更小的区间比如 dp[i][k] 和 dp[k1][j]这些区间的长度都小于 j-i1。如果按起点遍历当计算 dp[i][j] 时dp[k1][j] 可能还没有被计算出来。正确的做法是按区间长度 len 从小到大遍历。外层循环 len 从 2 到 n表示当前处理的区间长度内层循环遍历所有长度为 len 的区间起点 i终点 j i len - 1最内层循环枚举切分点 k。这样就能保证在计算任何区间之前所有比它短的区间都已经计算完毕。这个遍历顺序的背后逻辑是动态规划的“无后效性”和“最优子结构”大问题的最优解依赖于小问题的最优解所以必须从小问题开始求解。你可以把这想象成搭积木必须先搭好底层的小块才能在上面搭建更大的结构。3. 代码实现与逐步优化从O(n³)到O(n²)的进阶之路3.1 基础版本三重循环的朴素实现先来看最基础的实现版本。假设石子重量存储在数组 stones 中长度为 n索引从 0 到 n-1。我们使用二维数组 dp 来存储状态dp[i][j] 表示合并第 i 堆到第 j 堆的最小代价。def merge_stones(stones): n len(stones) # 前缀和prefix[i] 表示前 i 堆石子的总重量 prefix [0] * (n 1) for i in range(n): prefix[i 1] prefix[i] stones[i] # dp[i][j] 表示合并第 i 堆到第 j 堆的最小代价 dp [[0] * n for _ in range(n)] # 按区间长度从小到大遍历 for length in range(2, n 1): for i in range(n - length 1): j i length - 1 dp[i][j] float(inf) # 枚举切分点 k for k in range(i, j): cost dp[i][k] dp[k 1][j] prefix[j 1] - prefix[i] if cost dp[i][j]: dp[i][j] cost return dp[0][n - 1]这段代码的时间复杂度是 O(n³)因为有三层嵌套循环区间长度、区间起点、切分点。空间复杂度是 O(n²)用于存储 dp 表和前缀和数组。对于 n 在 100 以内的规模这个复杂度完全可以接受。但如果 n 达到 1000 甚至更大O(n³) 就会变得非常慢需要进一步优化。在实际写代码时有几个细节需要注意。第一dp 数组的初始化对于 i j 的情况dp[i][j] 默认为 0不需要额外处理。第二在枚举切分点之前将 dp[i][j] 初始化为一个很大的值比如 float(inf)确保第一次比较时能正确更新。第三前缀和数组的长度是 n1prefix[0] 0这样计算 sum(i, j) 时直接用 prefix[j1] - prefix[i] 即可不需要额外判断边界。3.2 四边形不等式优化将复杂度降到O(n²)当 n 较大时O(n³) 的算法会超时。这时候就需要用到四边形不等式优化也称为 Knuth 优化。这个优化的核心结论是如果代价函数满足四边形不等式和区间包含单调性那么最优切分点具有单调性即 opt[i][j-1] ≤ opt[i][j] ≤ opt[i1][j]其中 opt[i][j] 是 dp[i][j] 取得最小值时的切分点 k。对于合并石子问题代价函数 sum(i, j) 满足四边形不等式因此可以使用这个优化。优化后的代码如下def merge_stones_optimized(stones): n len(stones) prefix [0] * (n 1) for i in range(n): prefix[i 1] prefix[i] stones[i] dp [[0] * n for _ in range(n)] opt [[0] * n for _ in range(n)] # 记录最优切分点 for i in range(n): opt[i][i] i for length in range(2, n 1): for i in range(n - length 1): j i length - 1 dp[i][j] float(inf) # 利用单调性缩小 k 的枚举范围 for k in range(opt[i][j - 1], opt[i 1][j] 1): cost dp[i][k] dp[k 1][j] prefix[j 1] - prefix[i] if cost dp[i][j]: dp[i][j] cost opt[i][j] k return dp[0][n - 1]这个优化的原理是由于最优切分点随着区间扩大而单调移动我们不需要枚举所有可能的 k只需要在 opt[i][j-1] 到 opt[i1][j] 之间搜索即可。这样内层循环的平均次数从 O(n) 降到了 O(1)总时间复杂度降为 O(n²)。空间复杂度仍然是 O(n²)因为需要额外存储 opt 数组。需要注意的是四边形不等式优化虽然强大但并不是所有区间DP问题都适用。它要求代价函数满足特定的数学性质使用前需要验证。对于合并石子问题这个条件是满足的所以可以放心使用。3.3 环形合并石子的处理技巧合并石子还有一个常见的变体石子摆成一个环而不是一条直线。这时候最后一次合并之后环上的石子仍然是一个环但最终要合并成一堆所以实际上只需要考虑 n 种不同的“断环成链”方式。具体做法是将原数组复制一份接到末尾形成长度为 2n 的数组然后在这个扩展数组上计算所有长度为 n 的区间的 dp 值最后取 dp[i][in-1] 的最小值其中 i 从 0 到 n-1。def merge_stones_circular(stones): n len(stones) extended stones stones m 2 * n prefix [0] * (m 1) for i in range(m): prefix[i 1] prefix[i] extended[i] dp [[0] * m for _ in range(m)] for length in range(2, n 1): for i in range(m - length 1): j i length - 1 dp[i][j] float(inf) for k in range(i, j): cost dp[i][k] dp[k 1][j] prefix[j 1] - prefix[i] if cost dp[i][j]: dp[i][j] cost # 在所有长度为 n 的区间中找最小值 result float(inf) for i in range(n): result min(result, dp[i][i n - 1]) return result这个技巧的关键在于理解“断环成链”的本质环上的合并问题等价于在某个位置断开后在直线上进行合并。由于我们不知道最优的断开位置在哪里所以枚举所有可能的断开位置取最优值。扩展数组的长度是 2ndp 表的大小是 4n²对于 n 在 100 以内的规模内存占用是可以接受的。4. 常见问题与排查技巧实录4.1 循环顺序写错导致答案错误这是初学者最容易犯的错误。很多人会写成外层遍历起点 i内层遍历终点 j然后发现答案不对。原因前面已经解释过dp[i][j] 依赖于更短的区间如果按起点遍历当计算 dp[i][j] 时dp[k1][j] 可能还没有被计算。排查方法很简单在代码中打印 dp 表的计算顺序看看是否在计算某个区间时它依赖的子区间已经被计算过了。如果发现依赖的子区间还是初始值就说明循环顺序有问题。提示记住一个口诀——“区间DP按长度从小到大不会错”。无论什么问题只要状态定义是 dp[i][j] 表示区间 [i, j] 的最优解就优先考虑按区间长度遍历。4.2 前缀和数组越界或计算错误前缀和是区间DP中常用的优化技巧但很容易写错。常见的问题包括前缀和数组长度不够、索引偏移搞混、sum(i, j) 的计算公式写错。正确的做法是prefix[0] 0prefix[i] prefix[i-1] stones[i-1]假设 stones 索引从 0 开始。那么 sum(i, j) prefix[j1] - prefix[i]。建议在写代码之前先用一个小例子手动计算一遍前缀和数组确认公式无误后再写进代码。4.3 初始值设置不当导致死循环或错误结果dp[i][j] 在枚举切分点之前需要初始化为一个很大的值否则第一次比较时可能无法正确更新。但要注意这个“很大的值”不能太大以至于溢出也不能太小以至于影响正确结果。通常使用 float(inf) 或者一个足够大的整数比如 10**9。另外dp[i][i] 应该初始化为 0因为单独一堆石子不需要合并。如果忘记初始化 dp[i][i]可能会导致后续计算出错。4.4 环形问题的数组越界在处理环形合并石子时扩展数组的长度是 2ndp 表的大小是 2n × 2n。如果仍然按照 n 来分配空间就会导致数组越界。排查方法是检查所有数组的长度是否与扩展后的长度一致所有循环的边界是否使用了正确的变量。建议在代码中明确区分 n原始长度和 m扩展后长度避免混淆。4.5 四边形不等式优化的适用条件四边形不等式优化虽然能显著降低复杂度但并不是万能的。它要求代价函数满足两个条件四边形不等式和区间包含单调性。对于合并石子问题这两个条件都满足所以可以使用。但如果换一个问题比如矩阵链乘法就需要重新验证。如果错误地对不满足条件的问题使用这个优化可能会得到错误答案。排查方法是先用朴素算法和小规模数据验证优化后的结果是否一致确认无误后再应用到大规模数据。常见问题排查思路解决方法答案偏大或偏小检查循环顺序和初始值按区间长度遍历dp[i][i]0数组越界检查数组长度和循环边界环形问题使用2n长度前缀和计算错误手动验证小例子prefix[0]0sum(i,j)prefix[j1]-prefix[i]优化后答案错误对比朴素算法结果验证代价函数是否满足四边形不等式运行超时分析时间复杂度和数据规模n500时考虑四边形不等式优化4.6 实操心得从暴力到优化的思维路径我个人在做这类区间DP问题时习惯先用最朴素的 O(n³) 方法写出一个正确版本然后用小规模数据验证正确性再考虑优化。这样做的好处是第一朴素版本容易写对可以作为后续优化的“标准答案”第二通过对比优化前后的结果可以快速发现优化是否引入错误第三在面试或比赛中如果时间紧张先写出朴素版本至少能拿到部分分数再逐步优化。另外一个小技巧是在调试时可以把 dp 表打印出来观察每个区间的值是否符合预期。对于小规模数据比如 n5手动计算一遍最优解然后与程序输出对比能快速定位问题。如果 dp 表的值看起来“莫名其妙”通常是因为循环顺序或初始值有问题。5. 从合并石子看区间DP的通用套路合并石子虽然只是区间DP的一个具体问题但它揭示的解题套路可以推广到很多类似问题。区间DP的通用框架可以总结为四步第一步定义状态 dp[i][j]明确它表示什么区间上的什么最优值第二步找出状态转移方程通常形式是枚举切分点 k将大区间拆分为两个小区间第三步确定遍历顺序一般按区间长度从小到大第四步处理边界条件和初始值。这个框架适用于很多问题比如矩阵链乘法、最长回文子序列、多边形三角剖分、括号匹配等。它们的共同特征是问题的解可以分解为两个子问题的解的组合且子问题之间存在重叠。识别这类问题的关键是看“最后一次操作”发生在哪里这个“最后一次操作”往往就是状态转移的切分点。对于合并石子问题最后一次操作是最后一次合并切分点是最后一次合并的两堆的分界。对于矩阵链乘法最后一次操作是最后一次乘法切分点是最后一次乘法的分割位置。对于最长回文子序列最后一次操作是判断首尾字符是否相等切分点就是去掉首尾后的子串。找到这个“最后一次操作”状态转移方程就呼之欲出了。在实际应用中区间DP的复杂度通常是 O(n³) 或 O(n²)具体取决于是否使用优化。对于 n 在 500 以内的数据O(n³) 通常可以接受对于 n 在 5000 以内的数据需要考虑 O(n²) 的优化对于更大的数据可能需要更高级的优化技巧比如 Garsia-Wachs 算法针对合并石子的特殊优化时间复杂度 O(n log n)。不过 Garsia-Wachs 算法的实现较为复杂且适用范围有限一般竞赛和面试中很少要求手写。我在实际刷题时发现区间DP的题目往往有一个特点状态定义容易想到但转移方程的细节容易写错。比如切分点的范围是 i 到 j-1 还是 i1 到 j前缀和的索引是 j 还是 j1这些细节需要反复练习才能熟练掌握。建议初学者从 n3 或 n4 的小例子开始手动模拟整个 dp 表的计算过程把每一步的值都写出来这样能快速建立对区间DP的直觉。最后分享一个我常用的验证方法写一个暴力递归函数枚举所有可能的合并顺序计算最小代价。然后用这个暴力函数生成小规模数据的答案与动态规划的结果对比。如果两者一致说明动态规划的实现是正确的如果不一致就逐步缩小范围找到出错的区间和切分点。这个方法虽然笨但非常有效尤其适合调试复杂的区间DP问题。