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

题目描述
有 n 堆石子排成一行，第 i 堆石子有 weights[i] 个石子。你需要通过合并相邻的石子堆，最终将所有石子合并成一堆。每次合并只能合并相邻的两堆，合并这两堆石子时会产生得分，得分等于这两堆石子的总数量（合并后的新堆的石子数）的立方。你的目标是找出一种合并顺序，使得总得分最小，并返回这个最小总得分。

例如，石子堆 = [1, 2, 3]：

• 合并前两堆：得分 = (1+2)³ = 27，新堆为 [3, 3]
• 合并这两堆：得分 = (3+3)³ = 216，总得分 = 27+216 = 243
• 或者先合并后两堆：得分 = (2+3)³ = 125，新堆为 [1, 5]
• 再合并这两堆：得分 = (1+5)³ = 216，总得分 = 125+216 = 341
  最小总得分是 243。

解题步骤

1. 问题分析

这是一个典型的区间DP问题，因为：

• 合并操作只涉及相邻堆，每次合并后区间长度减小。
• 需要枚举所有可能的合并顺序，找到最优顺序。
• 最终状态是整段区间合并成一堆。

设 dp[i][j] 表示将第 i 到第 j 堆石子合并成一堆的最小总得分。
目标：求 dp[0][n-1]。

2. 状态转移方程推导

考虑最后一次合并发生在哪里。假设最后一次合并时，左边是 [i, k] 合并成的一堆，右边是 [k+1, j] 合并成的一堆，然后将这两堆合并。

• 合并 [i, k] 的最小得分是 dp[i][k]
• 合并 [k+1, j] 的最小得分是 dp[k+1][j]
• 最后一步合并的得分等于 (sum(i, j))³，其中 sum(i, j) 是区间 [i, j] 的石子总数。

因此状态转移方程为：

\[dp[i][j] = \min_{k \in [i, j-1]} \{ dp[i][k] + dp[k+1][j] + (\text{sum}(i, j))^3 \} \]

这里 sum(i, j) 可以用前缀和数组 prefix 快速计算：

\[\text{sum}(i, j) = \text{prefix}[j+1] - \text{prefix}[i] \]

3. 初始化与边界条件

• 当区间长度 len = 1 时，只有一堆石子，不需要合并，得分为 0。
  即 dp[i][i] = 0。
• 当 len = 2 时，直接合并这两堆，得分是 (weights[i] + weights[i+1])³。
• 当 len > 2 时，需要枚举分割点 k。

4. 计算顺序

区间DP的经典计算顺序：

1. 枚举区间长度 len 从 2 到 n。
2. 枚举区间左端点 i，则右端点 j = i + len - 1。
3. 枚举分割点 k 从 i 到 j-1，更新 dp[i][j]。

这样保证计算 dp[i][j] 时，更短的区间已经计算完毕。

5. 时间复杂度与空间优化

• 时间复杂度：O(n³)（三层循环）。
• 空间复杂度：O(n²)（二维DP表）。

6. 示例详解

石子堆 = [1, 2, 3]
n = 3, 前缀和 prefix = [0, 1, 3, 6]

len = 2

• [0,1]: sum=3, dp[0][1] = 3³ = 27
• [1,2]: sum=5, dp[1][2] = 5³ = 125

len = 3
区间 [0,2]：

• k=0: dp[0][0]+dp[1][2]+sum³ = 0+125+6³=125+216=341
• k=1: dp[0][1]+dp[2][2]+sum³ = 27+0+216=243
  取 min = 243

最终 dp[0][2] = 243。

7. 代码实现（Python）

def min_merge_cost_cubic(weights):
    n = len(weights)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + weights[i]

    dp = [[0] * n for _ in range(n)]
    # 初始化长度为1的区间已在dp中默认为0
    for length in range(2, n + 1):  # 区间长度
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            total = prefix[j + 1] - prefix[i]
            for k in range(i, j):
                cost = dp[i][k] + dp[k + 1][j] + total ** 3
                if cost < dp[i][j]:
                    dp[i][j] = cost
    return dp[0][n - 1]

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

8. 关键点总结

1. 区间DP的定义要清晰：dp[i][j] 是最小总得分，不是最后一次合并的得分。
2. 合并得分基于当前合并区间的石子总数的立方，与子区间的合并顺序无关。
3. 必须用前缀和快速计算区间和，否则会超时。
4. 本题与经典“石子合并（平方和得分）”的区别在于得分函数是立方，但DP结构相同。

通过以上步骤，你可以理解如何用区间DP解决这种合并类问题，并且能推广到其他合并得分函数的情况。