合并相邻石子堆的最大总得分问题（每次合并得分等于两堆石子数量之和的立方，求最大总得分）

题目描述

给定一排石子堆，每堆石子的数量用一个整数数组 stones 表示（stones[i] ≥ 1）。我们只能合并相邻的两堆石子，直到所有石子合并成一堆。
每次合并时，选择的相邻两堆石子数量分别为 a 和 b，合并后新堆的石子数量为 a + b，同时获得本次合并的得分为 (a + b)^3。
目标是最大化所有合并操作的总得分。
请设计一个算法，计算出最大总得分。

示例
输入：stones = [1, 2, 3]
输出：最大总得分
解释：

• 方案1：先合并前两堆（1+2=3，得分=3³=27），得到 [3, 3]；再合并这两堆（3+3=6，得分=6³=216），总得分=27+216=243。
• 方案2：先合并后两堆（2+3=5，得分=125），得到 [1, 5]；再合并这两堆（1+5=6，得分=216），总得分=125+216=341。
  最大总得分=341。

解题思路

这个问题与经典的“石子合并”问题类似，但得分函数从 (a+b) 的线性形式变为立方形式 (a+b)^3，这使得合并顺序对得分影响更大。
因为合并必须相邻，且最终所有堆会合为一堆，这自然形成一个区间划分的过程：每次合并相当于将某个区间内的所有石子堆合并成一堆。
因此，可以使用区间动态规划（Interval DP）来解决。

关键步骤与状态定义

1. 预处理前缀和
为了方便快速计算任意区间 [i, j] 内的石子总数，先计算前缀和数组 prefixSum，其中 prefixSum[i] 表示前 i 堆石子总数（下标从1开始更直观）。
例如，对于 stones[0...n-1]，定义：

• prefixSum[0] = 0
• prefixSum[i] = prefixSum[i-1] + stones[i-1]（i从1到n）

则区间 [l, r] 的石子总数（下标从0开始）为：

\[sum(l, r) = prefixSum[r+1] - prefixSum[l] \]

2. 状态定义
设 dp[l][r] 表示将区间 [l, r] 内的所有石子堆合并成一堆时，所能获得的最大总得分。
最终答案为 dp[0][n-1]。

3. 状态转移
考虑最后一次合并区间 [l, r]：
最后一次合并是将该区间分成两部分 [l, k] 和 [k+1, r]（其中 l ≤ k < r），分别合并成两堆，再将这两堆合并。

• 左部分 [l, k] 合并成一堆，其石子总数为 sum(l, k)，得分为 dp[l][k]。
• 右部分 [k+1, r] 合并成一堆，石子总数为 sum(k+1, r)，得分为 dp[k+1][r]。
• 最后合并这两堆：合并得分为 (sum(l, k) + sum(k+1, r))^3 = (sum(l, r))^3（因为左右总和就是整个区间的石子总数）。

因此，总得分为：

\[dp[l][k] + dp[k+1][r] + (sum(l, r))^3 \]

我们需要枚举所有可能的分割点 k，取最大值：

\[dp[l][r] = \max_{l \le k < r} \left( dp[l][k] + dp[k+1][r] + (sum(l, r))^3 \right) \]

4. 边界条件
当区间长度为1时（即 l == r），只有一堆石子，不需要合并，得分为0：

\[dp[l][l] = 0 \]

5. 计算顺序
由于转移依赖更小的区间，我们需要按照区间长度从小到大进行计算。

• 外层循环：区间长度 len 从 2 到 n（长度为1已初始化）。
• 内层循环：左端点 l 从 0 到 n - len，计算出右端点 r = l + len - 1。
• 在内层循环中枚举所有分割点 k。

示例推导（输入 stones = [1, 2, 3]）

前缀和：
prefixSum = [0, 1, 3, 6]
（即 sum(0,0)=1, sum(0,1)=3, sum(0,2)=6）

初始化：
dp[0][0]=0, dp[1][1]=0, dp[2][2]=0

计算区间长度 len=2：

• [0,1]: sum=3
  枚举 k=0：dp[0][0]+dp[1][1]+3³=0+0+27=27
dp[0][1]=27
• [1,2]: sum=5
  枚举 k=1：dp[1][1]+dp[2][2]+5³=0+0+125=125
dp[1][2]=125

计算区间长度 len=3：

• [0,2]: sum=6
  • k=0：左部分 [0,0]，右部分 [1,2]
    得分=dp[0][0]+dp[1][2]+6³=0+125+216=341
  • k=1：左部分 [0,1]，右部分 [2,2]
    得分=dp[0][1]+dp[2][2]+6³=27+0+216=243
    取最大值：dp[0][2]=341

最终答案：dp[0][2]=341，与手动计算一致。

算法复杂度

• 时间复杂度：O(n³)，因为需要枚举区间（O(n²)）和分割点（O(n)）。
• 空间复杂度：O(n²)，用于存储 dp 数组。

代码框架（Python）

def max_merge_score(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(0, n - length + 1):
            r = l + length - 1
            total = sum_range(l, r)
            best = 0
            for k in range(l, r):
                score = dp[l][k] + dp[k + 1][r] + total ** 3
                if score > best:
                    best = score
            dp[l][r] = best
    
    return dp[0][n - 1]

# 测试
print(max_merge_score([1, 2, 3]))  # 341

关键讨论与扩展

1. 为什么立方得分会使问题更适合最大化得分？
   因为立方函数增长很快，合并大堆时的得分远高于小堆。策略倾向于尽早积累大堆，以便后续合并时获得更高的立方得分。在上例中，先合并（2,3）得到大堆5，比先合并（1,2）更优。

2. 如果是“最小化总得分”怎么办？
   状态转移中的 max 改为 min 即可，但策略会变化：立方函数下，尽量避免过早产生大堆。

3. 能否优化到 O(n²)？
   对于线性得分（如 (a+b)），经典石子合并问题可通过“四边形不等式优化”降到 O(n²)。但对于立方得分，由于得分函数不满足单调性，一般优化不适用，通常仍需 O(n³)。

总结

本题展示了区间DP在相邻合并类问题中的典型应用：

• 状态定义为区间 [l, r] 的最优值。
• 转移时枚举最后一次合并的分割点。
• 得分函数依赖于区间总和，通过前缀和快速计算。

通过这个例子，你可以深入理解区间DP在处理“相邻合并+复杂得分函数”问题时的通用思路。