合并相邻石子堆的最小得分问题（每次合并的得分为两堆石子数量之和的平方，最小化总得分）
题目描述
给定一个整数数组 stones，stones[i] 表示第 i 堆石子的数量。每次合并操作可以选择相邻的两堆石子，将它们合并为一堆，合并的得分为合并后新堆石子数量的平方，即 (stones[i] + stones[i+1])^2，合并后新堆的位置为原来两堆的位置之一（通常理解为新堆占据这个连续区间）。合并后数组长度减 1。重复这一过程，直到只剩下一堆石子。要求计算将所有石子合并为一堆的最小总得分。
例如，stones = [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. 定义状态
设 dp[i][j] 表示将区间 [i, j] 内的所有石子合并为一堆的最小总得分。其中 0 ≤ i ≤ j < n，n 为石子堆数。
2. 状态转移方程
考虑最后一次合并：区间 [i, j] 最终一定是由两个子区间 [i, k] 和 [k+1, j] 合并而成，其中 i ≤ k < j。
- 将
[i, k]合并为一堆，其石子总数为sum(i, k)，得分为dp[i][k]。 - 将
[k+1, j]合并为一堆，其石子总数为sum(k+1, j)，得分为dp[k+1][j]。 - 最后将这两堆合并，得分为
(sum(i, k) + sum(k+1, j))^2 = (sum(i, j))^2，其中sum(i, j)表示区间[i, j]的总石子数。
因此，状态转移方程为：
dp[i][j] = min{ dp[i][k] + dp[k+1][j] + (sum(i, j))^2 }，对每个 k 满足 i ≤ k < j
注意：这里 (sum(i, j))^2 是最后一步合并的得分，而 dp[i][k] 和 dp[k+1][j] 已经包含了将子区间合并为两堆所需的得分。所以总得分是这三部分之和。
3. 初始化
当区间长度为 1 时，即 i == j，不需要合并，得分为 0：
dp[i][i] = 0。
4. 计算顺序
因为 dp[i][j] 依赖于更短的区间（[i, k] 和 [k+1, j] 的长度都小于 [i, j] 的长度），所以我们按区间长度从小到大计算。
- 外层循环：长度
len从 2 到 n。 - 内层循环：左端点
i从 0 到n - len，则右端点j = i + len - 1。 - 内内层循环：枚举分割点
k从i到j-1，计算dp[i][j]的最小值。
5. 前缀和优化
为了快速计算区间和 sum(i, j)，我们可以使用前缀和数组 prefix，其中 prefix[0] = 0，prefix[i+1] = stones[0] + ... + stones[i]。
则 sum(i, j) = prefix[j+1] - prefix[i]。
6. 最终答案
答案为 dp[0][n-1]。
举例说明
以 stones = [1, 2, 3] 为例：
- 前缀和：
prefix = [0, 1, 3, 6]。 - 初始化：
dp[0][0] = 0，dp[1][1] = 0，dp[2][2] = 0。 - 长度
len = 2：[0,1]：sum = prefix[2]-prefix[0]=3，枚举k=0：dp[0][1] = dp[0][0]+dp[1][1]+3^2 = 0+0+9=9。[1,2]：sum = prefix[3]-prefix[1]=5，枚举k=1：dp[1][2] = dp[1][1]+dp[2][2]+5^2 = 0+0+25=25。
- 长度
len = 3：[0,2]，sum = prefix[3]-prefix[0]=6，枚举k=0和k=1：k=0：dp[0][0]+dp[1][2]+6^2 = 0+25+36=61。k=1：dp[0][1]+dp[2][2]+6^2 = 9+0+36=45。
取最小值45，即dp[0][2] = 45。
因此最小总得分为 45。
复杂度分析
- 时间复杂度：O(n³)，因为三层循环（区间长度、左端点、分割点）。
- 空间复杂度：O(n²)，用于存储
dp数组。
关键点
本题的难点在于识别出：虽然合并得分是平方项，但最后一步的得分只与区间总石子数有关，与子区间内部的合并顺序无关。因此状态转移方程中，最后一步得分是固定的 (sum(i, j))^2，而子区间的合并顺序则通过 dp[i][k] 和 dp[k+1][j] 已经考虑了最优解。