LeetCode 补充题 170. 环形能量项链的最优合并
题目描述
牛客原题： ✅ 补充题 170. 环形能量项链的最优合并
给定环形项链的头标记数组
marks。第i颗珠子的头标记为marks[i]，尾标记为下一颗的头标记，最后一颗接第一颗。合并相邻珠子
(m,r)与(r,n)会释放m×r×n的能量。合并到只剩一颗珠子，求最大总能量，再对1000000007取模。
示例 1：
输入：
marks = [2,3,5,10]
输出：710
解释： 先合并 (10,2) 与 (2,3) 得 60，再与 (3,5) 合并得 150，最后与 (5,10) 合并得 500，总能量为 710。
提示：
-
n≤100，标记值不超过1000。 - 仅合并相邻珠子，首尾也相邻。
- 先求真实最大总能量，再对
1000000007取模。
题意分析
合并顺序会改变中间标记参与乘积的方式，局部能量最大不保证总能量最大。选择最后一次合并时，它两侧的合并过程彼此独立，因此适合区间动态规划；环形结构再通过复制数组覆盖各断点。
解法：复制环并枚举最后合并位置
核心思路
[!blue]
珠子区间
[l,r]合并后只保留头标记a[l]和尾标记a[r+1]。设dp[l][r]为把该区间合成一颗的最大能量，单颗珠子无需合并，初值为 0。若最后在
k处分开两部分，它们已经分别变成(a[l],a[k+1])与(a[k+1],a[r+1])，最后释放的能量就是三个标记的乘积。枚举l <= k < r，取左右最优值加该乘积的最大值，按区间长度递增计算。复制环上标记并多留一个尾标记，使所有长度为
n的断环窗口都可表示。取这些窗口的最大真实值后才取模；提前取模会改变大小关系。给定范围下至多n-1次合并，每次乘积不超过1000³，64 位足够。
解题步骤
- 复制一遍环标记，保留 r+1 所需的额外末端标记。
- 按长度递增枚举最多 n 颗珠子的区间。
- 枚举最后一次合并点，比较左右最优值加三标记乘积。
- 从所有长度 n 的窗口中取真实最大值，最后才取模。
代码实现
class Solution {
public long necklace(int[] values) {
int n = values.length;
int[] a = new int[2 * n + 1];
for (int i = 0; i < a.length; i++) {
a[i] = values[i % n];
}
long[][] dp = new long[2 * n][2 * n];
for (int len = 2; len <= n; len++) {
for (int l = 0; l + len <= 2 * n; l++) {
int r = l + len - 1;
for (int k = l; k < r; k++) {
dp[l][r] =
Math.max(
dp[l][r],
dp[l][k] + dp[k + 1][r] + (long) a[l] * a[k + 1] * a[r + 1]);
}
}
}
long answer = 0;
for (int l = 0; l < n; l++) {
answer = Math.max(answer, dp[l][l + n - 1]);
}
return answer % 1_000_000_007;
}
}
func necklace(values []int) int64 {
n := len(values)
a := make([]int64, 2*n+1)
for i := range a {
a[i] = int64(values[i%n])
}
dp := make([][]int64, 2*n)
for i := range dp {
dp[i] = make([]int64, 2*n)
}
for length := 2; length <= n; length++ {
for l := 0; l+length <= 2*n; l++ {
r := l + length - 1
for k := l; k < r; k++ {
dp[l][r] = max(dp[l][r], dp[l][k]+dp[k+1][r]+a[l]*a[k+1]*a[r+1])
}
}
}
answer := int64(0)
for l := 0; l < n; l++ {
answer = max(answer, dp[l][l+n-1])
}
return answer % 1_000_000_007
}
复杂度分析
- 时间复杂度：$O(n^3)$。
- 空间复杂度：额外空间 $O(n^2)$。
关键点总结
[!green]
先决定最后一次合并，剩下两侧才是独立子问题；不同断环位置都要覆盖，取模不能改变最大值比较顺序。
易错点总结
[!yellow]
不能在取最大值之前把DP对模数取余；按原题范围，总能量小于100×1000³，long足够。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 312. 戳气球 | 困难 | 同样倒过来枚举最后一步，使两侧子区间独立，并由边界与分割点计算乘积贡献。 |
| 1039. 多边形三角剖分的最低得分 | 中等 | 都使用三处标记乘积作为区间划分代价，原题最小化，本题最大化且需枚举环的断点。 |