合并相邻石子堆的最大得分问题（每次合并的得分为两堆石子数量之和的立方，求最大总得分）

问题描述

给定一个长度为 n 的数组 stones，stones[i] 表示第 i 堆石子的数量。每次操作，你可以选择相邻的两堆石子进行合并，合并后得到一堆新的石子，其数量为原来两堆石子数量之和。每次合并的得分定义为这次合并产生的新的石子堆的数量的立方（即 (stones[i] + stones[j])^3）。重复合并操作，直到最终只剩下一堆石子。目标是最大化整个合并过程的总得分。

示例：

输入：stones = [1, 2, 3]
输出：216
解释：
合并过程（一种可能）：
1. 合并 [1, 2] -> 新堆数量 3，得分 3^3 = 27。数组变为 [3, 3]。
2. 合并 [3, 3] -> 新堆数量 6，得分 6^3 = 216。总得分 = 27 + 216 = 243。
另一种可能的合并顺序：
1. 合并 [2, 3] -> 新堆数量 5，得分 5^3 = 125。数组变为 [1, 5]。
2. 合并 [1, 5] -> 新堆数量 6，得分 6^3 = 216。总得分 = 125 + 216 = 341。
因此，最大总得分为 341。

我们需要设计一个动态规划算法，计算出所有可能的合并顺序中，能获得的最大总得分。

解题思路

这是经典的“石子合并”问题的一个变种。经典问题中，合并得分通常是两堆石子数量之和（线性）或乘积，而这里变为立方，这改变了状态转移方程中的得分计算方式，但基本框架不变。

关键点：

• 合并操作只能合并相邻的两堆石子。这天然地将问题划分成了子区间的形式。
• 最终状态是只剩下一堆石子，也就是将整个数组 [0, n-1] 合并成一堆。
• 在合并过程中，最后一次合并一定是将某个左边部分 [0, k] 和右边部分 [k+1, n-1] 合并成最终一堆。所以，我们可以从最后一步合并往前倒推，将大问题分解为两个子区间的合并问题，并加上最后这次合并的得分。

定义状态：
设 dp[i][j] 表示将区间 [i, j] 内的所有石子堆合并成一堆时，能获得的最大总得分（其中 0 ≤ i ≤ j < n）。
我们需要求的就是 dp[0][n-1]。

状态转移：
考虑区间 [i, j] 的最后一次合并。假设我们在位置 k（i ≤ k < j）处将区间分割为左子区间 [i, k] 和右子区间 [k+1, j]，然后合并这两个子区间对应的两堆石子。

• 左子区间合并成一堆的总数量为 sum(i, k)，右子区间为 sum(k+1, j)。
• 最后这次合并的得分为：(sum(i, k) + sum(k+1, j))^3，即 (sum(i, j))^3。
• 左子区间合并过程中的最大得分为 dp[i][k]，右子区间为 dp[k+1][j]。

因此，状态转移方程为：

dp[i][j] = max(dp[i][k] + dp[k+1][j]) + (sum(i, j))^3  ，对所有的 k ∈ [i, j-1] 取最大值

这里 sum(i, j) 表示区间 [i, j] 内所有石子的总数量（即原始数组中该区间的元素和）。注意，最终合并的得分只与区间和有关，与子区间的合并顺序无关，但子区间内部的最大得分需要由 dp 计算得出。

边界条件：

• 当 i == j 时，区间只有一堆石子，不需要合并，得分为 0。即 dp[i][i] = 0。

预处理：
由于频繁计算区间和，我们可以预先计算前缀和数组 prefix，使得 sum(i, j) = prefix[j+1] - prefix[i]，其中 prefix[0] = 0，prefix[t] = stones[0] + ... + stones[t-1]。

逐步求解过程

假设输入 stones = [1, 2, 3]，n = 3。

第一步：计算前缀和

prefix[0] = 0
prefix[1] = stones[0] = 1
prefix[2] = 1 + 2 = 3
prefix[3] = 3 + 3 = 6

第二步：初始化 DP 表
创建二维数组 dp，大小为 n × n，初始值全部设为 0。
根据边界条件，dp[i][i] = 0 已经满足。

dp 初始状态：
i\j 0 1 2
0   0 0 0
1     0 0
2       0

第三步：按区间长度递增的顺序计算
区间长度 len 从 2 到 n（因为长度 1 的区间不需要合并，得分为 0）。

• len = 2：

  • 区间 [0,1]：i=0, j=1。可能的 k 只有 0。
    • sum(0,1) = prefix[2] - prefix[0] = 3 - 0 = 3
    • dp[0][1] = dp[0][0] + dp[1][1] + 3^3 = 0 + 0 + 27 = 27
  • 区间 [1,2]：i=1, j=2。k=1。
    • sum(1,2) = prefix[3] - prefix[1] = 6 - 1 = 5
    • dp[1][2] = dp[1][1] + dp[2][2] + 5^3 = 0 + 0 + 125 = 125

  更新 dp：

i\j 0  1   2
0   0  27  0
1      0   125
2         0

• len = 3：

  • 区间 [0,2]：i=0, j=2。可能的 k=0 或 1。
    • 先计算区间和：sum(0,2) = prefix[3] - prefix[0] = 6 - 0 = 6
    • 情况1：k=0
      • 左：dp[0][0] = 0
      • 右：dp[1][2] = 125
      • 得分 = 0 + 125 + 6^3 = 125 + 216 = 341
    • 情况2：k=1
      • 左：dp[0][1] = 27
      • 右：dp[2][2] = 0
      • 得分 = 27 + 0 + 216 = 243
    • 取最大值：max(341, 243) = 341
  • 所以 dp[0][2] = 341

  最终 dp：

i\j 0  1   2
0   0  27  341
1      0   125
2         0

第四步：输出结果
dp[0][2] = 341 即为最终答案。

算法复杂度

• 时间复杂度：O(n³)。需要枚举所有区间 O(n²)，对每个区间枚举分割点 O(n)，共 O(n³)。
• 空间复杂度：O(n²)，用于存储 dp 表。前缀和数组 O(n)。

关键点总结

1. 区间 DP 的典型结构：定义 dp[i][j] 表示区间 [i, j] 的最优解，通过枚举分割点 k 来合并左右子区间。
2. 得分计算：本问题的特殊之处在于合并得分是合并后石子总数的立方。由于 (sum(i,j))^3 在每次状态转移中都要计算，且与分割点 k 无关，所以可以提前计算好区间和，并在转移时直接使用。
3. 计算顺序：必须按区间长度从小到大的顺序计算，确保计算大区间时，其子区间的解已经算好。

这个问题的变形（得分函数为立方）强化了区间 DP 中“区间和”的重要性，并且立方增长会使得合并顺序的影响更加显著，需要通过动态规划来精确枚举所有可能的分割点，从而找到最优合并顺序。