第一次在题目列表里看到《分离与合体》的时候我第一反应是这题是不是要模拟什么魔法合成点进去才发现就是一个很干净的区间DP模型给你 n 个数排成一排每次可以把一个长度大于 1 的连续区间从中间切一刀分成左右两个非空区间获得左端点的数乘右端点的数的加分问所有区间都切成长度为 1 后最多能拿多少分。这类题一上来容易想歪有人去模拟切割顺序有人直接贪心其实把它和经典的石子合并放在一起看本质就是区间DP。这篇文章从状态定义、转移方程写到记忆化搜索和递推实现再讲清楚怎么输出分离和合体方案最后说说四边形不等式优化和一些常见坑适合刚学区间DP的人照着一步步写。1. 分离正向做、合体反向看先想清楚操作的本质1.1 切一刀和拼一次是互逆操作先看操作本身。假设当前有一段连续区间[l, r]你从中间某个位置k把它切成[l, k]和[k1, r]这次分离的得分是a[l] * a[r]和k具体选在哪里没关系只和这段区间两端的原始位置有关。这就很有意思了。如果倒过来看从[l, k]和[k1, r]这两个相邻区间合并成[l, r]得到的收益同样是a[l] * a[r]。所以分离和合体其实是同一件事的两个方向中间的分割点一模一样。你从完整区间一路切到单点和从单点一路合并到完整区间维护的是同一棵二叉树叶子是原始的单点每个内部节点代表一次分离或合体发生的位置。为什么这个等价性重要因为做区间DP时我们习惯从小到大算状态也就是先处理短区间再处理长区间这正是合体方向。但题目描述的是分离方向很多新手会纠结要不要倒着模拟。实际上不需要你只要把f[i][j]定义为区间[i, j]从任意状态变成最终状态能获得的最大收益就行了。分离和合体共享同一套状态和转移最后求的f[1][n]就是答案。我拿一个例子说明。比如a [3, 1, 5, 8]最优策略下第一次分离是在[1,4]的k1处切得到3*824分剩余[2,4]在k2处切得到1*88分最后[3,4]在k3处切得到5*840分总分 72。反过来看合体顺序就变成先合并[3,4]得 40再合并[2,4]得 8最后合并[1,4]得 24总分同样是 72。分数一样树的结构也一样只是遍历方向不同。1.2 为什么贪心会挂一个很自然的想法是每次找当前能获得最大收益的一刀切下去局部最优拼全局最优。听上去合理但实际上很容易翻车因为收益只和区间两端有关而两端是谁取决于之前的切割或合并形态这不是一个可以分离的贪心指标。举个例子a [5, 1, 4, 5]。这个序列无论在[1,4]的哪个位置切第一刀当前收益都是5*525看起来完全一样。但如果你第一刀切在k3接下来处理左区间[1,3]在里面切第一刀收益都是5*420这时候选k1会让[1,3]的总收益变成 24而选k2会让[1,3]的总收益变成 25一步之差整个问题的最优值就不同了。你只盯着当前最大收益去选根本没法判断哪个切口把未来引向更好的结构。这就是区间DP存在的意义把每一个可能的切割点都枚举一遍让状态自己说话。贪心只看到了当前这一步DP看到的是以当前区间为根的整棵子树。2. 状态定义与转移方程一个空位都不能差的推导2.1 状态和初始值定义f[i][j]表示区间[i, j]完全处理完后的最大收益。这里处理完可以理解为如果题目要求的是分离那就是把[i,j]全部切成单点如果题目要求的是合体那就是把[i,j]内的所有单点合并成一个区间。初始值是f[i][i] 0因为长度为 1 的区间已经不需要再操作既不能切也不能合自然没有收益。如果题目里a[i]都是正整数那么所有收益非负f数组可以初始化为 0。如果题目可能出现负数就要把所有状态初始化为-INF比如-1e18否则取max的时候会被 0 污染。大多数题解默认给的是正整数但我在做题时会习惯性判断一下数据范围里有没有负数这是个好习惯。2.2 转移方程对于区间[l, r]最后一次分离或者说最后一次合体一定发生在某个位置k上l k r。这次操作把区间分成左半部分[l, k]右半部分[k1, r]左右两半各自内部的最优收益分别是f[l][k]和f[k1][r]它们之间互不影响因为切割之后两半就成为独立的子问题。再加上当前这次切割的收益a[l] * a[r]就得到转移方程f[l][r] max( f[l][k] f[k1][r] a[l] * a[r] ) k from l to r-1这里的核心是收益只依赖整个区间[l, r]的两端和分割点k没有关系。这也是这道题和别的区间DP题最大的区别。拿石子合并对比石子合并里合并两堆的代价等于两堆石子数量之和会随着分割点变化而这题的a[l] * a[r]是固定的你只要定下区间两端不管中间怎么切这一刀的收益都不会变。为什么可以只用子问题最优值用反证法想一下。假设[l, k]内部存在一种方案收益比f[l][k]更大那我把这个方案替换进去[l, r]的总收益也会变大这就和f[l][r]已经是最优值矛盾。所以左右子区间各自取最优一定不会亏最优子结构成立。2.3 循环边界和枚举顺序转移的时候必须注意几个边界k从l遍历到r-1不能等于r否则右区间为空。len从 2 开始枚举因为长度为 1 的状态已经初始化好了。区间[l, r]必须满足l len - 1 n。这个转移的时间复杂度是O(n^3)因为状态数是O(n^2)每个状态要枚举O(n)个分割点。空间复杂度是O(n^2)。n 500的时候大概 1.25 亿次运算轻松过n 1000就到 10 亿了需要考虑优化或者换思路。3. 记忆化搜索和递推二选一我建议先写递归3.1 记忆化搜索不容易写错枚举顺序区间DP最恶心的地方不是转移方程而是循环顺序。很多新手先写for l再写for r结果发现调出来的答案总是差一点。我自己的习惯是第一版永远写记忆化搜索因为递归天然保证了子区间先计算完全不用管区间长度枚举顺序。下面是 C 的记忆化搜索写法#include bits/stdc.h using namespace std; using ll long long; const int N 505; int n; ll a[N]; ll f[N][N]; ll dfs(int l, int r) { if (l r) return 0; if (f[l][r] ! -1) return f[l][r]; ll best -1; for (int k l; k r; k) { best max(best, dfs(l, k) dfs(k 1, r) a[l] * a[r]); } return f[l][r] best; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n; for (int i 1; i n; i) cin a[i]; memset(f, -1, sizeof(f)); cout dfs(1, n) \n; return 0; }这里有个很关键的细节f[l][r]初始化为-1不是0。因为收益可能为 0比如长度为 1 的区间如果用if (f[l][r]) return f[l][r];判断长度为 1 的边界倒是没问题但某些合法状态恰好算出来是 0就会被当成没算过反复递归轻则超时重则栈溢出。3.2 递推为了常数和后续优化记忆化搜索虽然好写但常数比递推大而且某些题目特意卡递归栈深度。所以第二版我会改成递推。区间DP递推的核心规律是先枚举区间长度再枚举左端点最后枚举分割点。for (int len 2; len n; len) { for (int l 1; l len - 1 n; l) { int r l len - 1; for (int k l; k r; k) { f[l][r] max(f[l][r], f[l][k] f[k 1][r] a[l] * a[r]); } } }为什么必须按长度枚举因为你在算f[l][r]的时候需要依赖f[l][k]和f[k1][r]这两个区间的长度都小于r-l1。只有把短区间全部算完长区间才能得到正确结果。如果按for (l 1; l n; l) for (r l1; r n; r)这种顺序计算f[1][3]时可能需要f[2][3]而f[2][3]要等外层l2的时候才会被计算顺序就乱了。这类错误不会导致数组越界只会得到错误答案非常隐蔽。3.3 实际比赛里我怎么选如果n 500两种写法都行记忆化搜索多出来的递归开销完全可以接受。如果n 1000而且题目时间比较宽裕记忆化搜索可能也能过但递推更稳。如果n到 2000 以上就必须考虑四边形不等式优化或者换状态设计了。我的建议是先用记忆化搜索把思路验证清楚确保转移方程没问题再花两分钟改成递推。区间DP最怕的不是不会写转移而是转移写对了却被循环顺序坑得怀疑人生。递归版代码朴素直接递推版代码适合卡常数两个都写一遍你对这个模型的理解会深很多。4. 输出方案记录决策点把分离和合体顺序打出来很多区间DP题不是只求最大值还要求输出操作顺序。《分离与合体》这类题经常让你输出分离过程有些变种还要求输出合体过程。这个需求一点也不复杂核心就是额外开一个数组g[l][r]在更新最优值的时候记录下对应的分割点k。4.1 开一个决策数组在记忆化搜索的更新逻辑里加一行ll best -1; int bestK -1; for (int k l; k r; k) { ll val dfs(l, k) dfs(k 1, r) a[l] * a[r]; if (val best) { best val; bestK k; } } g[l][r] bestK; return f[l][r] best;注意这里用的是严格大于不是。如果用当多个分割点得到相同最优值时每次记录的都是最后一个输出方案会不稳定但也不算错。实际做题时严格大于能让方案固定下来对拍和调试都更方便。4.2 输出分离顺序分离是从大区间往小区间切所以应该先输出当前[l, r]的切割点再去递归左右两边类似前序遍历。假设题目要求每行输出一个分割操作可以这么写void printSplit(int l, int r) { if (l r) return; int k g[l][r]; cout split [ l , r ] at k \n; printSplit(l, k); printSplit(k 1, r); }如果题目要求的不是输出l r k这样的三元组而是要输出类似合并时先处理的区间之类就需要根据题意调整。4.3 输出合体顺序合体顺序和分离顺序相反是从叶子到根的过程也就是要先递归处理左右子树再输出当前合并操作类似后序遍历void printMerge(int l, int r) { if (l r) return; int k g[l][r]; printMerge(l, k); printMerge(k 1, r); cout merge [ l , k ] with [ k1 , r ]\n; }还有一种常见输出是括号化表达式类似矩阵连乘的打印方式print(l, r)如果l r就输出A_l否则输出( 左子树 右子树 )。这种输出在需要展示完整二叉树结构时很实用。4.4 拿一个样例完整走一遍以a [3, 1, 5, 8]为例手动推一遍。长度 2 区间f[1][2] 3*1 3g[1][2] 1f[2][3] 1*5 5g[2][3] 2f[3][4] 5*8 40g[3][4] 3长度 3 区间f[1][3]k1时f[2][3] 3*5 5 15 20k2时f[1][2] 3*5 3 15 18。所以f[1][3] 20g[1][3] 1。f[2][4]k2时f[3][4] 1*8 40 8 48k3时f[2][3] 1*8 5 8 13。所以f[2][4] 48g[2][4] 2。长度 4 区间f[1][4]k1时f[2][4] 3*8 48 24 72k2时f[1][2] f[3][4] 24 3 40 24 67k3时f[1][3] 24 20 24 44。所以f[1][4] 72g[1][4] 1。最优值是 72。分离顺序是split [1,4] at 1 split [2,4] at 2 split [3,4] at 3合体顺序则反过来merge [3,4] merge [2,3]? // 不对看 g[2][4] 2所以先 merge [3,4] 再 merge [2,2] 和 [3,4] 得到 [2,4]最后 merge [1,1] 和 [2,4] 得到 [1,4]用printMerge输出会更清楚它会先递归[1,1]不输出递归[2,4]这里又会先递归[2,2]和[3,4]最终输出merge [3,3] and [4,4] merge [2,2] and [3,4] merge [1,1] and [2,4]这个输出正好是分离顺序的逆过程验证了前面说的分离和合体是同一棵树的两个遍历方向。5. 四边形不等式能不能用、怎么用以及我踩过的坑5.1 什么时候可以优化到 O(n^2)如果你把题目改成求最小代价比如每次分离的代价是a[l] * a[r]那转移方程就是f[l][r] min( f[l][k] f[k1][r] a[l] * a[r] )这是非常经典的满足四边形不等式的形式。因为a[l] * a[r]只依赖于区间两端和k无关并且对于正整数序列它满足区间包含单调性。这时候可以记录最优决策点g[l][r]下一轮枚举k的范围可以压缩到g[l][r-1] k g[l1][r]这样每个状态不再枚举O(n)个分割点总复杂度从O(n^3)降到O(n^2)。这个优化写起来很短但前提是你要确认题目里的w[l][r]满足决策单调性。对于最大化版本需要额外验证我建议先在本地对拍一遍不要直接套模板。优化后的核心代码长这样for (int len 2; len n; len) { for (int l 1; l len - 1 n; l) { int r l len - 1; int L g[l][r - 1]; int R g[l 1][r]; g[l][r] L; for (int k L; k R; k) { ll val f[l][k] f[k 1][r] a[l] * a[r]; if (val f[l][r]) { f[l][r] val; g[l][r] k; } } } }注意g[i][i]必须初始化为i。因为在计算长度 2 的区间[l, r]时L g[l][r-1] g[l][l]如果它是 0枚举范围就错了而且这种错误不会报运行时错误只会给出错误答案特别难查。5.2 实际调试中的几个大坑第一个坑是用int存答案。a[i] * a[j]两个int相乘结果可能直接溢出如果题目数据到了1e9级别甚至中间过程都能溢出。建议所有涉及到a[i] * a[j]的地方都转成long longf数组直接定义成long long。这是我做区间DP题踩过最多次的坑没有之一。第二个坑是递推时f[l][r]的初始值。如果题目保证收益非负初始化成 0 没问题但如果存在负权值必须初始化成-INF否则转移时用 0 去max会覆盖掉合法状态里的负数结果。很多题面不会明说数据非负你要自己看清楚。第三个坑是记忆化搜索的判重。前面提过不要用f[l][r]是否为 0 来判断而要用-1初始化和vis数组。尤其是边界状态f[i][i] 0这个词面上的没算过和算出来是 0完全不是一回事一旦混淆递归会退化到指数级。第四个坑是输出方案时递归深度。虽然次数不会太多但如果你用前序遍历输出分离树的深度是O(n)在极端数据下栈可能比较紧张。可以改成用显式栈模拟不过一般题目不会卡这个知道有这回事就行。5.3 和石子合并、能量项链放在一起学区间DP的入门三件套就是这三道题石子合并合并代价和区间内部元素和相关核心是枚举最后合并的两堆。分离与合体收益只和区间两端相关核心是理解最后一刀/最后一合的决策点。能量项链头尾标记相乘环状结构拆成二倍链。三道题放一起看你会发现它们的转移框架几乎一样都是枚举k把区间分成左右两半区别只是cost项怎么算。把分离与合体吃透之后再去做能量项链会顺很多因为环拆链、端点乘这些操作都是在同一个框架上做小改动。最后说点题外话。我最初写这道题的时候循环顺序和决策数组初始化各错了一次调了半小时才发现是g[i][i]没初始化不是 RE而是答案错得离谱特别隐蔽。后来我养成了两个习惯第一所有区间DP先用记忆化搜索把答案试出来再改递推去卡时限第二只要题目要求输出方案一定顺手开g数组别等最后再补。这个习惯帮我省了很多时间。如果你也在学区间DP建议把这道题和石子合并、能量项链放一起做做完基本就掌握这一类了。 
长河君 · 2026/10/7 1:08:40 · 阅读 1.2k 分离与合体：区间DP状态定义、转移与方案输出
第一次在题目列表里看到《分离与合体》的时候我第一反应是这题是不是要模拟什么魔法合成点进去才发现就是一个很干净的区间DP模型给你 n 个数排成一排每次可以把一个长度大于 1 的连续区间从中间切一刀分成左右两个非空区间获得左端点的数乘右端点的数的加分问所有区间都切成长度为 1 后最多能拿多少分。这类题一上来容易想歪有人去模拟切割顺序有人直接贪心其实把它和经典的石子合并放在一起看本质就是区间DP。这篇文章从状态定义、转移方程写到记忆化搜索和递推实现再讲清楚怎么输出分离和合体方案最后说说四边形不等式优化和一些常见坑适合刚学区间DP的人照着一步步写。1. 分离正向做、合体反向看先想清楚操作的本质1.1 切一刀和拼一次是互逆操作先看操作本身。假设当前有一段连续区间[l, r]你从中间某个位置k把它切成[l, k]和[k1, r]这次分离的得分是a[l] * a[r]和k具体选在哪里没关系只和这段区间两端的原始位置有关。这就很有意思了。如果倒过来看从[l, k]和[k1, r]这两个相邻区间合并成[l, r]得到的收益同样是a[l] * a[r]。所以分离和合体其实是同一件事的两个方向中间的分割点一模一样。你从完整区间一路切到单点和从单点一路合并到完整区间维护的是同一棵二叉树叶子是原始的单点每个内部节点代表一次分离或合体发生的位置。为什么这个等价性重要因为做区间DP时我们习惯从小到大算状态也就是先处理短区间再处理长区间这正是合体方向。但题目描述的是分离方向很多新手会纠结要不要倒着模拟。实际上不需要你只要把f[i][j]定义为区间[i, j]从任意状态变成最终状态能获得的最大收益就行了。分离和合体共享同一套状态和转移最后求的f[1][n]就是答案。我拿一个例子说明。比如a [3, 1, 5, 8]最优策略下第一次分离是在[1,4]的k1处切得到3*824分剩余[2,4]在k2处切得到1*88分最后[3,4]在k3处切得到5*840分总分 72。反过来看合体顺序就变成先合并[3,4]得 40再合并[2,4]得 8最后合并[1,4]得 24总分同样是 72。分数一样树的结构也一样只是遍历方向不同。1.2 为什么贪心会挂一个很自然的想法是每次找当前能获得最大收益的一刀切下去局部最优拼全局最优。听上去合理但实际上很容易翻车因为收益只和区间两端有关而两端是谁取决于之前的切割或合并形态这不是一个可以分离的贪心指标。举个例子a [5, 1, 4, 5]。这个序列无论在[1,4]的哪个位置切第一刀当前收益都是5*525看起来完全一样。但如果你第一刀切在k3接下来处理左区间[1,3]在里面切第一刀收益都是5*420这时候选k1会让[1,3]的总收益变成 24而选k2会让[1,3]的总收益变成 25一步之差整个问题的最优值就不同了。你只盯着当前最大收益去选根本没法判断哪个切口把未来引向更好的结构。这就是区间DP存在的意义把每一个可能的切割点都枚举一遍让状态自己说话。贪心只看到了当前这一步DP看到的是以当前区间为根的整棵子树。2. 状态定义与转移方程一个空位都不能差的推导2.1 状态和初始值定义f[i][j]表示区间[i, j]完全处理完后的最大收益。这里处理完可以理解为如果题目要求的是分离那就是把[i,j]全部切成单点如果题目要求的是合体那就是把[i,j]内的所有单点合并成一个区间。初始值是f[i][i] 0因为长度为 1 的区间已经不需要再操作既不能切也不能合自然没有收益。如果题目里a[i]都是正整数那么所有收益非负f数组可以初始化为 0。如果题目可能出现负数就要把所有状态初始化为-INF比如-1e18否则取max的时候会被 0 污染。大多数题解默认给的是正整数但我在做题时会习惯性判断一下数据范围里有没有负数这是个好习惯。2.2 转移方程对于区间[l, r]最后一次分离或者说最后一次合体一定发生在某个位置k上l k r。这次操作把区间分成左半部分[l, k]右半部分[k1, r]左右两半各自内部的最优收益分别是f[l][k]和f[k1][r]它们之间互不影响因为切割之后两半就成为独立的子问题。再加上当前这次切割的收益a[l] * a[r]就得到转移方程f[l][r] max( f[l][k] f[k1][r] a[l] * a[r] ) k from l to r-1这里的核心是收益只依赖整个区间[l, r]的两端和分割点k没有关系。这也是这道题和别的区间DP题最大的区别。拿石子合并对比石子合并里合并两堆的代价等于两堆石子数量之和会随着分割点变化而这题的a[l] * a[r]是固定的你只要定下区间两端不管中间怎么切这一刀的收益都不会变。为什么可以只用子问题最优值用反证法想一下。假设[l, k]内部存在一种方案收益比f[l][k]更大那我把这个方案替换进去[l, r]的总收益也会变大这就和f[l][r]已经是最优值矛盾。所以左右子区间各自取最优一定不会亏最优子结构成立。2.3 循环边界和枚举顺序转移的时候必须注意几个边界k从l遍历到r-1不能等于r否则右区间为空。len从 2 开始枚举因为长度为 1 的状态已经初始化好了。区间[l, r]必须满足l len - 1 n。这个转移的时间复杂度是O(n^3)因为状态数是O(n^2)每个状态要枚举O(n)个分割点。空间复杂度是O(n^2)。n 500的时候大概 1.25 亿次运算轻松过n 1000就到 10 亿了需要考虑优化或者换思路。3. 记忆化搜索和递推二选一我建议先写递归3.1 记忆化搜索不容易写错枚举顺序区间DP最恶心的地方不是转移方程而是循环顺序。很多新手先写for l再写for r结果发现调出来的答案总是差一点。我自己的习惯是第一版永远写记忆化搜索因为递归天然保证了子区间先计算完全不用管区间长度枚举顺序。下面是 C 的记忆化搜索写法#include bits/stdc.h using namespace std; using ll long long; const int N 505; int n; ll a[N]; ll f[N][N]; ll dfs(int l, int r) { if (l r) return 0; if (f[l][r] ! -1) return f[l][r]; ll best -1; for (int k l; k r; k) { best max(best, dfs(l, k) dfs(k 1, r) a[l] * a[r]); } return f[l][r] best; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n; for (int i 1; i n; i) cin a[i]; memset(f, -1, sizeof(f)); cout dfs(1, n) \n; return 0; }这里有个很关键的细节f[l][r]初始化为-1不是0。因为收益可能为 0比如长度为 1 的区间如果用if (f[l][r]) return f[l][r];判断长度为 1 的边界倒是没问题但某些合法状态恰好算出来是 0就会被当成没算过反复递归轻则超时重则栈溢出。3.2 递推为了常数和后续优化记忆化搜索虽然好写但常数比递推大而且某些题目特意卡递归栈深度。所以第二版我会改成递推。区间DP递推的核心规律是先枚举区间长度再枚举左端点最后枚举分割点。for (int len 2; len n; len) { for (int l 1; l len - 1 n; l) { int r l len - 1; for (int k l; k r; k) { f[l][r] max(f[l][r], f[l][k] f[k 1][r] a[l] * a[r]); } } }为什么必须按长度枚举因为你在算f[l][r]的时候需要依赖f[l][k]和f[k1][r]这两个区间的长度都小于r-l1。只有把短区间全部算完长区间才能得到正确结果。如果按for (l 1; l n; l) for (r l1; r n; r)这种顺序计算f[1][3]时可能需要f[2][3]而f[2][3]要等外层l2的时候才会被计算顺序就乱了。这类错误不会导致数组越界只会得到错误答案非常隐蔽。3.3 实际比赛里我怎么选如果n 500两种写法都行记忆化搜索多出来的递归开销完全可以接受。如果n 1000而且题目时间比较宽裕记忆化搜索可能也能过但递推更稳。如果n到 2000 以上就必须考虑四边形不等式优化或者换状态设计了。我的建议是先用记忆化搜索把思路验证清楚确保转移方程没问题再花两分钟改成递推。区间DP最怕的不是不会写转移而是转移写对了却被循环顺序坑得怀疑人生。递归版代码朴素直接递推版代码适合卡常数两个都写一遍你对这个模型的理解会深很多。4. 输出方案记录决策点把分离和合体顺序打出来很多区间DP题不是只求最大值还要求输出操作顺序。《分离与合体》这类题经常让你输出分离过程有些变种还要求输出合体过程。这个需求一点也不复杂核心就是额外开一个数组g[l][r]在更新最优值的时候记录下对应的分割点k。4.1 开一个决策数组在记忆化搜索的更新逻辑里加一行ll best -1; int bestK -1; for (int k l; k r; k) { ll val dfs(l, k) dfs(k 1, r) a[l] * a[r]; if (val best) { best val; bestK k; } } g[l][r] bestK; return f[l][r] best;注意这里用的是严格大于不是。如果用当多个分割点得到相同最优值时每次记录的都是最后一个输出方案会不稳定但也不算错。实际做题时严格大于能让方案固定下来对拍和调试都更方便。4.2 输出分离顺序分离是从大区间往小区间切所以应该先输出当前[l, r]的切割点再去递归左右两边类似前序遍历。假设题目要求每行输出一个分割操作可以这么写void printSplit(int l, int r) { if (l r) return; int k g[l][r]; cout split [ l , r ] at k \n; printSplit(l, k); printSplit(k 1, r); }如果题目要求的不是输出l r k这样的三元组而是要输出类似合并时先处理的区间之类就需要根据题意调整。4.3 输出合体顺序合体顺序和分离顺序相反是从叶子到根的过程也就是要先递归处理左右子树再输出当前合并操作类似后序遍历void printMerge(int l, int r) { if (l r) return; int k g[l][r]; printMerge(l, k); printMerge(k 1, r); cout merge [ l , k ] with [ k1 , r ]\n; }还有一种常见输出是括号化表达式类似矩阵连乘的打印方式print(l, r)如果l r就输出A_l否则输出( 左子树 右子树 )。这种输出在需要展示完整二叉树结构时很实用。4.4 拿一个样例完整走一遍以a [3, 1, 5, 8]为例手动推一遍。长度 2 区间f[1][2] 3*1 3g[1][2] 1f[2][3] 1*5 5g[2][3] 2f[3][4] 5*8 40g[3][4] 3长度 3 区间f[1][3]k1时f[2][3] 3*5 5 15 20k2时f[1][2] 3*5 3 15 18。所以f[1][3] 20g[1][3] 1。f[2][4]k2时f[3][4] 1*8 40 8 48k3时f[2][3] 1*8 5 8 13。所以f[2][4] 48g[2][4] 2。长度 4 区间f[1][4]k1时f[2][4] 3*8 48 24 72k2时f[1][2] f[3][4] 24 3 40 24 67k3时f[1][3] 24 20 24 44。所以f[1][4] 72g[1][4] 1。最优值是 72。分离顺序是split [1,4] at 1 split [2,4] at 2 split [3,4] at 3合体顺序则反过来merge [3,4] merge [2,3]? // 不对看 g[2][4] 2所以先 merge [3,4] 再 merge [2,2] 和 [3,4] 得到 [2,4]最后 merge [1,1] 和 [2,4] 得到 [1,4]用printMerge输出会更清楚它会先递归[1,1]不输出递归[2,4]这里又会先递归[2,2]和[3,4]最终输出merge [3,3] and [4,4] merge [2,2] and [3,4] merge [1,1] and [2,4]这个输出正好是分离顺序的逆过程验证了前面说的分离和合体是同一棵树的两个遍历方向。5. 四边形不等式能不能用、怎么用以及我踩过的坑5.1 什么时候可以优化到 O(n^2)如果你把题目改成求最小代价比如每次分离的代价是a[l] * a[r]那转移方程就是f[l][r] min( f[l][k] f[k1][r] a[l] * a[r] )这是非常经典的满足四边形不等式的形式。因为a[l] * a[r]只依赖于区间两端和k无关并且对于正整数序列它满足区间包含单调性。这时候可以记录最优决策点g[l][r]下一轮枚举k的范围可以压缩到g[l][r-1] k g[l1][r]这样每个状态不再枚举O(n)个分割点总复杂度从O(n^3)降到O(n^2)。这个优化写起来很短但前提是你要确认题目里的w[l][r]满足决策单调性。对于最大化版本需要额外验证我建议先在本地对拍一遍不要直接套模板。优化后的核心代码长这样for (int len 2; len n; len) { for (int l 1; l len - 1 n; l) { int r l len - 1; int L g[l][r - 1]; int R g[l 1][r]; g[l][r] L; for (int k L; k R; k) { ll val f[l][k] f[k 1][r] a[l] * a[r]; if (val f[l][r]) { f[l][r] val; g[l][r] k; } } } }注意g[i][i]必须初始化为i。因为在计算长度 2 的区间[l, r]时L g[l][r-1] g[l][l]如果它是 0枚举范围就错了而且这种错误不会报运行时错误只会给出错误答案特别难查。5.2 实际调试中的几个大坑第一个坑是用int存答案。a[i] * a[j]两个int相乘结果可能直接溢出如果题目数据到了1e9级别甚至中间过程都能溢出。建议所有涉及到a[i] * a[j]的地方都转成long longf数组直接定义成long long。这是我做区间DP题踩过最多次的坑没有之一。第二个坑是递推时f[l][r]的初始值。如果题目保证收益非负初始化成 0 没问题但如果存在负权值必须初始化成-INF否则转移时用 0 去max会覆盖掉合法状态里的负数结果。很多题面不会明说数据非负你要自己看清楚。第三个坑是记忆化搜索的判重。前面提过不要用f[l][r]是否为 0 来判断而要用-1初始化和vis数组。尤其是边界状态f[i][i] 0这个词面上的没算过和算出来是 0完全不是一回事一旦混淆递归会退化到指数级。第四个坑是输出方案时递归深度。虽然次数不会太多但如果你用前序遍历输出分离树的深度是O(n)在极端数据下栈可能比较紧张。可以改成用显式栈模拟不过一般题目不会卡这个知道有这回事就行。5.3 和石子合并、能量项链放在一起学区间DP的入门三件套就是这三道题石子合并合并代价和区间内部元素和相关核心是枚举最后合并的两堆。分离与合体收益只和区间两端相关核心是理解最后一刀/最后一合的决策点。能量项链头尾标记相乘环状结构拆成二倍链。三道题放一起看你会发现它们的转移框架几乎一样都是枚举k把区间分成左右两半区别只是cost项怎么算。把分离与合体吃透之后再去做能量项链会顺很多因为环拆链、端点乘这些操作都是在同一个框架上做小改动。最后说点题外话。我最初写这道题的时候循环顺序和决策数组初始化各错了一次调了半小时才发现是g[i][i]没初始化不是 RE而是答案错得离谱特别隐蔽。后来我养成了两个习惯第一所有区间DP先用记忆化搜索把答案试出来再改递推去卡时限第二只要题目要求输出方案一定顺手开g数组别等最后再补。这个习惯帮我省了很多时间。如果你也在学区间DP建议把这道题和石子合并、能量项链放一起做做完基本就掌握这一类了。