暴力枚举法解决环形石子合并问题
暴力枚举法解决环形石子合并问题：原理、代码与分析
一、问题引入
石子合并问题是区间动态规划的经典案例，而 “环形石子合并” 是其进阶形式：
在圆形操场的四周有 n 堆石子，每次只能合并相邻的两堆，合并得分是新堆的石子数。求将所有石子合并成一堆的最小得分和最大得分。
二、暴力枚举法的核心思路
暴力枚举法的本质是穷举所有可能的合并顺序，计算每种顺序的得分，最终取极值。
由于石子是环形排列，我们需要先将其转化为线性数组（拼接原数组，覆盖所有环形起点），再对每个线性子数组枚举所有合并顺序：
环形转线性：将原数组 stones 拼接一份（如 [4,1,2,3] → [4,1,2,3,4,1,2,3]），枚举所有长度为 n 的子数组，等价于枚举环形的所有起点。
枚举合并顺序：对每个线性子数组，递归枚举所有 “合并相邻堆” 的可能顺序，累计得分，最终记录全局最小 / 最大值。
三、C++ 代码实现（详细注释）
cpp
运行
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
// 全局变量：记录全局最小/最大得分
int global_min = INT_MAX;
int global_max = INT_MIN;
/**
* 递归暴力枚举所有合并顺序
* @param stones 当前剩余的石子堆数组
* @param current_score 当前累计的合并得分
*/
void bruteForceMerge(vector<int>& stones, int current_score) {
// 递归终止条件：只剩1堆石子，更新全局得分
if (stones.size() == 1) {
global_min = min(global_min, current_score);
global_max = max(global_max, current_score);
return;
}
// 枚举所有相邻的两堆，尝试合并
for (int i = 0; i < stones.size() - 1; ++i) {
// 1. 记录原始值（用于回溯）
int a = stones[i], b = stones[i + 1];
int merge_score = a + b; // 本次合并的得分
// 2. 原地合并：修改i位置，删除i+1位置
stones[i] = merge_score;
stones.erase(stones.begin() + i + 1);
// 3. 递归处理合并后的新数组
bruteForceMerge(stones, current_score + merge_score);
// 4. 回溯：恢复数组状态（保证其他分支的独立性）
stones.insert(stones.begin() + i + 1, b);
stones[i] = a;
}
}
int main() {
int n;
cout << "请输入石子堆数 n：";
cin >> n;
vector<int> stones(n);
cout << "请输入 " << n << " 堆石子的数量：";
for (int i = 0; i < n; ++i) {
cin >> stones[i];
}
// 环形转线性：枚举所有起点（覆盖环形的所有可能起始位置）
for (int start = 0; start < n; ++start) {
vector<int> linear_stones;
for (int i = 0; i < n; ++i) {
// 取模实现环形遍历，start为起点，i为偏移量
linear_stones.push_back(stones[(start + i) % n]);
}
// 对当前线性子数组枚举所有合并顺序
bruteForceMerge(linear_stones, 0);
}
// 输出结果
cout << "暴力枚举法最小得分：" << global_min << endl;
cout << "暴力枚举法最大得分：" << global_max << endl;
return 0;
}
四、代码运行示例
输入：
plaintext
请输入石子堆数 n：4
请输入 4 堆石子的数量：4 1 2 3
输出：
plaintext
暴力枚举法最小得分：19
暴力枚举法最大得分：26
五、暴力枚举法的优缺点分析
优点
逻辑直观：完全贴合 “合并相邻堆” 的规则，结果绝对正确，适合理解问题本质；
实现简单：无需复杂的动态规划或分治思想，仅需递归 + 枚举即可完成。
缺点
时间复杂度极高：
O(n×n!)
（n 为石子堆数），n=6 时需枚举约 720 种合并顺序，n=7 时需 5040 种，n>8 时几乎无法运行；
实用性差：仅能处理极小规模用例，无法应用于实际场景。
六、暴力法的优化方向
暴力法的核心问题是 “重复计算” 和 “阶乘级复杂度”，实际应用中需放弃暴力枚举，改用更高效的算法：
记忆化搜索：缓存 “合并区间 [i,j] 的得分”，时间复杂度降至 O(n 3)；
区间动态规划：自底向上计算区间最优解，是环形石子合并的标准最优解法，时间复杂度O(n 3 )，可处理 n≤200 的大规模用例。
七、总结
暴力枚举法是理解 “石子合并问题” 的入门方式，但其阶乘级的时间复杂度决定了它仅适用于学习阶段。实际开发中，我们通常会使用区间动态规划来解决环形石子合并问题，既保证效率，又能得到全局最优解。