能量项链问题精讲：区间DP入门与破环成链的完整推导

1. 先把题目的来龙去脉看清楚1.1 这道题到底在说什么“能量项链”这四个字对练过区间DP的人来说几乎成了条件反射一样的代名词。它来自NOIP 2006是一道非常经典的区间DP入门题。题目讲的是环形项链上的珠子合并但骨子里考的是一类非常标准的动态规划模型。很多人第一次接触区间DP就是从这道题开始的。题干不长但第一次读很容易懵。桌上有n颗珠子串成环形项链每颗珠子自带两个标记头标记和尾标记。按顺序数下去前一颗的尾标记恰好等于后一颗的头标记最后一颗的尾标记又等于第一颗的头标记。合并相邻的两颗珠子时会释放一定能量数值等于“左边珠子的头标记 × 左边珠子的尾标记 × 右边珠子的尾标记”。合并完之后会变成一颗新珠子新珠子的头标记继承左边尾标记继承右边。题目要求你安排合并顺序把n颗珠子合并成一颗让释放的总能量最大。这里有个容易忽略的输入细节题目给的不是“每颗珠子的头尾两个数”而是一个长度n的序列。比如输入2 3 5实际代表三颗珠子分别是(2,3)、(3,5)、(5,2)。第n颗珠子的尾标记要绕回来取第一个数这是环形的体现。我习惯拿三颗珠子的小例子说明合并顺序的影响。n3序列2 3 5三颗珠子是(2,3)、(3,5)、(5,2)。先合并前两颗2*3*530得到(2,5)再和(5,2)合并能量2*5*220总能量50。先合并后两颗3*5*230得到(3,2)再和(2,3)合并能量2*3*212总能量42。先合并第三颗和第一颗5*2*330得到(5,3)再和(3,5)合并能量3*5*345总能量75。三颗珠子就出现了50、42、75三种结果说明合并顺序直接决定最终能量。题目要求的就是在所有合并顺序里找一个最大值。1.2 为什么它是区间DP的经典入门题因为每次合并都是“连续两段”的合并。不管前面怎么合并最后一步一定是把两颗珠子合并成一个而这两颗珠子分别对应原环上的某一段连续区间。想求整个环的最优值本质就是要求所有可能子区间的最优值再在某个位置拼起来。这个结构天然适合区间DP。区间DP有两个核心条件最优子结构和重叠子问题。能量项链两个都满足。最优子结构体现在“区间合并的最优值由左右两个子区间的最优值决定”重叠子问题体现在大区间会反复用到同一个小区间的结果所以需要把每个区间的最优值存下来。它和“矩阵链乘”非常像。矩阵链乘是决定n个矩阵相乘时括号加在哪里每步代价是三个维度相乘能量项链是决定n颗环形珠子合并时先合并哪一段每步代价也是三个标记相乘。把矩阵链乘从链状改成环状再把每步代价从p[i]*p[k]*p[j]换成a[i]*a[k1]*a[j1]就是这道题。理解了能量项链矩阵链乘和一些变体的区间DP也就一起理解了。2. 状态定义和转移方程是怎么推出来的2.1 dp[i][j]到底存的是什么先说清楚数组a的含义。a[1]到a[n]存的是每颗珠子的头标记珠子i的尾标记等于a[i1]。这里用的是“头标记即a[i]尾标记即a[i1]”的表示法所以第n颗珠子的尾标记应该是a[1]这就有了环形的问题。后面破环成链之后这个“尾标记就是下一个位置”的性质会一直成立下标也不会绕回非常方便。定义dp[i][j]表示把第i颗到第j颗珠子这段连续区间合并成一枚珠子时能获得的最大总能量。这里的i和j是数组下标也就是从某个起点开始连续的一段珠子。单颗珠子不需要合并所以dp[i][i]0。这个状态定义很关键。很多文章里定义dp的时候会说“区间[i,j]合并得到的最大值”但没有强调这里的i和j是“珠子编号”而不是“标记编号”。如果不注意后面枚举分割点时会搞混到底是a[k]还是a[k1]。我的建议是心里始终记住“a[i]是珠子i的头标记a[i1]是珠子i的尾标记”这样转移方程怎么换都不会乱。2.2 一次合并如何抽象成三个数相乘假设当前要合并区间[i,j]最后一次合并一定发生在某个分界点k上也就是先把区间分成左半边[i,k]和右半边[k1,j]。左右两边在最后一次合并前已经分别被合并成了一颗珠子。左边这颗珠子头标记是a[i]尾标记是a[k1]。右边这颗珠子头标记是a[k1]尾标记是a[j1]。为什么要看a[k1]因为左边区间最后一个珠子编号是k它的尾标记等于a[k1]而右边区间第一颗珠子编号是k1它的头标记也正好是a[k1]。左右两颗珠子能合并就是靠这个共同的标记咬合在一起的。合并这两颗珠子释放的能量按题目规则就是左边珠子的头标记乘左边珠子的尾标记乘右边珠子的尾标记即a[i] × a[k1] × a[j1]于是整个区间[i,j]的最优值就可以写成dp[i][j] max(dp[i][k] dp[k1][j] a[i] * a[k1] * a[j1])其中k从i枚举到j-1。这个方程看起来和矩阵链乘几乎一样只是中间那个标记位置从a[k]变成了a[k1]。如果一开始用错表示法把能量项写成a[i]*a[k]*a[j]样例可能碰巧能过但换几组数据就会出错。我的经验是每次写转移方程前都在草稿纸上画三颗珠子的合并过程把左右两个珠子的头尾标记标出来这样能避免很多低级错误。2.3 转移方程写成代码长什么样区间DP的代码套路非常固定三层循环第一层枚举区间长度第二层枚举区间起点第三层枚举分割点。for (int len 2; len n; len) { for (int i 1; i len - 1 2 * n; i) { int j i len - 1; for (int k i; k j; k) { dp[i][j] max(dp[i][j], dp[i][k] dp[k 1][j] a[i] * a[k 1] * a[j 1]); } } }这里有几个细节要先讲清楚。第一len为什么要从2开始因为len1的区间只有一颗珠子不需要合并dp[i][i]0已经初始化过了。第二k为什么要从i枚举到j-1因为分割点左边至少要有一颗珠子右边也至少要有一颗珠子如果kj右边区间就空了没有意义。第三为什么dp[i][k]和dp[k1][j]一定已经算好了因为左右两个子区间的长度都比当前区间len小外层循环从小到大枚举len所以更短的区间一定被先计算过。这个三层循环的复杂度是O(n³)n100时大概一百万次操作非常快。后面的代码实现阶段我们会在这个框架上补上环形处理就能得到完整可跑的版本。3. 环形结构破环成链的完整思路3.1 环为什么要拆成链如果题目给的是一个普通的链状珠子序列区间DP直接做就行dp[1][n]就是答案。但项链是首尾相接的最优解可能从任意一颗珠子开始第一颗和第n颗之间也存在合并关系。如果直接拿原数组做区间DP相当于默认第一颗和第n颗之间不能合并这显然不对。一个朴素思路是枚举断点把环形项链从某个位置剪开变成一条链每次做一次链状区间DP最后取最大值。这个思路很直白但复杂度会变成O(n⁴)。n100时虽然也能跑但代码要套外层循环不太优雅。更常用的处理方式是“破环成链”本质是把环复制一份展开成一个长度为2n的链。这样所有可能的“环形区间”都能在这个长链上表示为一段普通连续区间一次DP就能覆盖所有断点的情况。3.2 复制一份数组之后边界怎么算破环成链的实现很简单把原数组a[1..n]复制到a[n1..2n]让每个位置i都满足a[in]a[i]。这样原环上任意一段连续珠子都能在长度为2n的链上找到一个等长的连续区间。比如原环从第5颗珠子开始绕一整圈回到第4颗在复制后的数组上就对应区间[5, n4]。所有长度为n的窗口也就是[i, in-1]其中i从1到n正好对应环形项链的所有可能断点。这里有一个边界的坑。当我们枚举到区间终点j时转移方程里会用到a[j1]。如果j正好是2n那a[j1]就是a[2n1]这个位置在复制后的数组里并不存在。为了避免越界可以在复制完数组后额外执行一句a[2 * n 1] a[1];因为第2n颗珠子对应原排列里的第n颗它的尾标记按环形规则应该是原序列第1颗珠子的头标记也就是a[1]。补齐这个位置后代码就可以放心地访问a[j1]了。3.3 最终答案为什么要枚举所有断点取max很多新手做完区间DP后直接输出dp[1][n]然后发现样例能过一提交就错。原因很简单dp[1][n]只是从第1颗珠子作为起点、绕一圈回到第n颗的那一种断开方式而环形项链并没有规定第1颗珠子是起点。举个例子三颗珠子的输入2 3 5前面算过最优顺序是先合并第三颗和第一颗这种情况在链状数组的原始区间[1,3]里并没有被完整考虑因为合并第三颗和第一颗本质上相当于从第3颗断开。所以最终答案应该枚举所有长度为n的窗口取最大值long long ans 0; for (int i 1; i n; i) { ans max(ans, dp[i][i n - 1]); }理解了这个“枚举所有断点取max”的过程环形区间DP的核心就掌握了。以后遇到任何环上的区间合并问题都可以用同一种思路处理。4. 完整代码与关键实现细节4.1 可以直接跑的C代码把前面的推导拼起来就是一份非常标准的能量项链题解代码。我习惯把数组大小开成2*n5留出余量避免边界问题。#include bits/stdc.h using namespace std; const int MAXN 110; int n; int a[MAXN * 2 5]; long long dp[MAXN * 2 5][MAXN * 2 5]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n; for (int i 1; i n; i) { cin a[i]; a[i n] a[i]; } a[2 * n 1] a[1]; // 补上最后一个环形边界防止a[j1]越界 long long ans 0; for (int len 2; len n; len) { for (int i 1; i len - 1 2 * n; i) { int j i len - 1; for (int k i; k j; k) { long long cur dp[i][k] dp[k 1][j] 1LL * a[i] * a[k 1] * a[j 1]; if (cur dp[i][j]) dp[i][j] cur; } if (len n i n) { ans max(ans, dp[i][j]); } } } cout ans \n; return 0; }代码思路是先读入数组并复制一份然后按区间长度从小到大做DP。每次更新ans只取i n的位置因为i从n1到2n的那些长度为n的窗口本质上和前面某些窗口是同一组珠子不需要重复计入答案。如果不想在循环里判断len n也可以改成分段写法for (int len 2; len n; len) { for (int i 1; i len - 1 2 * n; i) { // 转移 } } for (int i 1; i n; i) { ans max(ans, dp[i][i n - 1]); }两种写法都对第二种逻辑更清晰我平时更推荐用它。4.2 数组大小、越界和初值问题先聊数组大小。n最大取100复制之后需要访问到a[2n1]所以数组至少要开205。有的代码喜欢用MAXN100然后开a[205]这没问题。我习惯在声明数组时直接写成a[2 * MAXN 5]这样不管MAXN怎么改都不会越界。dp数组的大小也很关键。因为复制后区间下标可以去到2n所以dp至少要开[2n1][2n1]。有的新手只开[105][105]一运行就数组越界表现是本地跑小样例正常数据一大就崩溃或答案错乱。再说初值。dp是全局变量自动初始化为0。对这道题来说初始化为0是合适的因为合并能量全为正整数dp[i][i]0而所有长度大于1的区间最终都会被更大的正数覆盖。如果你有洁癖也可以用memset(dp, 0, sizeof(dp))明确初始化。最后提一下类型。能量三项相乘最大不会超过100 × 100 × 100 1,000,000总共合并99次总能量约1e8用int其实也放得下。但在竞赛里养成开long long的习惯更稳妥尤其是以后做类似题时数据范围可能变大提前用long long能避免很多不必要的调试时间。5. 常见错误与调试记录5.1 我见过最多的几个翻车点区间DP的代码结构其实不难但“小错不断”是常态。我把常见的翻车点整理成了下面这张表错误写法错误后果正确做法不处理环形直接dp[1][n]当答案最优解如果从其他位置断开就直接算错破环成链并枚举所有长度为n的窗口数组只开到n复制后访问n1位置越界开到2n5并补上a[2n1]枚举len从1开始单颗珠子也被进入转移语义混乱len从2开始len上限写成2n会重复合并同一颗珠子状态非法len上限是n转移方程写a[i]*a[k]*a[j1]下标偏移错误大数据下答案不稳理解“尾标记下一个头标记”后写a[k1]用int存答案万一数据范围变化容易溢出用long long这里面最隐蔽的是转移方程的下标偏移。很多人在做矩阵链乘时习惯写p[i]*p[k]*p[j]转到能量项链时顺手就写成a[i]*a[k]*a[j]。如果样例恰好比较弱可能发现不了问题但一换复杂数据就出错。我的建议是每次写转移方程都回看一遍状态定义dp[i][j]代表区间[i,j]分割点是k那么三个乘数分别是区间左端的头标记a[i]、连接处的标记a[k1]、区间右端的尾标记a[j1]。这三个位置在代码里是自洽的。5.2 一个实用的自测小套路区间DP的转移方程写对了之后剩下的主要风险是边界和环形处理。我建议比赛前用两种方法自测。第一种是暴力对拍。n比较小的时候用DFS枚举所有合并顺序算出真实最大值再和DP结果对比。具体思路是在DFS中维护一个当前珠子序列每次枚举相邻两颗珠子合并递归下去合并到只剩一颗时更新答案。n8时这种暴力能跑得很轻松n10也勉强可以。如果暴力结果和DP结果不一致说明状态定义或转移方程有问题。第二种是打印DP表。把len较小时的dp值手工算一遍和程序输出对照。比如输入2 3 5len2的dp值应该分别是30、30、30len3的dp最大值应该是75。如果某个值和手算不一样就定位到具体的区间和分割点检查是下标还是边界的问题。这两种方法配合起来基本能覆盖所有常见错误。我学习阶段写很多区间DP题都会用这个流程排查效率很高。6. 从能量项链延伸到一类区间DP6.1 同门师兄弟石子合并和矩阵链乘能量项链不是孤例它和好几道经典题共享同一套状态设计和转移框架。我把最常拿来对比的三道题列在一起题目数据形态合并代价环形处理石子合并链或环合并相邻石子堆两堆石子数量之和常规版是链环形版要复制数组矩阵链乘链给n个矩阵维度p[i]*p[k]*p[j]不用处理链状直接做能量项链环给珠子头标记序列a[i]*a[k1]*a[j1]复制数组枚举全部断点石子合并的转移通常是dp[i][j] 合并代价矩阵链乘是dp[i][k] dp[k1][j] p[i]*p[k]*p[j]能量项链是dp[i][k] dp[k1][j] a[i]*a[k1]*a[j1]。可以看出外层结构完全一样变的只是合并代价的计算方式。所以这道题做熟了后面再遇到区间合并模型的新题核心思路基本能直接迁移。6.2 一眼识别区间DP题的几个信号很多人拿到新题不知道自己该不该用区间DP我自己的判断清单是这样的操作对象是一段连续序列比如石子堆、珠子串、括号串、数组片段。操作是合并或切分相邻两部分合并的结果会影响后续决策。目标是最大化或最小化某种总代价而且局部合并的代价能明确计算。数据范围在n≤100到n≤500左右O(n³)复杂度在时限内能过。如果一道题命中三到四条基本可以优先往区间DP方向想。比如常见的括号匹配计数、字符串折叠压缩、多边形剖分等问题很多都能套用这套状态框架。熟练之后看到“合并相邻”和“求最优值”这两个词反应就会快很多。6.3 后续还能往哪走四边形不等式与记忆化搜索能量项链这道题n只有100O(n³)足够。但同样模型的题目如果n上限变成1000或5000O(n³)就会超时这时候可以用四边形不等式优化。只要合并代价满足四边形不等式和区间单调性分割点k的最优位置会随区间单调移动可以用opt[i][j-1]到opt[i1][j]的范围限制枚举复杂度降到O(n²)。代价函数a[i]*a[k1]*a[j1]是否满足条件要看具体数据很多区间DP题都满足值得了解。如果觉得循环写法容易绕也可以换记忆化搜索。dfs(i,j)表示合并区间[i,j]的最大能量每次枚举k递归左右两边加上记忆化去重。代码更贴近直觉不容易在枚举边界上出错缺点是有函数递归开销但对n100以内的题完全没问题。long long dfs(int l, int r) { if (l r) return 0; if (mem[l][r] ! -1) return mem[l][r]; long long res 0; for (int k l; k r; k) { res max(res, dfs(l, k) dfs(k 1, r) 1LL * a[l] * a[k 1] * a[r 1]); } return mem[l][r] res; }这个版本在理解转移方程之后几乎是顺理成章适合做不出递推顺序时兜底。我个人在实际操作中的体会是能量项链这道题最值得反复咀嚼的地方不在于代码本身而在于“环拆成链”这个思维习惯。我第一次写的时候就是直接输出dp[1][n]样例跑得很漂亮换个数据就翻车。后来才意识到问题出在环形项链的“起点”并不固定。从此以后看到任何环上的合并DP我的第一反应都是复制数组、枚举窗口、取最大值。这道题练熟之后区间DP的整体手感会好很多后面再遇到矩阵链乘、石子合并的变体基本就是换个代价函数的事。