石子合并问题的扩展：每次合并的得分是两堆石子数量之积，求最小总得分

题目描述
有 n 堆石子排成一列，第 i 堆石子的重量为 stones[i]（stones[i] > 0）。现在要将这些石子合并成一堆，合并规则如下：

1. 每次只能合并相邻的两堆石子，合并后新堆的重量是原来两堆重量之和。
2. 每次合并的得分是两堆石子的重量之积（即 stones[i] * stones[j]）。
3. 目标是找到一种合并顺序，使得所有合并得分的总和最小，并返回这个最小总得分。

举例说明
假设有 3 堆石子，重量为 [1, 2, 3]。
合并方法 1：先合并前两堆 (1,2)，得分 1*2=2，新堆为 [3, 3]，再合并这两堆 (3,3)，得分 3*3=9，总得分 2+9=11。
合并方法 2：先合并后两堆 (2,3)，得分 2*3=6，新堆为 [1, 5]，再合并这两堆 (1,5)，得分 1*5=5，总得分 6+5=11。
两种方法总得分相同，所以最小总得分为 11。

如果石子堆更多，合并顺序会影响总得分，我们需要找到最优顺序。

解题思路
这是一个经典的区间动态规划问题，与“合并石子获得最小成本”类似，但这里的“成本”是两堆石子的乘积。由于每次合并后新堆重量变化，合并顺序会影响后续乘积，因此我们需要用区间 DP 枚举所有合并顺序。

核心观察：

• 合并区间 [i, j] 时，最后一次合并一定是将 [i, k] 和 [k+1, j] 合并，得分为 (sum[i][k] * sum[k+1][j])，其中 sum[i][j] 是石子堆 i 到 j 的总重量。
• 总得分 = 左子区间合并的最小得分 + 右子区间合并的最小得分 + 最后一次合并得分。
• 因为合并后新堆重量是两子区间总重量之和，所以我们可以用前缀和快速计算区间和。

定义状态
设 dp[i][j] 表示将区间 [i, j] 的所有石子合并成一堆的最小总得分（i 和 j 从 0 开始）。
初始条件：dp[i][i] = 0（一堆石子不需要合并，得分为 0）。
目标：求 dp[0][n-1]。

状态转移方程
对于区间 [i, j]，枚举最后一步合并的分界点 k（i ≤ k < j）：

1. 先将 [i, k] 合并成一堆，其最小得分为 dp[i][k]，合并后的重量为 sum(i, k)。
2. 再将 [k+1, j] 合并成一堆，其最小得分为 dp[k+1][j]，合并后的重量为 sum(k+1, j)。
3. 最后合并这两堆，得分为 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) }  (i ≤ k < j)

其中 sum(i, j) 是 stones[i] + ... + stones[j]。

为了快速计算 sum(i, j)，我们可以预处理前缀和数组 prefix，使得 sum(i, j) = prefix[j+1] - prefix[i]。

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

1. 先计算所有长度为 1 的区间（dp[i][i] = 0）。
2. 然后计算长度为 2, 3, ..., n 的区间。
3. 对于每个区间 [i, j]，枚举所有可能的分界点 k 并取最小值。

逐步推导（以 stones = [1, 2, 3] 为例）

1. 预处理前缀和：prefix = [0, 1, 3, 6]（prefix[i] 表示前 i 堆的和）。
2. 初始化：dp[0][0] = dp[1][1] = dp[2][2] = 0。
3. 长度 = 2：
   • 区间 [0,1]：k 只能为 0，
     dp[0][1] = dp[0][0] + dp[1][1] + sum(0,0)*sum(1,1) = 0 + 0 + 1*2 = 2。
   • 区间 [1,2]：k 只能为 1，
     dp[1][2] = dp[1][1] + dp[2][2] + sum(1,1)*sum(2,2) = 0 + 0 + 2*3 = 6。
4. 长度 = 3：区间 [0,2]：
   • k=0：dp[0][0] + dp[1][2] + sum(0,0)*sum(1,2) = 0 + 6 + 1*(2+3) = 0+6+5=11。
   • k=1：dp[0][1] + dp[2][2] + sum(0,1)*sum(2,2) = 2 + 0 + (1+2)*3 = 2+0+9=11。
   • 取最小值：dp[0][2] = min(11, 11) = 11。
5. 最终结果：dp[0][2] = 11。

算法复杂度

• 时间复杂度：O(n³)，因为三层循环：区间长度、起点、分界点。
• 空间复杂度：O(n²)，存储 dp 数组。

代码框架（Python）

def minScore(stones):
    n = len(stones)
    if n == 0:
        return 0
    
    # 前缀和
    prefix = [0] * (n+1)
    for i in range(n):
        prefix[i+1] = prefix[i] + stones[i]
    
    # 区间和函数
    def range_sum(i, j):
        return prefix[j+1] - prefix[i]
    
    # dp 数组
    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):      # 分界点
                cost = dp[i][k] + dp[k+1][j] + range_sum(i, k) * range_sum(k+1, j)
                dp[i][j] = min(dp[i][j], cost)
    
    return dp[0][n-1]

# 测试
print(minScore([1, 2, 3]))  # 输出 11

思考与扩展

1. 如果要求最大总得分，只需将 min 改为 max。
2. 如果石子排成环形，常见处理是将数组复制一份接在后面，然后枚举所有长度为 n 的区间，取最小值。
3. 本题与经典“合并石子最小成本”的区别在于：经典问题中成本是两堆石子数量之和，而这里是乘积。乘积会导致合并顺序的影响更大，因为大数相乘会显著增加得分，所以最优顺序倾向于让较大的数尽量晚合并（以减少乘积的累加）。

通过上述步骤，你可以理解如何用区间 DP 解决这类“合并相邻元素，得分与元素值相关”的问题。