石子合并（每次合并的得分为两堆石子数量之和的平方，最大化总得分）

题目描述

给定一个长度为 n 的数组 stones，stones[i] 表示第 i 堆石子的数量。每次只能合并相邻的两堆石子，合并的成本（得分）为这两堆石子数量之和的平方。合并后得到的新堆石子数量为原来两堆之和，新堆放在原来两堆的位置。不断合并直到只剩下一堆石子。

目标是最大化所有合并步骤的得分总和。

示例：

stones = [1, 2, 3]

合并方案1：

1. 合并 (1,2) → 新堆 3，得分 (1+2)² = 9，数组变为 [3, 3]
2. 合并 (3,3) → 新堆 6，得分 (3+3)² = 36，总得分 = 9 + 36 = 45

合并方案2：

1. 合并 (2,3) → 新堆 5，得分 (2+3)² = 25，数组变为 [1, 5]
2. 合并 (1,5) → 新堆 6，得分 (1+5)² = 36，总得分 = 25 + 36 = 61

因此最大得分为 61。

解题思路

这是区间动态规划（Interval DP）的经典问题。
关键点：

1. 合并的顺序会影响最终总得分，因为平方函数是非线性的，先合并大数会使得后续合并的基数更大，得分可能更高。
2. 我们需要枚举所有可能的合并顺序，并找到最大得分。

定义状态

设 dp[i][j] 表示将区间 [i, j] 内的所有石子合并成一堆时，能获得的最大总得分（只包括这个区间内的合并步骤）。

状态转移

考虑最后一次合并：区间 [i, j] 最后一步一定是将 [i, k] 合并成的一堆与 [k+1, j] 合并成的一堆进行合并，其中 i ≤ k < j。

• 设 sum(i, j) 表示区间 [i, j] 的石子总数。
• 合并 [i, k] 与 [k+1, j] 的得分为 (sum(i, k) + sum(k+1, j))² = (sum(i, j))²，因为总和不变。
• 但是，dp[i][j] 要包含区间内部所有合并的得分，所以：

\[ dp[i][j] = \max_{i \le k < j} \left( dp[i][k] + dp[k+1][j] + (sum(i, j))^2 \right) \]

注意：这里 (sum(i, j))² 是最后一步合并的得分，dp[i][k] 和 dp[k+1][j] 是左右两段内部合并的总得分。

初始条件

当区间长度为 1 时，只有一堆石子，不需要合并，得分为 0：
dp[i][i] = 0

计算顺序

由于 dp[i][j] 依赖于更短的区间，所以我们按区间长度从小到大计算。

1. 先算长度为 1 的区间（初始值）。
2. 长度从 2 到 n 依次计算。

为了快速求区间和，可以用前缀和数组 prefix，其中 prefix[i] 表示前 i 个元素的和（1-indexed更方便），则：

\[sum(i, j) = prefix[j+1] - prefix[i] \]

示例推演（stones = [1, 2, 3]）

n = 3，下标 0 到 2。
前缀和（1-indexed）：

• prefix[0] = 0
• prefix[1] = 1
• prefix[2] = 3
• prefix[3] = 6

长度 1：
dp[0][0] = 0
dp[1][1] = 0
dp[2][2] = 0

长度 2：

• [0,1]: sum = 1+2 = 3
  k=0: dp[0][0] + dp[1][1] + 3² = 0 + 0 + 9 = 9
  dp[0][1] = 9
• [1,2]: sum = 2+3 = 5
  k=1: dp[1][1] + dp[2][2] + 5² = 0 + 0 + 25 = 25
  dp[1][2] = 25

长度 3：

• [0,2]: sum = 1+2+3 = 6
  k=0: dp[0][0] + dp[1][2] + 6² = 0 + 25 + 36 = 61
  k=1: dp[0][1] + dp[2][2] + 6² = 9 + 0 + 36 = 45
  取最大值：dp[0][2] = 61

结果：61

代码框架（Python）

def max_stone_merge_score(stones):
    n = len(stones)
    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              # 终点
            total = prefix[j+1] - prefix[i]  # 区间和
            dp[i][j] = 0
            for k in range(i, j):          # 分割点
                cur = dp[i][k] + dp[k+1][j] + total * total
                if cur > dp[i][j]:
                    dp[i][j] = cur
    return dp[0][n-1]

# 测试
stones = [1, 2, 3]
print(max_stone_merge_score(stones))  # 输出 61

算法分析

• 时间复杂度：O(n³)，因为三层循环（长度、起点、分割点）。
• 空间复杂度：O(n²)，用于存储 dp 表。

关键点

1. 平方得分使得合并顺序很重要，不同于线性得分（如石子合并最小成本问题）。
2. 最后一步合并的得分只依赖于区间和，与内部如何合并无关，但内部合并的得分（dp[i][k] 和 dp[k+1][j]）会影响总得分，所以需要枚举分割点取最大值。

如果你有更多疑问或想进一步优化（例如数据范围大时的优化思路），可以继续讨论。