圆形石子合并问题

在算法设计中，圆形石子合并问题是经典的动态规划应用场景之一。本文将详细讲解该问题的解法，并用 C++ 实现 3 种不同算法，最后对比它们的优劣。

一、问题描述

在圆形操场周围有n堆石子，每次只能合并相邻的 2 堆，合并得分是新堆的石子数。求将所有石子合并为 1 堆的最小得分和最大得分。

二、算法 1：基础动态规划（环形转线性）

思路

圆形结构可通过复制数组转化为线性结构（长度为2n），再用区间 DP 求解：

• 定义dp_min[i][j]：合并区间[i,j]的最小得分
• 定义dp_max[i][j]：合并区间[i,j]的最大得分
• 状态转移：dp_min[i][j]=min(dp_min[i][k]+dp_min[k+1][j])+sum(i,j)(i≤k<j)dp_max[i][j]=max(dp_max[i][k]+dp_max[k+1][j])+sum(i,j)(i≤k<j)
• sum(i,j)是区间[i,j]的石子总数（用前缀和快速计算）

C++ 代码

#include <iostream> #include <vector> #include <climits> using namespace std; // 计算前缀和 vector<int> getPrefixSum(const vector<int>& arr) { vector<int> pre(arr.size() + 1, 0); for (int i = 0; i < arr.size(); ++i) { pre[i+1] = pre[i] + arr[i]; } return pre; } // 区间[i,j]的和（基于前缀和） int getSum(const vector<int>& pre, int i, int j) { return pre[j+1] - pre[i]; } pair<int, int> stoneMergeDP(vector<int> stones) { int n = stones.size(); if (n == 1) return {0, 0}; // 环形转线性：复制数组 vector<int> arr = stones; arr.insert(arr.end(), stones.begin(), stones.end()); vector<int> pre = getPrefixSum(arr); int len = 2 * n; vector<vector<int>> dp_min(len, vector<int>(len, 0)); vector<vector<int>> dp_max(len, vector<int>(len, 0)); // 枚举区间长度（从2到n） for (int l = 2; l <= n; ++l) { for (int i = 0; i + l <= len; ++i) { int j = i + l - 1; dp_min[i][j] = INT_MAX; dp_max[i][j] = INT_MIN; // 枚举分割点 for (int k = i; k < j; ++k) { int sum = getSum(pre, i, j); dp_min[i][j] = min(dp_min[i][j], dp_min[i][k] + dp_min[k+1][j] + sum); dp_max[i][j] = max(dp_max[i][j], dp_max[i][k] + dp_max[k+1][j] + sum); } } } // 遍历所有长度为n的区间，取最小/最大值 int min_res = INT_MAX, max_res = INT_MIN; for (int i = 0; i < n; ++i) { min_res = min(min_res, dp_min[i][i + n - 1]); max_res = max(max_res, dp_max[i][i + n - 1]); } return {min_res, max_res}; } int main() { vector<int> stones = {4, 1, 2, 3}; // 测试用例 auto [min_score, max_score] = stoneMergeDP(stones); cout << "最小得分：" << min_score << endl; cout << "最大得分：" << max_score << endl; return 0; }

三、算法 2：贪心算法（仅适用于链形 + 特殊条件）

思路

贪心算法仅在链形结构 + 石子数非递减 / 非递增时有效（圆形结构不适用），核心是：

• 最小得分：每次合并最小的相邻两堆（类似哈夫曼编码）
• 最大得分：每次合并最大的相邻两堆

C++ 代码（链形场景）

#include <iostream> #include <vector> #include <queue> using namespace std; // 贪心求最小得分（链形） int greedyMin(vector<int> stones) { priority_queue<int, vector<int>, greater<int>> pq(stones.begin(), stones.end()); int res = 0; while (pq.size() > 1) { int a = pq.top(); pq.pop(); int b = pq.top(); pq.pop(); res += a + b; pq.push(a + b); } return res; } // 贪心求最大得分（链形） int greedyMax(vector<int> stones) { priority_queue<int> pq(stones.begin(), stones.end()); int res = 0; while (pq.size() > 1) { int a = pq.top(); pq.pop(); int b = pq.top(); pq.pop(); res += a + b; pq.push(a + b); } return res; } int main() { vector<int> stones = {4, 1, 2, 3}; // 链形测试用例 cout << "链形最小得分（贪心）：" << greedyMin(stones) << endl; cout << "链形最大得分（贪心）：" << greedyMax(stones) << endl; return 0; }

四、算法 3：记忆化搜索（递归 + 缓存）

思路

基于基础 DP 的递归实现，用记忆化缓存避免重复计算，逻辑与基础 DP 一致，但代码更简洁。

C++ 代码

#include <iostream> #include <vector> #include <climits> #include <unordered_map> using namespace std; vector<int> pre; vector<vector<int>> memo_min, memo_max; int n; int dfs_min(int i, int j) { if (i == j) return 0; if (memo_min[i][j] != -1) return memo_min[i][j]; int res = INT_MAX; for (int k = i; k < j; ++k) { int sum = pre[j+1] - pre[i]; res = min(res, dfs_min(i, k) + dfs_min(k+1, j) + sum); } return memo_min[i][j] = res; } int dfs_max(int i, int j) { if (i == j) return 0; if (memo_max[i][j] != -1) return memo_max[i][j]; int res = INT_MIN; for (int k = i; k < j; ++k) { int sum = pre[j+1] - pre[i]; res = max(res, dfs_max(i, k) + dfs_max(k+1, j) + sum); } return memo_max[i][j] = res; } pair<int, int> stoneMergeMemo(vector<int> stones) { n = stones.size(); if (n == 1) return {0, 0}; vector<int> arr = stones; arr.insert(arr.end(), stones.begin(), stones.end()); pre.resize(arr.size() + 1, 0); for (int i = 0; i < arr.size(); ++i) { pre[i+1] = pre[i] + arr[i]; } memo_min.assign(2*n, vector<int>(2*n, -1)); memo_max.assign(2*n, vector<int>(2*n, -1)); int min_res = INT_MAX, max_res = INT_MIN; for (int i = 0; i < n; ++i) { min_res = min(min_res, dfs_min(i, i + n - 1)); max_res = max(max_res, dfs_max(i, i + n - 1)); } return {min_res, max_res}; } int main() { vector<int> stones = {4, 1, 2, 3}; auto [min_score, max_score] = stoneMergeMemo(stones); cout << "最小得分（记忆化）：" << min_score << endl; cout << "最大得分（记忆化）：" << max_score << endl; return 0; }

五、算法优劣对比

六、总结

圆形石子合并问题的最优解法是基础动态规划（或记忆化搜索），贪心算法仅适用于特殊场景。实际应用中，若n较大（如n>100），需优化 DP（如四边形不等式优化，时间复杂度可降为 O(n2)）。