1. 暴力递归

有 n 堆石子排成一行，第 i 堆有 a[i] 个石子。每次只能合并相邻的两堆，合并代价为两堆石子数量之和。求合并成一堆的最小总代价。

首先考虑暴力算法，第一次合并的时候选择任意两堆合并，有n-1种选择方案，合并完成之后，总的石子数量为n-1堆，假如有5堆石子，任意选择相邻的两个合并

合并	0,1	1,2	2,3	3,4
剩余	2,3,4	0,3,4	0,1,4	0,1,2

第二次合并的时候就有n-2种合并方案，假如第一次选择合并1,2，剩下了0,[12],3,4，那么第二次合并的方案就有

合并	0,[12]	[12],3	3,4
剩余	3,4	0,4	0,[12]

总之合并完的方案有(n-1)*(n-2)*(n-3)...*2*1=(n-1)!种方案，我们从这些方案里面选择一个代价最小的方案。

看到后面才知道，原来不是n-1的阶乘方案，而是一种叫做卡特兰数的东西

暴力解决方案本质就是一种多叉树的划分，最终就是当前树的代价=子树的代价+当前合并的代价

def dfs(arr):
    n = len(arr)
    # 只有一堆石子则返回0（无需合并，代价为0）
    if n == 1:
        return 0
    min_val = float('inf')
    for i in range(1, n):
        # 计算当前合并的代价
        merge_cost = arr[i-1] + arr[i]
        # 生成新的石子数组,移除原两堆，插入合并后的新堆
        new_arr = arr[:i-1] + [merge_cost] + arr[i+1:]
        # 递归计算剩余石子的合并代价，加上当前代价
        total_cost = merge_cost + dfs(new_arr)
        # 更新最小值
        if total_cost < min_val:
            min_val = total_cost
    return min_val

# 示例测试
stones = [3, 4, 5, 6]
print("最小合并代价：", dfs(stones))  # 输出：36

2. 集合划分

所有合并方案（(n-1)! 种）可以按 “最后一次合并的位置” 划分成 n-1 个不重复的集合：
集合 Sₖ(k=1,2,...,n-1)：最后一次合并的是 “前 k 堆合并的结果” 和 “后 n-k 堆合并的结果”。这些集合完全不重复，且覆盖所有方案（任何方案的最后一步必然对应某个 k）。

按‘最终合并边界’这个唯一特征，给所有‘中间过程不同但最终边界相同’的方案‘贴标签’” —— 不管中间合并步骤多复杂，只要最终那一步的边界一致，就归为同一类，这正是它能覆盖所有方案且不重复的关键

我们用 n=5 堆石子 [a, b, c, d, e] 为例，按 “最后一次合并的位置” 划分集合。所有合并方案最终都会归于以下 4 个集合（因为 n=5 需合并 4 次，最后一次合并有 4 种可能的拆分方式）：
集合划分规则
最后一次合并是指 “将所有石子最终合并成一堆的那一步”，此时必然是将左侧 k 堆的合并结果与右侧 5-k 堆的合并结果合并（k=1,2,3,4）。

1. 集合 S₁：最后合并 [a] 和 [b,c,d,e]

• 含义：最后一步是将单独的 a 与 [b,c,d,e] 合并（左侧 1 堆，右侧 4 堆）。
• 包含的所有方案的共同点：
  无论 [b,c,d,e] 内部如何合并（比如先合 b&c，再合 d&e 等），最终都要和 a 做最后一次合并。

2. 集合 S₂：最后合并 [a,b] 和 [c,d,e]

• 含义：最后一步是将 [a,b] 的合并结果与 [c,d,e] 的合并结果合并（左侧 2 堆，右侧 3 堆）。
• 包含的所有方案的共同点：
  [a,b] 内部可以先合并（代价 a+b），[c,d,e] 内部可以任意合并（比如先合 c&d 或 d&e），但最后一步必须是这两部分合并。

3. 集合 S₃：最后合并 [a,b,c] 和 [d,e]

• 含义：最后一步是将 [a,b,c] 的合并结果与 [d,e] 的合并结果合并（左侧 3 堆，右侧 2 堆）。
• 包含的所有方案的共同点：
  [a,b,c] 内部可任意合并（比如先合 a&b 或b&c），[d,e] 内部先合并（代价 d+e），最后一步是这两部分合并。

4. 集合 S₄：最后合并 [a,b,c,d] 和 [e]

• 含义：最后一步是将 [a,b,c,d] 的合并结果与单独的 e 合并（左侧 4 堆，右侧 1 堆）。
• 包含的所有方案的共同点：
  无论 [a,b,c,d] 内部如何合并，最终都要和 e 做最后一次合并。

总结

n=5 时，所有合并方案（共 4! = 24 种）被不重复地划分为 S₁~S₄ 四个集合。
每个集合的最小代价由 “左侧子问题的最小代价 + 右侧子问题的最小代价 + 总石子和” 计算。
全局最小代价 = min(S₁的最小值, S₂的最小值, S₃的最小值, S₄的最小值)。

这样划分的核心是：无论中间步骤如何合并，最终一步必然是 “左右两大块合并”，因此按这两大块的边界划分，就能覆盖所有可能的方案。

3. 集合划分思考

这里集合划分我总是不理解，总感觉最后合并的时候已经没有所谓的边界了，因为石子在不断的合并过程中已经变成了一堆石子，没有了原有的边界。但是当我把合并过程画出来的时候，恍然大悟。石子确实两两合并在一起了，新的石子堆数都发生了变化，跟原来的肯定不同了。但是这里说的边界是最原始的那个合并边界。假如我有abcdefgh这8堆石子，先合并ab,cd,ef,gh，假如我给新的石子起名为j,k,l,m，然后再对这个新石子合并，例如jk,lm，又变成了一个新的石子堆，这个时候完全就看不出原来的边界，就会觉得非常奇怪，但是如果我们不重新命名，例如ab合并的新堆叫做[ab]，cd合并的新堆叫做[c,d]，ef合并的新堆叫做[e,f]，gh合并的新堆叫做[gh]，然后再两两合并，例如[ab]和[cd]合并成新堆[abcd],[ef],[gh]，然后再进行合并成[abcd],[efgh]或者[abcdef],[gh]，就可以看到最后合并的边界了

“不重新命名、保留原始范围” 的发现，直接戳中了集合划分的核心本质！很多人卡壳就是因为默认把合并后的新堆 “重新命名”（比如 j、k、l、m），丢失了和原始石子的关联 —— 而你意识到 “用原始范围标记新堆”，其实就是把 “边界” 牢牢锚在了原始石子的索引上，这一下就把 “看似消失的边界” 拉回来了。

咱们用你 8 堆石子（a-h 对应原始索引 0-7）的例子，把这个逻辑扒得更透，你会发现 “边界从未消失，只是需要用原始索引标记”：

第一步：合并后的 “新堆”，本质是 “原始石子的集合”

“不重新命名”，其实是给每个新堆贴了 “原始范围标签”—— 这个标签就是边界的 “身份证”：

• 合并 a&b（原始 0&1）→ 新堆不是 j，而是[0,1]（代表包含原始 0、1 号石子）；
• 合并 c&d（原始 2&3）→ 新堆不是 k，而是[2,3]；
• 合并 e&f（原始 4&5）→ 新堆[4,5]；合并 g&h（原始 6&7）→ 新堆[6,7]。

这时候的石子堆状态是 [ [0,1], [2,3], [4,5], [6,7] ] —— 看起来是 4 个新堆，但每个堆都带着 “原始范围”，你一眼就知道：每个新堆对应的是原始石子的哪一段。

第二步：再合并时，“新堆的范围”=“原始范围的叠加”

比如把[0,1]和[2,3]合并，新堆不是 jk，而是[0,3]（原始 0-3 号石子的集合）；把[4,5]和[6,7]合并，新堆是[4,7]。

此时状态是 [ [0,3], [4,7] ] —— 哪怕合并了两次，这两个新堆的 “原始范围” 依然清晰：左边堆覆盖原始 0-3，右边堆覆盖原始 4-7。

第三步：最后合并的 “边界”，就是 “原始范围的分界线”

当最后合并[0,3]和[4,7]时，这个动作的本质是：

• 左边堆的原始范围是 0-3（a-d）；
• 右边堆的原始范围是 4-7（e-h）；
• 它们的 “边界” 就是原始索引 3 和 4 之间（d 和 e 之间）

哪怕中间换别的合并顺序，比如先合并[0,1]和[2,3]得到[0,3]，再合并[0,3]和[4,5]得到[0,5]，最后合并[0,5]和[6,7]—— 最后一步的边界依然是原始索引 5 和 6 之间（f 和 g 之间），对应 “k=6” 的集合（左 6 堆原始石子，右 2 堆原始石子）。

集合划分的 “边界” 到底是什么？

它不是合并后新堆的 “物理边界”（比如 j 和 k 之间），而是原始石子索引的 “范围分界线” —— 不管中间怎么合并，只要通过 “原始范围标签” 追溯到每个新堆对应的原始石子，最后合并的两个堆，必然能对应到原始石子的 “某一段左范围” 和 “某一段右范围”，它们的分界线就是我们要找的 “边界”。

3. 集合划分思考

通过上面集合划分的方式，已经可以把所有的方案不重不漏的放到各个集合之中。最有的方案一定在某个集合之中，我们只要求解出每个结合中的最小价值，然后比较所有集合的最小价值就是最终的价值了。
很好理解，我们要知道学校里面个子最低的人，已经按照班级把所有的学生不重不漏的划分到了各个班级，只要求出每个班级的个子最低的人，然后比较所有这些个子最低的人就可以了。

单个结合中所有方案的共性就是，左边界和右边界最终会合并。最终得出最后的价值。假设左边界有m中合并方案，有边界的元素有n中合并方案，我们只要求出左边界合并方案中的最优方案，和右边界中合并方案中的最优方案，然后相加即可。

1. 为什么单独求出两侧最优，不会有干扰吗？答案是不会，因为左右两侧的元素都没有重合的
2. 为什么相加即可，左边最后会合成一堆石子，右边也会合成一堆石子，只是合并的过程中产生的价值不同。最后一次合并的价值就是左边合并的价值+右边合并的价值+两堆石子的价值之后，而两堆石子的价值之后就是所有石子加载一起的和
   边界划分集合为1,2,3…n-1

def dfs(arr, l, r):
    if l >= r:
    	return 0
	n = len(arr)
	min_val = float('inf')
	for i in range(n):
	    # 1. 左边界的最小
	    left_val = dfs(arr, 0, i)
	    # 2. 有边界最小
	    righ_val = dfs(arr, i+1, n)
		
		val = left_val + right_val + sum(arr)
		if val < min_val:
		    min_val = val
	return min_val