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