石子合并（线性数组最小总成本，每次只能合并相邻两堆）
字数 2999 2025-12-11 07:40:27

石子合并（线性数组最小总成本，每次只能合并相邻两堆）

题目描述

我们有 n 堆石子排成一排，第 i 堆的石子数量为 a[i]。每次只能合并相邻的两堆，合并的成本是这两堆石子的数量之和。合并后，这两堆变成新的一堆（位置在原来两堆的左侧位置，或者理解为保留合并后的堆在合并区间的最左位置，不影响后续计算），新堆的石子数量就是合并的两堆之和。不断重复合并相邻两堆，直到只剩下一堆石子为止。问题是：设计算法计算合并的总成本最小是多少。

示例
输入：a = [3, 4, 2, 1, 5]
过程（一种合并方式）：

  1. 合并第 3 和第 4 堆（2 和 1），成本 = 2+1=3，数组变为 [3, 4, 3, 5]
  2. 合并第 1 和第 2 堆（3 和 4），成本 = 3+4=7，数组变为 [7, 3, 5]
  3. 合并第 2 和第 3 堆（3 和 5），成本 = 3+5=8，数组变为 [7, 8]
  4. 合并最后两堆，成本 = 7+8=15，总成本 = 3+7+8+15 = 33
    但这不是最优的。最优合并方式可以得到更小的总成本。目标是求出最小总成本。

解题思路

这是一个典型的区间动态规划问题。
关键点：

  1. 合并顺序会影响总成本。
  2. 每次合并的是一个区间内所有石子堆的累加和。
  3. 如果最后一次合并是把区间 [i, j] 分成 [i, k] 和 [k+1, j] 两大部分合并，那么总成本 = 合并 [i, k] 的最小成本 + 合并 [k+1, j] 的最小成本 + sum(i, j)（即最后一次合并的成本，因为最后一步合并的是两堆，它们的石子数就是两个子区间各自的总和）。

设 dp[i][j] 表示合并区间 [i, j] 内所有石子堆的最小总成本（i 和 j 从 0 开始）。
状态转移方程：

\[dp[i][j] = \min_{k = i}^{j-1} \Big( dp[i][k] + dp[k+1][j] + \text{sum}(i, j) \Big) \]

其中 sum(i, j) 是 a[i] + a[i+1] + ... + a[j]。

初始条件：

  • 当区间长度为 1 时（i == j），不需要合并，成本为 0，即 dp[i][i] = 0。

我们按区间长度从小到大计算。

详细步骤

步骤 1：预处理前缀和

为了快速计算 sum(i, j)，先计算前缀和数组 prefix：
prefix[0] = 0
prefix[i] = a[0] + a[1] + ... + a[i-1]，那么 sum(i, j) = prefix[j+1] - prefix[i]。

步骤 2：DP 表初始化

创建二维数组 dp[n][n]，全部初始化为 0（因为长度为 1 的区间成本为 0）。
注意：当 i > j 时无意义，不处理。

步骤 3：按区间长度枚举

区间长度 len 从 2 到 n（即至少两堆才需要合并）：

  • 对每个起点 i（0 <= i <= n-len），计算终点 j = i + len - 1。
  • 初始化 dp[i][j] 为一个很大的数（如 float('inf')）。
  • 对每个分割点 k（i <= k < j）：
    把区间 [i, j] 分成 [i, k] 和 [k+1, j] 两部分，分别合并成两堆，再合并这两堆。
    合并成本 = dp[i][k] + dp[k+1][j] + sum(i, j)。
    取所有 k 的最小值。

步骤 4：结果

最终答案 = dp[0][n-1]。

例子推演

以 a = [3, 4, 2, 1, 5] 为例：

  1. 前缀和：prefix = [0, 3, 7, 9, 10, 15]。
  2. 区间长度 2：
    • [0,1]：sum=7，只能 k=0，dp[0][1]=dp[0][0]+dp[1][1]+7=0+0+7=7。
    • [1,2]：sum=6，dp[1][2]=0+0+6=6。
    • [2,3]：sum=3，dp[2][3]=3。
    • [3,4]：sum=6，dp[3][4]=6。
  3. 区间长度 3：
    • [0,2]：sum=3+4+2=9。
      k=0：dp[0][0]+dp[1][2]+9=0+6+9=15
      k=1：dp[0][1]+dp[2][2]+9=7+0+9=16
      取 min=15 → dp[0][2]=15。
    • [1,3]：sum=4+2+1=7。
      k=1：dp[1][1]+dp[2][3]+7=0+3+7=10
      k=2：dp[1][2]+dp[3][3]+7=6+0+7=13
      取 min=10 → dp[1][3]=10。
    • [2,4]：sum=2+1+5=8。
      k=2：dp[2][2]+dp[3][4]+8=0+6+8=14
      k=3：dp[2][3]+dp[4][4]+8=3+0+8=11
      取 min=11 → dp[2][4]=11。
  4. 区间长度 4：
    • [0,3]：sum=3+4+2+1=10。
      k=0：dp[0][0]+dp[1][3]+10=0+10+10=20
      k=1：dp[0][1]+dp[2][3]+10=7+3+10=20
      k=2：dp[0][2]+dp[3][3]+10=15+0+10=25
      取 min=20 → dp[0][3]=20。
    • [1,4]：sum=4+2+1+5=12。
      k=1：dp[1][1]+dp[2][4]+12=0+11+12=23
      k=2：dp[1][2]+dp[3][4]+12=6+6+12=24
      k=3：dp[1][3]+dp[4][4]+12=10+0+12=22
      取 min=22 → dp[1][4]=22。
  5. 区间长度 5（整个数组）：
    • [0,4]：sum=15。
      k=0：dp[0][0]+dp[1][4]+15=0+22+15=37
      k=1：dp[0][1]+dp[2][4]+15=7+11+15=33
      k=2：dp[0][2]+dp[3][4]+15=15+6+15=36
      k=3：dp[0][3]+dp[4][4]+15=20+0+15=35
      取 min=33 → dp[0][4]=33。

最终答案：dp[0][4] = 33。

复杂度分析

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

关键理解点

  • 为什么状态转移方程中要加上 sum(i, j)？
    因为最后一次合并的成本等于当前整个区间的石子总数，与前面怎么合并无关。
  • 为什么按区间长度枚举？
    因为 dp[i][j] 依赖更短的区间结果（dp[i][k] 和 dp[k+1][j] 的区间长度都比 [i, j] 短），所以必须从小到大计算。
  • 与“合并相邻同色方块”等问题结构类似，都是区间合并的最小成本，但这里成本计算是固定的（区间和），没有颜色匹配或消除规则。
石子合并（线性数组最小总成本，每次只能合并相邻两堆） 题目描述 我们有 n 堆石子排成一排，第 i 堆的石子数量为 a[i] 。每次 只能合并相邻的两堆 ，合并的成本是这两堆石子的数量之和。合并后，这两堆变成新的一堆（位置在原来两堆的左侧位置，或者理解为保留合并后的堆在合并区间的最左位置，不影响后续计算），新堆的石子数量就是合并的两堆之和。不断重复合并相邻两堆，直到只剩下一堆石子为止。问题是：设计算法计算 合并的总成本最小是多少 。 示例 输入： a = [3, 4, 2, 1, 5] 过程（一种合并方式）： 合并第 3 和第 4 堆（2 和 1），成本 = 2+1=3，数组变为 [3, 4, 3, 5] 合并第 1 和第 2 堆（3 和 4），成本 = 3+4=7，数组变为 [7, 3, 5] 合并第 2 和第 3 堆（3 和 5），成本 = 3+5=8，数组变为 [7, 8] 合并最后两堆，成本 = 7+8=15，总成本 = 3+7+8+15 = 33 但这不是最优的。最优合并方式可以得到更小的总成本。目标是求出 最小总成本 。 解题思路 这是一个典型的 区间动态规划 问题。 关键点： 合并顺序会影响总成本。 每次合并的是 一个区间内所有石子堆的累加和 。 如果最后一次合并是把区间 [i, j] 分成 [i, k] 和 [k+1, j] 两大部分合并，那么总成本 = 合并 [i, k] 的最小成本 + 合并 [k+1, j] 的最小成本 + sum(i, j) （即最后一次合并的成本，因为最后一步合并的是两堆，它们的石子数就是两个子区间各自的总和）。 设 dp[i][j] 表示合并区间 [i, j] 内所有石子堆的最小总成本（ i 和 j 从 0 开始）。 状态转移方程： \[ dp[ i][ j] = \min_ {k = i}^{j-1} \Big( dp[ i][ k] + dp[ k+1][ j ] + \text{sum}(i, j) \Big) \] 其中 sum(i, j) 是 a[i] + a[i+1] + ... + a[j] 。 初始条件： 当区间长度为 1 时（ i == j ），不需要合并，成本为 0，即 dp[i][i] = 0 。 我们按 区间长度 从小到大计算。 详细步骤 步骤 1：预处理前缀和 为了快速计算 sum(i, j) ，先计算前缀和数组 prefix ： prefix[0] = 0 prefix[i] = a[0] + a[1] + ... + a[i-1] ，那么 sum(i, j) = prefix[j+1] - prefix[i] 。 步骤 2：DP 表初始化 创建二维数组 dp[n][n] ，全部初始化为 0（因为长度为 1 的区间成本为 0）。 注意：当 i > j 时无意义，不处理。 步骤 3：按区间长度枚举 区间长度 len 从 2 到 n（即至少两堆才需要合并）： 对每个起点 i （ 0 <= i <= n-len ），计算终点 j = i + len - 1 。 初始化 dp[i][j] 为一个很大的数（如 float('inf') ）。 对每个分割点 k （ i <= k < j ）： 把区间 [i, j] 分成 [i, k] 和 [k+1, j] 两部分，分别合并成两堆，再合并这两堆。 合并成本 = dp[i][k] + dp[k+1][j] + sum(i, j) 。 取所有 k 的最小值。 步骤 4：结果 最终答案 = dp[0][n-1] 。 例子推演 以 a = [3, 4, 2, 1, 5] 为例： 前缀和： prefix = [0, 3, 7, 9, 10, 15] 。 区间长度 2： [0,1] ： sum=7 ，只能 k=0 ， dp[0][1]=dp[0][0]+dp[1][1]+7=0+0+7=7 。 [1,2] ： sum=6 ， dp[1][2]=0+0+6=6 。 [2,3] ： sum=3 ， dp[2][3]=3 。 [3,4] ： sum=6 ， dp[3][4]=6 。 区间长度 3： [0,2] ： sum=3+4+2=9 。 k=0 ： dp[0][0]+dp[1][2]+9=0+6+9=15 k=1 ： dp[0][1]+dp[2][2]+9=7+0+9=16 取 min=15 → dp[0][2]=15 。 [1,3] ： sum=4+2+1=7 。 k=1 ： dp[1][1]+dp[2][3]+7=0+3+7=10 k=2 ： dp[1][2]+dp[3][3]+7=6+0+7=13 取 min=10 → dp[1][3]=10 。 [2,4] ： sum=2+1+5=8 。 k=2 ： dp[2][2]+dp[3][4]+8=0+6+8=14 k=3 ： dp[2][3]+dp[4][4]+8=3+0+8=11 取 min=11 → dp[2][4]=11 。 区间长度 4： [0,3] ： sum=3+4+2+1=10 。 k=0 ： dp[0][0]+dp[1][3]+10=0+10+10=20 k=1 ： dp[0][1]+dp[2][3]+10=7+3+10=20 k=2 ： dp[0][2]+dp[3][3]+10=15+0+10=25 取 min=20 → dp[0][3]=20 。 [1,4] ： sum=4+2+1+5=12 。 k=1 ： dp[1][1]+dp[2][4]+12=0+11+12=23 k=2 ： dp[1][2]+dp[3][4]+12=6+6+12=24 k=3 ： dp[1][3]+dp[4][4]+12=10+0+12=22 取 min=22 → dp[1][4]=22 。 区间长度 5（整个数组）： [0,4] ： sum=15 。 k=0 ： dp[0][0]+dp[1][4]+15=0+22+15=37 k=1 ： dp[0][1]+dp[2][4]+15=7+11+15=33 k=2 ： dp[0][2]+dp[3][4]+15=15+6+15=36 k=3 ： dp[0][3]+dp[4][4]+15=20+0+15=35 取 min=33 → dp[0][4]=33 。 最终答案 ： dp[0][4] = 33 。 复杂度分析 时间复杂度：O(n³)，因为三层循环（区间长度、起点、分割点）。 空间复杂度：O(n²)。 关键理解点 为什么状态转移方程中要加上 sum(i, j) ？ 因为最后一次合并的成本等于当前整个区间的石子总数，与前面怎么合并无关。 为什么按区间长度枚举？ 因为 dp[i][j] 依赖更短的区间结果（ dp[i][k] 和 dp[k+1][j] 的区间长度都比 [i, j] 短），所以必须从小到大计算。 与“合并相邻同色方块”等问题结构类似，都是区间合并的最小成本，但这里成本计算是固定的（区间和），没有颜色匹配或消除规则。