石子合并（线性数组，每次只能合并相邻两堆，合并得分等于两堆石子数量之和的平方，求最小总得分）

题目描述

有 \(n\) 堆石子排成一行，每堆石子有一定的数量，用数组 \(a[1..n]\) 表示。
每次操作可以选择相邻的两堆石子合并为一堆，合并的得分等于这两堆石子的数量之和的平方。
合并后的新堆石子数量为原来两堆之和，新堆会占据原来的位置，并与左右相邻的石子堆相邻。
不断合并，直到最后只剩下一堆石子。
目标：找到一种合并顺序，使得所有合并操作的总得分最小，并输出这个最小总得分。

示例
假设石子堆为 \([1, 2, 3]\)：

• 合并前两堆：\((1+2)^2 = 9\)，剩下 \([3, 3]\)。
• 合并这两堆：\((3+3)^2 = 36\)，总得分 = \(9 + 36 = 45\)。
• 另一种顺序：先合并后两堆：\((2+3)^2 = 25\)，剩下 \([1, 5]\)，再合并：\((1+5)^2 = 36\)，总得分 = \(25 + 36 = 61\)。
  所以最小总得分为 45。

解题思路

这是经典的“石子合并”问题的变种，区别在于合并得分是“两堆石子数量之和的平方”，而不是通常的“两堆石子数量之和”。
得分函数的改变会影响合并顺序的选择，但区间动态规划框架仍然适用。

关键点：

1. 合并顺序对应一个二叉树结构，叶子是初始石子堆，内部节点是合并结果，得分是子树石子总和的平方。
2. 最后总得分 = 所有内部节点的“子树总和的平方”之和。
3. 如果我们把问题看作：将数组分成若干段，每次合并一段的最后两堆，直到这一段只剩一堆，这个顺序不影响最终得分（因为总得分等于所有内部节点的子树总和的平方之和）。
   实际上，对于一段石子 \(a[i..j]\)，无论合并顺序如何，总得分是固定的吗？
   注意：不是固定的！因为内部节点的子树总和依赖于合并顺序，平方和会不同。
   例如上面的例子，顺序不同，总得分不同。
   所以我们需要动态规划来枚举分割点，寻找最优合并顺序。

动态规划设计

定义：

• \(sum[i]\) 表示前 \(i\) 堆石子数量之和（前缀和），用于快速求区间和。
  区间 \([l, r]\) 的石子总数 = \(sum[r] - sum[l-1]\)。
• 设 \(dp[l][r]\) 表示将第 \(l\) 堆到第 \(r\) 堆石子合并为一堆的最小总得分。
  最终答案是 \(dp[1][n]\)。

转移方程：
考虑最后一次合并发生在哪里。最后一次合并是将左半段 \([l, k]\) 和右半段 \([k+1, r]\) 合并，左半段已经是一堆，右半段也已经是一堆。
那么：

1. 合并左右两堆的得分是：\((sum[r]-sum[l-1])^2\)。
2. 合并左半段 \([l, k]\) 的最小得分是 \(dp[l][k]\)。
3. 合并右半段 \([k+1, r]\) 的最小得分是 \(dp[k+1][r]\)。
4. 所以总得分 = \(dp[l][k] + dp[k+1][r] + (sum[r] - sum[l-1])^2\)。

我们需要枚举分界点 \(k\)，取最小值：

\[dp[l][r] = \min_{k=l}^{r-1} \left\{ dp[l][k] + dp[k+1][r] + (sum[r] - sum[l-1])^2 \right\} \]

其中 \(l \le k < r\)。

边界条件：
当 \(l = r\) 时，只有一堆石子，不需要合并，得分 = 0，即 \(dp[l][l] = 0\)。

计算顺序

区间 DP 通常按区间长度从小到大计算。
设区间长度 \(len\) 从 2 到 \(n\)：

• 对于每个 \(l\) 从 1 到 \(n-len+1\)，\(r = l+len-1\)。
• 枚举 \(k\) 从 \(l\) 到 \(r-1\)，更新 \(dp[l][r]\)。

示例演算

石子数组：\(a = [1, 2, 3]\)，\(n=3\)。
前缀和 \(sum = [0, 1, 3, 6]\)（下标从1开始，sum[0]=0）。

初始化：\(dp[i][i] = 0\)。

len=2：

• \(l=1, r=2\)：
  \(k\) 只能=1：
  \(dp[1][1] + dp[2][2] + (sum[2]-sum[0])^2 = 0+0+(3-0)^2=9\)，所以 \(dp[1][2]=9\)。
• \(l=2, r=3\)：
  \(k=2\)：
  \(dp[2][2] + dp[3][3] + (sum[3]-sum[1])^2 = 0+0+(6-1)^2=25\)，所以 \(dp[2][3]=25\)。

len=3：

• \(l=1, r=3\)：
  \(k=1\)：
  \(dp[1][1] + dp[2][3] + (sum[3]-sum[0])^2 = 0+25+36=61\)。
  \(k=2\)：
  \(dp[1][2] + dp[3][3] + 36 = 9+0+36=45\)。
  取最小值 45，所以 \(dp[1][3]=45\)。

最终答案 = 45。

时间复杂度与空间优化

• 时间复杂度：\(O(n^3)\)，因为三层循环：区间长度、起点、分界点。
• 空间复杂度：\(O(n^2)\) 存储 dp 表。
  对于 \(n\) 较大时（比如 \(n>500\)）可能超时，但此题通常 \(n\) 在 100 左右可接受。

注意：平方的得分导致没有四边形不等式优化（因为平方函数不满足单调性条件），所以一般只能 \(O(n^3)\)。

代码框架（Python）

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

# 示例
stones = [1, 2, 3]
print(min_merge_score(stones))  # 输出 45

总结

本题是区间动态规划的经典应用，通过枚举最后一次合并的分界点，将大区间问题分解为两个小区间子问题，加上合并当前两堆的得分（区间总和的平方），即可得到最小总得分。
尽管得分函数是平方，但动态规划的结构与普通石子合并相同，只是合并代价计算不同。