合并石子堆的最小总成本（每次合并相邻两堆，得分等于两堆石子数之和的立方）

题目描述

有 n 堆石子排成一列，第 i 堆有 stones[i] 个石子。每次只能合并相邻的两堆，合并的得分等于这两堆石子的数量之和的立方（即 (stones[i] + stones[j])^3），合并后新堆的石子数为两堆之和，位置在原来两堆的区间处。求将所有石子合并成一堆的最小总得分。

示例

输入: stones = [1, 2, 3]
输出: 28
解释: 
一种最优合并方式：
1. 合并 [1, 2] -> 新堆 3，得分 (1+2)^3 = 27，数组变为 [3, 3]
2. 合并 [3, 3] -> 新堆 6，得分 (3+3)^3 = 216
总得分 = 27 + 216 = 243？等等，这里计算有误。我们重新算一下。

我们先验证例子：
初始：[1,2,3]

• 合并(1,2)：得分 (3)^3=27，数组→[3,3]
• 合并(3,3)：得分 (6)^3=216，总得分=27+216=243
  但题目要求最小总得分，可能存在更小的合并方式：
• 合并(2,3)：得分 (5)^3=125，数组→[1,5]
• 合并(1,5)：得分 (6)^3=216，总得分=125+216=341（更大）
  看来这个例子中第一种方式更小。

但注意，本题的得分计算是立方而不是平方，因此合并顺序会显著影响总得分，因为立方会放大石子数量多的堆的影响。我们需要找到最小的总得分，而不是最大。

解题思路（区间DP）

这个问题是经典“石子合并”问题的变体，只是得分计算从“两堆石子数量之和”的平方变成了立方。
区间DP适合解决这种“相邻合并”问题，因为每次合并会合并一个连续区间。

1. 状态定义

设

• dp[l][r] 表示将区间 [l, r] 的所有石子合并成一堆的最小总得分（l, r 从 0 到 n-1）。
• prefix[i] 表示前 i 堆石子的前缀和，用于快速计算区间和。

定义 sum(l, r) = prefix[r+1] - prefix[l] 为区间 [l, r] 的石子总数。

最终目标：dp[0][n-1]。

2. 状态转移

考虑最后一次合并的位置：
在区间 [l, r] 中，最后一步是将 [l, k] 和 [k+1, r] 两堆合并（其中 l ≤ k < r）。
合并前，左边一堆的总石子数 = sum(l, k)，右边一堆的总石子数 = sum(k+1, r)。
合并这两堆的得分 = (sum(l, k) + sum(k+1, r))^3，而 sum(l, k) + sum(k+1, r) = sum(l, r)，所以最后一步得分固定为 (sum(l, r))^3，与 k 无关。

但 k 的选择会影响之前合并的得分：
之前将 [l, k] 合并成一堆的最小得分是 dp[l][k]，将 [k+1, r] 合并成一堆的最小得分是 dp[k+1][r]。

因此：

dp[l][r] = min_{k = l .. r-1} ( dp[l][k] + dp[k+1][r] ) + (sum(l, r))^3

注意：当 l == r 时，只有一堆，不需要合并，得分为 0。

3. 计算顺序

因为区间长度从短到长计算，所以按区间长度 len 从 2 到 n 枚举。
先计算 sum(l, r) 可以用前缀和 O(1) 得到。

4. 边界条件

• 当 l == r 时，dp[l][r] = 0。

5. 举例说明

stones = [1, 2, 3]
n = 3
前缀和 prefix = [0, 1, 3, 6]

len = 2:

• l=0,r=1: sum=3, 立方=27，只有 k=0 一种分割：dp[0][0]+dp[1][1]+27 = 0+0+27 = 27
• l=1,r=2: sum=5, 立方=125，dp[1][2]=125

len = 3: l=0,r=2, sum=6, 立方=216
k=0: dp[0][0]+dp[1][2]+216 = 0+125+216 = 341
k=1: dp[0][1]+dp[2][2]+216 = 27+0+216 = 243
取 min = 243

所以 dp[0][2] = 243，这就是最小总得分。
与之前手动比较一致，第一种合并方式得 243，第二种得 341，所以最小是 243。

6. 复杂度

状态数 O(n²)，每个状态需要枚举分割点 k，O(n) 个，总 O(n³)。
对于 n 较小（如 ≤ 200）可用。

代码实现（Python 示例）

def min_cost_merge_cubic(stones):
    n = len(stones)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + stones[i]
    
    def sum_range(l, r):
        return prefix[r + 1] - prefix[l]
    
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):  # 区间长度
        for l in range(n - length + 1):
            r = l + length - 1
            dp[l][r] = float('inf')
            total = sum_range(l, r)
            merge_cost = total ** 3
            for k in range(l, r):
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + merge_cost)
    return dp[0][n - 1]

# 测试
stones = [1, 2, 3]
print(min_cost_merge_cubic(stones))  # 输出 243

思考与扩展

1. 如果是平方，就是经典石子合并，可以用四边形不等式优化到 O(n²)，但这里是立方，仍然可以这样优化吗？
   在平方情况下，代价满足四边形不等式，但立方不满足，所以不能直接用四边形不等式优化。
2. 如果得分改为和的一次方，总得分固定，与合并顺序无关，因为每次合并得分=两堆之和，总得分=∑(每石子参与合并次数)。

这样，你理解了“合并石子堆的立方得分最小化”的区间 DP 解法吗？