深圳市网站建设_网站建设公司_展示型网站_seo优化

在算法领域，石子合并问题是动态规划的经典应用场景，而圆形（环形）排列的变体更是因其边界特殊性成为面试与竞赛中的高频考点。本文将从线性石子合并入手，拆解环形问题的核心难点，详解“断环成链”的解题套路，并附上完整代码实现，帮你彻底掌握这一题型。

一、问题描述

有N堆石子以圆形操场为载体首尾相连排列，每堆石子有固定数量。规定每次只能合并相邻的两堆石子，合并后新堆的石子数即为该次合并的得分。要求通过合理规划合并顺序，计算出将所有石子合并成一堆的最小得分和最大得分 。

二、核心思路：从线性到环形的转化

1. 线性石子合并：动态规划基础

在解决环形问题前，先回顾更简单的线性石子合并（石子排成一排），其核心逻辑是动态规划的区间DP思想：

- 状态定义：设 dp[i][j] 表示合并第i堆到第j堆石子的最小（或最大）得分。
- 状态转移：合并区间 [i,j] 时，必然存在一个分割点k（i≤k<j），先合并 [i,k] 和 [k+1,j] ，再合并这两部分。转移方程为：
plaintext

dp[i][j] = min/max(dp[i][k] + dp[k+1][j] + sum(i,j))


其中 sum(i,j) 是区间 [i,j] 的石子总数，可通过前缀和数组 pre 快速计算： sum(i,j) = pre[j] - pre[i-1] 。
- 遍历顺序：必须按区间长度L（从2到N）枚举，再枚举起点i，计算终点j=i+L-1，确保计算大区间时小区间已完成更新 。

2. 环形问题的关键：断环成链

环形与线性的核心区别是首尾相邻，合并时需考虑“第N堆与第1堆相邻”的特殊情况。解决思路是“断环成链”——将环形数组展开为长度为2N的线性数组，其中前N个元素为原数组，后N个元素重复原数组内容 。

例如原数组 [a1,a2,a3] ，展开后为 [a1,a2,a3,a1,a2,a3] 。此时，任意长度为N的连续子区间（如 [a3,a1,a2] ）都对应环形的一种“断环”方式。我们只需在展开后的数组上计算所有长度为N的区间的最小/最大得分，即可得到原环形问题的答案。

三、完整实现步骤

1. 数据预处理

- 读取N堆石子的数量，存储在数组 a 中（下标从1开始）。
- 构建前缀和数组 pre ，其中 pre[0]=0 ， pre[i] = pre[i-1] + a[(i-1)%N + 1] （适配展开后的数组）。

2. 动态规划数组初始化

- 定义 min_dp[i][j] 存储区间 [i,j] 的最小合并得分， max_dp[i][j] 存储最大得分。
- 初始化：当区间长度为1时（i=j），合并得分为0（无需合并），即 min_dp[i][i] = max_dp[i][i] = 0 。

3. 区间DP遍历

- 枚举区间长度L（从2到N，代表当前合并的堆数）。
- 枚举起点i（从1到2N-L+1，确保终点j=i+L-1不超过2N）。
- 计算终点j = i + L - 1，遍历分割点k（从i到j-1），更新状态转移方程：
plaintext

sum = pre[j] - pre[i-1]
min_dp[i][j] = min(min_dp[i][j], min_dp[i][k] + min_dp[k+1][j] + sum)
max_dp[i][j] = max(max_dp[i][j], max_dp[i][k] + max_dp[k+1][j] + sum)


4. 计算最终结果

- 遍历所有长度为N的区间起点i（从1到N），最终答案为：
- 最小得分： min(min_dp[i][i+N-1]) （i=1~N）
- 最大得分： max(max_dp[i][i+N-1]) （i=1~N）

四、C++完整代码

cpp

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 410; // 2*200，适配N≤200的情况

int main() {
int n;
cin >> n;
int a[MAXN], pre[MAXN] = {0};
for (int i = 1; i <= n; ++i) {
cin >> a[i];
a[i + n] = a[i]; // 断环成链，展开为2n长度
}
// 计算前缀和
for (int i = 1; i <= 2 * n; ++i) {
pre[i] = pre[i - 1] + a[i];
}

int min_dp[MAXN][MAXN], max_dp[MAXN][MAXN];
memset(min_dp, INF, sizeof(min_dp));
memset(max_dp, 0, sizeof(max_dp));
// 初始化单个区间
for (int i = 1; i <= 2 * n; ++i) {
min_dp[i][i] = 0;
max_dp[i][i] = 0;
}

// 枚举区间长度L（合并的堆数）
for (int L = 2; L <= n; ++L) {
// 枚举起点i
for (int i = 1; i + L - 1 <= 2 * n; ++i) {
int j = i + L - 1; // 终点
// 枚举分割点k
for (int k = i; k < j; ++k) {
int sum = pre[j] - pre[i - 1];
min_dp[i][j] = min(min_dp[i][j], min_dp[i][k] + min_dp[k + 1][j] + sum);
max_dp[i][j] = max(max_dp[i][j], max_dp[i][k] + max_dp[k + 1][j] + sum);
}
}
}

// 查找所有长度为n的区间的最小/最大值
int min_res = INF, max_res = 0;
for (int i = 1; i <= n; ++i) {
min_res = min(min_res, min_dp[i][i + n - 1]);
max_res = max(max_res, max_dp[i][i + n - 1]);
}

cout << "最小得分：" << min_res << endl;
cout << "最大得分：" << max_res << endl;
return 0;
}


五、复杂度分析与注意事项

- 时间复杂度：O(N³)，其中N为石子堆数。三层循环分别对应区间长度、起点、分割点，在N≤200时效率足够。
- 空间复杂度：O(N²)，用于存储动态规划数组和前缀和数组。
- 注意事项：展开数组时需确保长度为2N，避免边界越界；初始化 min_dp 时需设为无穷大， max_dp 设为0，保证状态转移的正确性。

六、总结

环形石子合并的核心是“断环成链”，将环形问题转化为熟悉的线性区间DP问题，再通过前缀和优化区间和计算，最终高效求解最小和最大得分。这一“转化思想”不仅适用于石子合并，还可迁移到环形排列的其他动态规划问题中（如环形最大子数组和）。

建议结合线性石子合并问题对比练习，重点体会“断环”的合理性与区间DP的遍历顺序逻辑。如果需要针对特定N值的测试用例调试，或想了解优化O(N³)复杂度的四边形不等式技巧，欢迎留言交流！