石子合并（每次合并的得分是两堆石子数量之积，求最小总得分）

题目描述

你有 n 堆石子排成一列，第 i 堆石子有 stones[i] 个石子。你的目标是将所有石子合并成一堆，合并规则如下：

1. 每次只能合并相邻的两堆石子。
2. 合并的得分等于两堆石子的数量相乘（即如果两堆石子数量分别为 x 和 y，则得分为 x * y）。
3. 合并后得到新的一堆，其石子数量为 x + y。

你需要进行 n-1 次合并，将所有石子合并成一堆。要求计算所有可能的合并顺序中，总得分的最小值。

示例：

stones = [3, 2, 4]

一种可能的合并顺序：

• 合并 (3, 2)：得分 = 3*2 = 6，新堆 = 5，剩下 [5, 4]。
• 合并 (5, 4)：得分 = 5*4 = 20，新堆 = 9。
  总得分 = 6 + 20 = 26。

另一种顺序：

• 合并 (2, 4)：得分 = 2*4 = 8，新堆 = 6，剩下 [3, 6]。
• 合并 (3, 6)：得分 = 3*6 = 18，新堆 = 9。
  总得分 = 8 + 18 = 26。

所以最小总得分为 26。

为什么是区间动态规划？

• 每次合并相邻两堆，合并顺序会影响后续合并的石子数量，从而影响总得分。
• 问题具有“最优子结构”：合并 stones[i..j] 的最小得分，可以通过合并其子区间 stones[i..k] 和 stones[k+1..j] 的最小得分，再加上最后合并这两大堆的得分来得到。
• 这是经典的“合并类”区间DP，与“石子合并（和版本）”类似，但得分计算不同。

解题步骤详解

1. 定义状态

设：

• n 为石子堆数。
• dp[i][j] 表示将区间 [i, j] 内的所有石子合并成一堆的最小总得分（0 ≤ i ≤ j < n）。
• 为了方便计算区间石子总数，可以预处理前缀和数组 prefixSum，使得 prefixSum[i] 表示前 i 堆石子数总和（通常 prefixSum[0] = 0，prefixSum[k] = sum(stones[0..k-1])），则区间 [i, j] 的石子总数 = prefixSum[j+1] - prefixSum[i]。

2. 状态转移方程

考虑最后一次合并：将区间 [i, j] 分成两段 [i, k] 和 [k+1, j]，先将这两段各自合并成一堆，再将这两堆合并。

• 合并 [i, k] 的得分是 dp[i][k]，合并后石子数 = sum(i, k)。
• 合并 [k+1, j] 的得分是 dp[k+1][j]，合并后石子数 = sum(k+1, j)。
• 最后合并这两大堆的得分 = sum(i, k) * sum(k+1, j)。

因此转移方程为：

dp[i][j] = min(
    dp[i][k] + dp[k+1][j] + sum(i, k) * sum(k+1, j)
) 对于所有 k 满足 i ≤ k < j

当区间长度为 1 时（i == j），合并得分为 0，因为不需要合并。

3. 计算顺序

区间 DP 通常按区间长度从小到大计算。

1. 初始化：dp[i][i] = 0。
2. 枚举长度 len 从 2 到 n（长度至少为 2 才能合并）。
3. 对于每个起点 i，计算终点 j = i + len - 1。
4. 枚举分界点 k 从 i 到 j-1，更新 dp[i][j]。

4. 边界情况

• 如果 n == 1，无需合并，得分为 0。
• 如果 n == 2，只有一种合并方式，得分为 stones[0] * stones[1]。

示例演算

以 stones = [3, 2, 4] 为例：

1. 前缀和：

   stones:    3, 2, 4
   prefix: 0, 3, 5, 9
   sum(i, j) = prefix[j+1] - prefix[i]
   

2. 初始化：

   dp[0][0] = 0
   dp[1][1] = 0
   dp[2][2] = 0
   

3. 长度 len=2：

   • [0,1]：dp[0][1] = dp[0][0] + dp[1][1] + sum(0,0)sum(1,1) = 0 + 0 + 32 = 6
   • [1,2]：dp[1][2] = 0 + 0 + 2*4 = 8

4. 长度 len=3：

   • [0,2]：
     k=0：dp[0][0] + dp[1][2] + sum(0,0)sum(1,2) = 0 + 8 + 3(2+4) = 0+8+18=26
     k=1：dp[0][1] + dp[2][2] + sum(0,1)sum(2,2) = 6 + 0 + (3+2)4 = 6+0+20=26
     min = 26

最终结果：dp[0][2] = 26。

时间复杂度

• 状态数：O(n²)
• 每个状态枚举分界点 k：O(n)
• 总复杂度：O(n³)，可通过四边形不等式优化到 O(n²)，但本题 n 较小（通常 ≤ 100）时 O(n³) 可接受。

关键点

• 本题的得分计算是乘积，而非之前常见的“和”，因此在转移时需要将两段各自的总和相乘，而不是简单相加。
• 乘积性质意味着尽量让大数和大数晚点合并，以减少乘积的累积影响，这是最小化的目标。
• 与“石子合并（和版本）”不同，乘积版本没有单调性（大数*大数可能很大），因此不能简单贪心，必须 DP 枚举。

核心代码（Python）

def minScore(stones):
    n = len(stones)
    if n == 1:
        return 0
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + stones[i]
    
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                left_sum = prefix[k+1] - prefix[i]
                right_sum = prefix[j+1] - prefix[k+1]
                score = dp[i][k] + dp[k+1][j] + left_sum * right_sum
                dp[i][j] = min(dp[i][j], score)
    return dp[0][n-1]

# 测试
print(minScore([3, 2, 4]))  # 26

思考扩展

• 如果要求最大总得分，只需将 min 改为 max，但通常最大值更容易产生（大数和大数相乘大，但合并顺序会影响后续值）。
• 如果石子是环形排列，可将数组复制一倍，然后 DP 计算所有长度为 n 的区间的最小值，复杂度 O(2n)³，可优化。

这个题目是区间 DP 中“合并类”的一个经典变形，重点在于理解乘积得分如何影响合并顺序，并用 DP 枚举所有分割方案。