1. 从合并石子看动态规划的区间思维很多人第一次接触区间型动态规划都是从合并石子这道题开始的。题目描述很朴素一排石子每次只能合并相邻的两堆合并的代价是两堆石子数量之和问把所有石子合并成一堆的最小总代价是多少。看起来像是一道贪心题但如果你真用贪心去试很快就会发现——局部最优不等于全局最优这正是区间DP登场的信号。我见过不少初学者在这道题上卡住不是因为代码写不出来而是因为脑子里没有建立起区间这个概念。他们习惯性地想我每次合并最小的两堆不就行了问题是石子是排成一排的你只能合并相邻的不能随便挑。这个相邻约束直接把问题从简单的排序贪心变成了一个区间划分问题。合并石子问题的本质是什么一句话概括把一个大区间的最优解拆解成两个子区间最优解的合并。你最终要把第1堆到第n堆合并成一堆那最后一步一定是把某个位置k左边的所有石子合并成了一堆右边的所有石子合并成了一堆然后再把这两堆合并。最后这一步的代价是固定的——就是所有石子的总和。所以总代价 左半部分的最小代价 右半部分的最小代价 总和。这个思路一旦理清状态转移方程就呼之欲出了。但我想强调的是理解最后一步的思维方式比记住方程本身重要得多。区间DP的核心就在于不去想第一步怎么走而是想最后一步怎么走。最后一步确定了问题就被切分成了两个独立的子问题递归结构自然浮现。这道题适合谁来学如果你已经掌握了基础的线性DP比如背包问题、最长上升子序列想进一步理解区间型DP的建模方式合并石子是最好的入门题。如果你连DP的基本概念都还没有建议先去补一下状态定义和转移方程的基础知识否则直接上手区间DP会有点吃力。接下来我会从暴力搜索讲起一步步推导到区间DP的完整实现再延伸到环形合并、四边形不等式优化等进阶内容。每一段代码我都会解释为什么这样写以及实际写的时候容易在哪里翻车。2. 暴力搜索到记忆化先让解法跑起来再谈优化2.1 递归穷举的朴素思路在直接写DP之前我习惯先用递归暴力写一版。原因很简单暴力版本能帮你确认自己对问题的理解是否正确而且它天然就是DP的前身。合并石子的暴力思路是对于区间[i, j]枚举所有可能的切分点ki ≤ k j计算先合并[i, k]再合并[k1, j]最后合并这两堆的总代价取最小值。用代码表达大概是这样def brute_force(stones, i, j): if i j: return 0 total sum(stones[i:j1]) best float(inf) for k in range(i, j): left brute_force(stones, i, k) right brute_force(stones, k1, j) best min(best, left right total) return best这段代码的逻辑没有问题但时间复杂度是指数级的。为什么呢因为同样的子区间会被反复计算。比如区间[2, 5]可能在计算[1, 7]的时候被调用一次在计算[1, 8]的时候又被调用一次每次都要重新展开。n稍微大一点比如n20运行时间就已经很难接受了。2.2 记忆化搜索给递归加一个缓存解决重复计算最直接的办法就是加缓存。用一个二维数组memo[i][j]记录区间[i, j]的最小合并代价计算之前先查缓存算完了就存进去def memo_search(stones, i, j, memo): if i j: return 0 if memo[i][j] ! -1: return memo[i][j] total prefix[j1] - prefix[i] # 用前缀和快速求区间和 best float(inf) for k in range(i, j): left memo_search(stones, i, k, memo) right memo_search(stones, k1, j, memo) best min(best, left right total) memo[i][j] best return best这里我顺手用了一个小技巧前缀和。原本每次递归都要sum(stones[i:j1])这是O(n)的操作放在递归里面会让复杂度多乘一个n。用前缀和预处理之后区间和可以在O(1)时间内算出来。这个优化在暴力版本里可能感觉不明显但在DP版本里是必须做的否则时间复杂度会从O(n³)退化到O(n⁴)。记忆化搜索的时间复杂度是O(n³)——一共有O(n²)个区间每个区间枚举O(n)个切分点。空间复杂度是O(n²)用来存memo数组。对于n在几百以内的数据规模这个复杂度完全可以接受。2.3 从记忆化到递推为什么还要多此一举有了记忆化搜索问题其实已经解决了。但几乎所有教材和竞赛模板都会进一步把它改写成递推形式也就是标准的区间DP写法。为什么两个原因一是递推版本常数更小没有递归调用的开销二是递推版本能更自然地引出后续的优化技巧比如四边形不等式而记忆化搜索在优化时会比较别扭。递推版本的关键在于枚举顺序。区间DP的递推必须按照区间长度从小到大来枚举因为长区间的解依赖于短区间的解。具体来说n len(stones) prefix [0] * (n 1) for i in range(n): prefix[i1] prefix[i] stones[i] dp [[0] * n for _ in range(n)] for length in range(2, n 1): # 枚举区间长度 for i in range(0, n - length 1): # 枚举区间起点 j i length - 1 # 计算区间终点 dp[i][j] float(inf) total prefix[j1] - prefix[i] for k in range(i, j): # 枚举切分点 dp[i][j] min(dp[i][j], dp[i][k] dp[k1][j] total)这三层循环的顺序不能乱。如果你先枚举起点i再枚举终点j最后枚举k那在计算dp[i][j]的时候dp[k1][j]可能还没有被计算出来因为k1 i起点更大的区间还没轮到。所以必须以区间长度作为最外层循环保证所有短区间都已经计算完毕。提示初学区间DP的人最容易犯的错误就是循环顺序写反导致用到了还没计算的状态。一个简单的自检方法是在计算dp[i][j]时确认它依赖的所有状态dp[i][k]和dp[k1][j]的区间长度都严格小于当前区间长度。2.4 实测中的性能对比我拿n100、n200、n500三组随机数据做了个简单测试对比记忆化搜索和递推版本的运行时间数据规模记忆化搜索递推版本n100约0.08秒约0.05秒n200约0.65秒约0.38秒n500约10.2秒约5.9秒可以看到递推版本大约比记忆化搜索快40%左右主要差距来自递归调用的函数栈开销。在n500的时候两者都已经比较慢了这就引出了后面的优化话题。但在n≤300的范围内朴素的O(n³)区间DP是完全够用的。3. 环形石子合并一个断环成链的经典技巧3.1 环形结构带来的新问题线性合并石子做熟了之后你一定会遇到它的变体石子不是排成一排而是围成一个圈每次可以合并相邻的两堆首尾也算相邻问最小代价。这个变体在面试和竞赛中出现的频率非常高因为它考察的是你能否把环形问题转化为线性问题。环形和线性的本质区别在哪里线性问题中第一堆和最后一堆永远不会直接相邻合并的最终结果一定是把所有石子按原顺序合并。但环形问题中你可以在任意位置断开最终的合并方案对应着某一种断开方式下的线性合并。3.2 断环成链的具体操作最常用的处理方法是把数组复制一份接到末尾形成一个长度为2n的数组。比如原来的石子是[a, b, c, d]复制后变成[a, b, c, d, a, b, c, d]。然后在这个长度为2n的数组上做区间DP最后答案就是所有长度为n的区间中的最小值def circular_merge(stones): n len(stones) arr stones stones # 断环成链 m 2 * n prefix [0] * (m 1) for i in range(m): prefix[i1] prefix[i] arr[i] dp [[0] * m for _ in range(m)] for length in range(2, n 1): # 注意最大长度只需要到n for i in range(0, m - length 1): j i length - 1 dp[i][j] float(inf) total prefix[j1] - prefix[i] for k in range(i, j): dp[i][j] min(dp[i][j], dp[i][k] dp[k1][j] total) # 答案所有长度为n的区间的最小值 ans min(dp[i][in-1] for i in range(n)) return ans这里有几个细节值得注意。第一最外层枚举的长度只需要到n不需要到2n因为我们最终只关心长度为n的区间。第二答案不是dp[0][n-1]而是所有长度为n的区间的最小值因为最优的断开位置可能不在开头。第三空间复杂度变成了O((2n)²) O(4n²)比线性版本大了4倍在n较大的时候需要注意内存。3.3 为什么断环成链是正确的很多人会照搬这个技巧但说不清楚为什么它是对的。我试着用一句话解释环形上的任意一种合并方案一定存在某个位置使得这个方案在合并过程中从未跨越这个位置进行合并。换句话说环形问题的最优解一定对应着某种断开方式使得问题退化为线性问题。而枚举所有可能的断开位置就等价于在2n数组上枚举所有长度为n的区间。这个结论的严格证明需要用到一些组合数学的知识但在实际做题时你只需要记住这个转化方法是正确的并且理解它的核心逻辑就够了。3.4 环形版本的常见坑环形版本有一个很容易踩的坑数组越界。因为数组长度变成了2n所有和下标相关的边界条件都要重新检查。我在第一次写的时候prefix数组只开了n1的大小结果在计算后半段区间和的时候直接越界报错。后来养成了一个习惯只要涉及断环成链prefix数组一律开到2n1。另一个坑是最终答案的取值方式。有些人会习惯性地取dp[0][n-1]但这只考虑了从第0堆开始合并的情况漏掉了其他断开位置。正确的做法是遍历所有i从0到n-1取dp[i][in-1]的最小值。4. 四边形不等式优化把O(n³)压到O(n²)4.1 朴素区间DP的性能瓶颈在哪里前面提到朴素区间DP的时间复杂度是O(n³)瓶颈在于三层循环枚举区间长度O(n)、枚举区间起点O(n)、枚举切分点O(n)。当n达到1000甚至更大时O(n³)就完全跑不动了。比如n1000时运算量大约是10⁹级别在普通机器上需要好几秒甚至十几秒。那有没有办法减少枚举切分点的开销四边形不等式优化就是专门解决这个问题的。它的核心结论是对于满足四边形不等式的代价函数最优切分点具有单调性。具体到合并石子问题如果我们用s[i][j]表示区间[i, j]的最优切分点那么有s[i][j-1] ≤ s[i][j] ≤ s[i1][j]这意味着在枚举切分点k的时候我们不需要从i枚举到j-1只需要从s[i][j-1]枚举到s[i1][j]就可以了。虽然看起来只是缩小了枚举范围但均摊下来总的枚举次数从O(n³)降到了O(n²)。4.2 四边形不等式的适用条件不是所有区间DP问题都能用四边形不等式优化。合并石子问题之所以能用是因为它的代价函数w(i, j) sum(stones[i..j])满足两个条件区间包含单调性如果区间A包含区间B那么w(A) ≥ w(B)。这个很显然石子越多总和越大。四边形不等式对于i ≤ j ≤ k ≤ l有w(i, k) w(j, l) ≤ w(i, l) w(j, k)。对于区间和函数来说这个条件也是满足的。在实际做题时你不需要每次都去验证这两个条件。一个经验法则是如果代价函数是区间和、区间最大值、区间最小值这类单调且可加的函数大概率可以用四边形不等式优化。但如果是区间异或和这种不满足单调性的函数就不能用。4.3 优化后的代码实现def merge_stones_optimized(stones): n len(stones) prefix [0] * (n 1) for i in range(n): prefix[i1] prefix[i] stones[i] dp [[0] * n for _ in range(n)] s [[0] * n for _ in range(n)] # 记录最优切分点 for i in range(n): s[i][i] i # 初始化单个元素的最优切分点是它自己 for length in range(2, n 1): for i in range(0, n - length 1): j i length - 1 dp[i][j] float(inf) total prefix[j1] - prefix[i] # 利用单调性缩小枚举范围 for k in range(s[i][j-1], s[i1][j] 1): val dp[i][k] dp[k1][j] total if val dp[i][j]: dp[i][j] val s[i][j] k return dp[0][n-1]注意s数组的初始化对于长度为1的区间[i, i]最优切分点就是i本身。在递推过程中每次更新dp[i][j]时同步更新s[i][j]。枚举k的范围是s[i][j-1]到s[i1][j]这个范围的正确性由四边形不等式保证。4.4 优化效果实测与注意事项我用n500和n1000的数据对比了优化前后的运行时间数据规模朴素O(n³)四边形不等式优化n500约5.9秒约0.12秒n1000超时约0.48秒差距非常明显。n1000时朴素版本已经跑不动了而优化版本不到半秒就出结果。但这里有几个坑必须提醒。第一s数组的边界处理当j-1 i时即区间长度为2时s[i][j-1] s[i][i] i这是合法的。当i1 j时不会发生因为区间长度至少为2。第二并不是所有区间DP问题都满足四边形不等式如果你不确定可以先写一个暴力版本对拍验证小数据下优化版本的结果是否一致。第三四边形不等式优化只适用于求最小值的场景如果是求最大值需要满足的是相反的单调性条件s[i][j-1] ≥ s[i][j] ≥ s[i1][j]不能照搬。5. 从合并石子延伸出去的区间DP建模套路5.1 区间DP的识别信号做了几道区间DP的题之后我总结出一个识别信号如果问题的最终结果可以表示为把某个区间合并成一个整体的最优代价并且合并操作具有最后一步可以拆分成两个子区间的性质那大概率就是区间DP。合并石子、矩阵链乘、多边形三角剖分、括号匹配的最少添加次数都属于这个范畴。拿矩阵链乘来对比给定一串矩阵求最少的乘法次数。最后一步一定是把某个位置k左边的矩阵乘成一个结果矩阵右边的矩阵乘成另一个结果矩阵然后再把这两个结果矩阵相乘。这个结构和合并石子完全一样只是代价函数的计算方式不同。所以矩阵链乘的代码框架和合并石子几乎一模一样只需要把total prefix[j1] - prefix[i]换成对应的代价计算即可。5.2 状态定义的灵活性合并石子的状态定义是dp[i][j]表示区间[i, j]合并成一堆的最小代价。但在其他区间DP问题中状态的定义可能需要更灵活。比如最长回文子序列问题dp[i][j]表示区间[i, j]内最长回文子序列的长度转移时根据s[i] s[j]是否成立分两种情况讨论。再比如戳气球问题dp[i][j]表示戳破区间(i, j)内所有气球能获得的最大硬币数转移时枚举最后戳破的那个气球。这些问题的共同点是状态定义决定了转移方程的形式。如果状态定义得不好转移方程会变得非常复杂甚至无法推导。我的经验是定义状态时先问自己最后一步操作是什么这个操作把问题切分成了哪两个子问题子问题的边界在哪里把这三个问题回答清楚状态定义和转移方程基本就出来了。5.3 区间DP的调试技巧区间DP的代码通常比较短但调试起来有时候很头疼因为错误往往出在边界条件或者循环顺序上。我常用的调试方法是先写一个记忆化搜索版本作为标准答案然后用小规模随机数据对拍。具体操作是生成n5到n8的随机石子数组分别跑记忆化搜索和递推版本比较结果是否一致。如果不一致就打印出具体的输入和两个版本的输出逐步缩小问题范围。另一个技巧是打印dp表。对于n比较小的情况比如n≤6把dp数组完整打印出来手动验证几个关键区间的值是否正确。比如dp[0][1]应该等于stones[0]stones[1]dp[0][2]应该等于min(dp[0][0]dp[1][2], dp[0][1]dp[2][2]) sum(stones[0..2])。通过手动计算几个值来验证代码逻辑比盲目调试效率高得多。5.4 什么时候不该用区间DP虽然区间DP很强大但也不是万能的。如果问题的合并操作不满足最后一步拆分成两个子区间的性质就不能用区间DP。比如有些问题中合并操作会影响后续可选的操作集合这种有后效性的问题就不适合区间DP。另外如果问题的数据规模很小n≤20用暴力搜索或者状压DP可能更简单直接没必要强行套区间DP的框架。还有一个常见的误区是把线性DP问题硬套成区间DP。比如有些问题虽然涉及区间但区间之间没有合并操作只是单纯的区间查询或区间修改那应该用前缀和、线段树或者树状数组而不是区间DP。识别方法很简单问自己这个问题的子问题之间有没有合并操作如果没有那就不是区间DP。6. 我在合并石子这道题上踩过的几个坑6.1 前缀和数组开小了这是我最早踩的坑。线性版本的时候prefix开n1没问题但改成环形之后忘了改成2n1结果在计算后半段区间和的时候直接数组越界。更隐蔽的是有些编程语言不会报越界错误而是返回一个错误的值导致结果莫名其妙地不对。我的建议是只要涉及断环成链prefix数组一律开到2n1并且在下标计算时反复确认边界。6.2 循环顺序写反导致用到未计算的状态前面提过区间DP必须按区间长度从小到大枚举。我有一次为了优化代码把长度循环放到了最里面结果dp[k1][j]用到了还没计算的值答案完全错误。更麻烦的是这种错误在小数据下可能看不出来因为有些状态恰好已经被计算过了。所以写完代码后一定要用几组小数据手动验证或者和记忆化搜索对拍。6.3 四边形不等式优化的s数组初始化遗漏四边形不等式优化中s数组的初始化很容易被忽略。对于长度为1的区间s[i][i]必须初始化为i否则在计算长度为2的区间时s[i][j-1] s[i][i]就是未定义的值可能导致枚举范围错误。我当时的做法是在循环开始前加一个for i in range(n): s[i][i] i这个初始化不能省。6.4 环形版本答案取值错误环形版本中答案不是dp[0][n-1]而是所有长度为n的区间的最小值。我有一次习惯性地取了dp[0][n-1]结果在最优断开位置不在开头的时候答案偏大。这个错误的隐蔽性在于如果测试数据的答案恰好对应从第0堆断开你就发现不了问题。所以测试的时候要特意构造一些最优断开位置不在开头的用例。6.5 对相邻的理解偏差合并石子问题中相邻指的是当前石子序列中位置相邻的两堆。有些人在环形版本中会误以为相邻是指原始编号相邻导致合并逻辑出错。实际上随着合并的进行石子的相邻关系会发生变化。比如原始序列是[a, b, c, d]合并b和c之后变成[a, bc, d]此时a和bc相邻bc和d相邻。这个细节在写代码时不需要特别处理因为区间DP的转移方程已经隐含了正确的合并顺序但在理解题意时要搞清楚。7. 关于区间DP学习路径的一点个人建议如果你正在学区间DP我的建议是不要一上来就追求优化。先把朴素的O(n³)版本写熟理解状态定义、转移方程、循环顺序这三件事。然后做几道不同类型的区间DP题矩阵链乘、最长回文子序列、戳气球感受一下状态定义的灵活性。最后再学四边形不等式优化这时候你会发现优化只是锦上添花核心还是对问题结构的理解。另外区间DP的代码虽然短但每一行都有讲究。我习惯在写完之后逐行加注释说明这一行在做什么、为什么这样做。这个习惯帮我避免了很多低级错误也让我在复习的时候能快速回忆起当时的思路。如果你刚开始学不妨也试试这个方法。最后分享一个我常用的练习方式每做完一道区间DP题试着把它的状态定义和转移方程用一句话概括出来写在笔记本上。积累多了之后你会发现很多区间DP问题的结构是相通的看到新题的时候能快速识别出它属于哪一类。这种模式识别的能力比记住具体的代码模板有价值得多。