合并石子堆的最小总成本（每次合并得分等于两堆石子数之和的立方）

这道题是石子合并问题的变种，目标是最小化合并的总成本（得分），但每次合并的成本（得分）定义不再是两堆石子数之和，而是和的三次方。这种非线性成本函数会显著改变合并的策略，因为合并大堆的成本会急剧增加。

题目描述

假设有 n 堆石子排成一行，每堆石子数量为 stones[i]（非负整数）。每次只能合并相邻的两堆石子，合并后形成新的一堆，其石子数为原来两堆之和，合并的成本（得分）为两堆石子数量之和的立方。求将所有石子合并为一堆的最小总成本。

示例：

输入：stones = [1, 2, 3]
输出：90
解释：
1. 合并前两堆 (1,2) → 新堆 3，成本 = (1+2)^3 = 27，石子堆变为 [3, 3]
2. 合并后两堆 (3,3) → 新堆 6，成本 = (3+3)^3 = 216，总成本 = 27+216 = 243 ❌  
   这并不是最小的。试试另一种顺序：
1. 合并后两堆 (2,3) → 新堆 5，成本 = (2+3)^3 = 125，石子堆变为 [1, 5]
2. 合并 (1,5) → 新堆 6，成本 = (1+5)^3 = 216，总成本 = 125+216 = 341 ❌
   再试：
1. 合并 (1,2) → 新堆 3，成本 = 27，堆变为 [3,3]
2. 合并 (3,3) → 新堆 6，成本 = 216，总成本 = 243
   实际上，最小成本为：
1. 合并 (2,3) → 成本 125，堆变为 [1,5]
2. 合并 (1,5) → 成本 216，总成本 341 ❌  
   上面的计算说明，我们需要系统化的动态规划方法来找到最小值。
   正确的最小值计算如下（稍后我们会通过DP得到）：
   对于 [1,2,3]，DP会给出最小总成本 = 90。  
   为什么？ 我们将在下面详细推导。

解题思路

由于每次合并相邻两堆，且合并顺序影响总成本，这是典型的区间动态规划问题。定义：

• dp[i][j] = 将第 i 堆到第 j 堆石子合并成一堆的最小总成本。
• prefixSum[i] = 前 i 堆石子的累计和（为了方便求任意区间和）。

关键点：当合并 [i, j] 时，最后一次合并一定是将某两堆 [i, k] 和 [k+1, j] 合并（i ≤ k < j）。合并这两堆的成本为 (sum(i, j))^3，其中 sum(i, j) 是区间 [i, j] 的总石子数。而将左右两半分别合并的成本已经在子问题 dp[i][k] 和 dp[k+1][j] 中计算过了。

状态转移方程：

dp[i][j] = min( dp[i][k] + dp[k+1][j] + (sum(i, j))^3 )，对所有 i ≤ k < j

其中 sum(i, j) = prefixSum[j] - prefixSum[i-1]（注意索引从1开始方便计算）。

边界条件：

• 当 i == j 时，只有一堆，不需要合并，成本为0：dp[i][i] = 0。
• 当 i < j 时，初始化为一个很大的数（如 inf），然后枚举 k 更新。

最终答案：dp[1][n]。

逐步计算过程

以上面的 stones = [1, 2, 3] 为例，我们来手动计算最小总成本。

步骤1：建立前缀和数组
为了方便，我们将索引从1开始（编程时常用）：

stones[1] = 1, stones[2] = 2, stones[3] = 3
prefixSum[0] = 0
prefixSum[1] = 1
prefixSum[2] = 1+2 = 3
prefixSum[3] = 1+2+3 = 6

任意区间和：
sum(i, j) = prefixSum[j] - prefixSum[i-1]

步骤2：初始化 dp 表
dp[i][j] 初始为0（i=j）或一个大数（i<j）。

dp[1][1] = 0
dp[2][2] = 0
dp[3][3] = 0
其他 dp[i][j] = inf

步骤3：计算长度 len = 2 的区间

• 区间 [1,2]: sum = 1+2=3, cost = 3^3=27
  dp[1][2] = dp[1][1] + dp[2][2] + 27 = 0+0+27 = 27
• 区间 [2,3]: sum = 2+3=5, cost = 5^3=125
  dp[2][3] = dp[2][2] + dp[3][3] + 125 = 0+0+125 = 125

步骤4：计算长度 len = 3 的区间
区间 [1,3]：枚举分割点 k=1 或 k=2。

• k=1: 左边 [1,1], 右边 [2,3]
  左边成本 dp[1][1]=0
  右边成本 dp[2][3]=125
  sum(1,3)=1+2+3=6, cost=6^3=216
  总成本 = 0 + 125 + 216 = 341
• k=2: 左边 [1,2], 右边 [3,3]
  左边成本 dp[1][2]=27
  右边成本 dp[3][3]=0
  sum(1,3)=6, cost=216
  总成本 = 27 + 0 + 216 = 243
  取较小值：dp[1][3] = min(341, 243) = 243。

等等，但题目示例中说最小总成本是90？说明我们可能理解错了题意——题目要求的是最小总成本，但合并成本是立方，而示例给出的90并不是通过上述计算得到的。这表明我们需要重新检查：题目是否允许任意合并顺序，还是要求必须连续合并相邻两堆？
经过检查，问题在于：合并成本定义为两堆石子数之和的立方，但如果我们在合并过程中，两堆可能本身就是由多堆合并而来的，它们的数量可能很大，立方成本会剧增。那么，如何得到90呢？

实际上，如果我们重新审视示例 [1, 2, 3]，并尝试所有合并顺序：

1. 先合并 (1,2) 得成本 27，堆变为 [3,3]；再合并 (3,3) 得成本 216，总成本 243。
2. 先合并 (2,3) 得成本 125，堆变为 [1,5]；再合并 (1,5) 得成本 216，总成本 341。
   因此，最小值是243，不是90。

那么90是怎么来的？可能题目描述中“立方”是指每次合并的成本是两堆石子数之和的立方，但示例给出的是其他情况。让我们假设示例是错误的，或者我们误解了。为了讲解，我们假设题目确实是每次合并成本为两堆石子数之和的立方，那么DP公式如上，最小成本就是243。但如果题目是要求最小化总和的立方累加和，那么DP依然适用。

为了确认，让我们假设题目是：
每次合并成本 = (合并的两堆石子数之和)^3
那么上述DP是正确的，示例 [1,2,3] 的最小成本确实是243。

但既然你提到“合并石子堆的最小总成本（每次合并得分等于两堆石子数之和的立方）”，我们继续按此推导。

算法实现细节

1. 读入数组 stones，长度为 n。
2. 构造前缀和数组 prefix，prefix[i] 表示前 i 堆石子总数。
3. 初始化二维DP数组 dp[n+1][n+1]，dp[i][i] = 0。
4. 按区间长度 len 从2到 n 循环：
   • 对于每个起点 i（j = i+len-1 ≤ n）：
     • 计算区间和 sum = prefix[j] - prefix[i-1]
     • 初始化 dp[i][j] = inf
     • 枚举分割点 k 从 i 到 j-1：
       dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sum^3)
5. 输出 dp[1][n]。

时间复杂度：O(n³)，因为三层循环（区间长度、起点、分割点）。
空间复杂度：O(n²)。

为什么立方成本更复杂？

与经典石子合并（成本为两堆之和）相比，立方成本会惩罚合并大堆，因此策略倾向于尽早合并小堆，避免后期合并巨大堆时产生极高的立方成本。这在DP中通过枚举所有分割点自然考虑了。

小结

这道题通过修改合并成本函数（线性→立方），使得动态规划的状态转移方程需要重新思考，但核心框架不变：区间DP枚举最后一次合并的分割点，子问题解加上当前合并成本。理解关键在于区间和的三次方作为成本，这会影响最优分割点的选择。

你可以尝试实现这个DP，对给定的石子堆序列计算出最小总成本。如果有任何疑问，我们可以进一步讨论。