合并石子获得最小得分问题（相邻合并，每次合并得分是两堆石子数量之积，求最小总得分）
字数 2495 2025-12-17 01:19:58

合并石子获得最小得分问题（相邻合并，每次合并得分是两堆石子数量之积，求最小总得分）

题目描述
给定一行石子堆，用数组 stones 表示，stones[i] 是第 i 堆石子的数量。每次操作可以选择相邻的两堆石子合并为一堆，合并的得分为这两堆石子数量的乘积，合并后新堆的石子数量是这两堆石子数量之和。不断重复合并，直到只剩下一堆石子。目标是找到一种合并顺序，使得整个过程中所有合并操作的总得分最小，并返回这个最小总得分。

例如，stones = [1, 2, 3]。
一种合并顺序：

  1. 合并前两堆 (1, 2)，得分 = 1 × 2 = 2，新堆为 [3, 3]（石子数 3 和原来的 3）。
  2. 合并这两堆 (3, 3)，得分 = 3 × 3 = 9。总得分 = 2 + 9 = 11。
    另一种顺序：
  3. 合并后两堆 (2, 3)，得分 = 2 × 3 = 6，新堆为 [1, 5]。
  4. 合并 (1, 5)，得分 = 1 × 5 = 5。总得分 = 6 + 5 = 11。
    最小总得分是 11。

解题思路
这是一个经典的区间动态规划问题。关键点：

  1. 合并操作只涉及相邻堆，且每次合并后区间内的石子总数是确定的（即区间和）。
  2. 定义状态：dp[i][j] 表示合并第 i 堆到第 j 堆（闭区间）成为一堆的最小总得分。
  3. 最终答案是 dp[0][n-1]，其中 n 是石子堆数。
  4. 状态转移：最后一次合并一定是将区间 [i, j] 分成左右两个子区间 [i, k] 和 [k+1, j] 分别合并成两堆，然后将这两堆合并。合并这两堆的得分是 (sum(i, k)) * (sum(k+1, j))，其中 sum(l, r) 是区间和。因此，转移方程为：

\[ dp[i][j] = \min_{i \le k < j} \{ dp[i][k] + dp[k+1][j] + sum(i, k) \times sum(k+1, j) \} \]

  1. 需要预处理前缀和数组 prefix，以便 O(1) 计算区间和：sum(i, j) = prefix[j+1] - prefix[i]。
  2. 计算顺序：按区间长度从小到大进行动态规划，因为长区间依赖于短区间。

详细步骤
假设有 n 堆石子，数组索引从 0 到 n-1。

第1步：预处理前缀和

  • 定义 prefix[0] = 0，prefix[i] = stones[0] + stones[1] + ... + stones[i-1]。
  • 计算区间和：sum(i, j) = prefix[j+1] - prefix[i]。

第2步：初始化 DP 数组

  • 创建二维数组 dp[n][n]，初始化为 0（因为当区间只有一堆时，不需要合并，得分为 0）。
  • 对于 i = j，dp[i][i] = 0。

第3步：按区间长度从小到大的顺序计算

  • 令 len 从 2 到 n（区间长度）。
  • 对于每个起点 i 从 0 到 n-len：
    • 计算终点 j = i + len - 1。
    • 初始化 dp[i][j] = INF（一个很大的数）。
    • 枚举分割点 k 从 i 到 j-1：
      • 左区间和：left_sum = sum(i, k) = prefix[k+1] - prefix[i]。
      • 右区间和：right_sum = sum(k+1, j) = prefix[j+1] - prefix[k+1]。
      • 当前合并得分：merge_score = left_sum * right_sum。
      • 总得分 = dp[i][k] + dp[k+1][j] + merge_score。
      • 更新最小值：dp[i][j] = min(dp[i][j], 总得分)。

第4步：返回结果

  • 结果就是 dp[0][n-1]。

举例说明
以 stones = [1, 2, 3] 为例。

前缀和：prefix = [0, 1, 3, 6]。

区间长度 len = 2：

  • i=0, j=1：k=0，left_sum = 1，right_sum = 2，merge_score = 2，dp[0][1] = 0+0+2=2。
  • i=1, j=2：k=1，left_sum = 2，right_sum = 3，merge_score = 6，dp[1][2] = 0+0+6=6。

区间长度 len = 3：

  • i=0, j=2：
    • k=0：left_sum = 1，right_sum = 5（sum(1,2)=5），merge_score = 5，得分 = dp[0][0]+dp[1][2]+5 = 0+6+5=11。
    • k=1：left_sum = 3（sum(0,1)=3），right_sum = 3，merge_score = 9，得分 = dp[0][1]+dp[2][2]+9 = 2+0+9=11。
    • 取最小值 11。
      结果：dp[0][2] = 11。

复杂度分析

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

思考扩展

  1. 如果要求最大总得分，只需将 min 改为 max。
  2. 如果是环形石子（即 stones 是环状数组），常用技巧是将数组复制一份接在后面，然后枚举所有长度为 n 的区间，取最小值，时间复杂度升至 O(n³)。
  3. 这个问题的状态转移与“石子合并（得分是两堆石子数之和）”略有不同，那里得分是 sum(i, j)，而这里是左右区间和的乘积，但 DP 框架类似。

通过以上步骤，你可以清晰地理解这个区间动态规划问题的求解过程。每一步都基于子问题的最优解，逐步构建出整个区间的最优解。

合并石子获得最小得分问题（相邻合并，每次合并得分是两堆石子数量之积，求最小总得分） 题目描述 给定一行石子堆，用数组 stones 表示， stones[i] 是第 i 堆石子的数量。每次操作可以选择 相邻 的两堆石子合并为一堆，合并的 得分为这两堆石子数量的乘积 ，合并后新堆的石子数量是这两堆石子数量之和。不断重复合并，直到只剩下一堆石子。目标是找到一种合并顺序，使得整个过程中所有合并操作的 总得分最小 ，并返回这个最小总得分。 例如， stones = [1, 2, 3] 。 一种合并顺序： 合并前两堆 (1, 2) ，得分 = 1 × 2 = 2，新堆为 [3, 3] （石子数 3 和原来的 3）。 合并这两堆 (3, 3) ，得分 = 3 × 3 = 9。总得分 = 2 + 9 = 11。 另一种顺序： 合并后两堆 (2, 3) ，得分 = 2 × 3 = 6，新堆为 [1, 5] 。 合并 (1, 5) ，得分 = 1 × 5 = 5。总得分 = 6 + 5 = 11。 最小总得分是 11。 解题思路 这是一个经典的区间动态规划问题。关键点： 合并操作只涉及相邻堆，且每次合并后区间内的石子总数是确定的（即区间和）。 定义状态： dp[i][j] 表示合并第 i 堆到第 j 堆（闭区间）成为 一堆 的最小总得分。 最终答案是 dp[0][n-1] ，其中 n 是石子堆数。 状态转移：最后一次合并一定是将区间 [i, j] 分成左右两个子区间 [i, k] 和 [k+1, j] 分别合并成两堆，然后将这两堆合并。合并这两堆的得分是 (sum(i, k)) * (sum(k+1, j)) ，其中 sum(l, r) 是区间和。因此，转移方程为： \[ dp[ i][ j] = \min_ {i \le k < j} \{ dp[ i][ k] + dp[ k+1][ j ] + sum(i, k) \times sum(k+1, j) \} \] 需要预处理前缀和数组 prefix ，以便 O(1) 计算区间和： sum(i, j) = prefix[j+1] - prefix[i] 。 计算顺序：按区间长度从小到大进行动态规划，因为长区间依赖于短区间。 详细步骤 假设有 n 堆石子，数组索引从 0 到 n-1。 第1步：预处理前缀和 定义 prefix[0] = 0 ， prefix[i] = stones[0] + stones[1] + ... + stones[i-1] 。 计算区间和： sum(i, j) = prefix[j+1] - prefix[i] 。 第2步：初始化 DP 数组 创建二维数组 dp[n][n] ，初始化为 0（因为当区间只有一堆时，不需要合并，得分为 0）。 对于 i = j ， dp[i][i] = 0 。 第3步：按区间长度从小到大的顺序计算 令 len 从 2 到 n（区间长度）。 对于每个起点 i 从 0 到 n-len： 计算终点 j = i + len - 1 。 初始化 dp[i][j] = INF （一个很大的数）。 枚举分割点 k 从 i 到 j-1 ： 左区间和： left_sum = sum(i, k) = prefix[k+1] - prefix[i] 。 右区间和： right_sum = sum(k+1, j) = prefix[j+1] - prefix[k+1] 。 当前合并得分： merge_score = left_sum * right_sum 。 总得分 = dp[i][k] + dp[k+1][j] + merge_score 。 更新最小值： dp[i][j] = min(dp[i][j], 总得分) 。 第4步：返回结果 结果就是 dp[0][n-1] 。 举例说明 以 stones = [1, 2, 3] 为例。 前缀和： prefix = [0, 1, 3, 6] 。 区间长度 len = 2 ： i=0, j=1 ： k=0 ， left_sum = 1 ， right_sum = 2 ， merge_score = 2 ， dp[0][1] = 0+0+2=2 。 i=1, j=2 ： k=1 ， left_sum = 2 ， right_sum = 3 ， merge_score = 6 ， dp[1][2] = 0+0+6=6 。 区间长度 len = 3 ： i=0, j=2 ： k=0 ： left_sum = 1 ， right_sum = 5 （ sum(1,2)=5 ）， merge_score = 5 ，得分 = dp[0][0]+dp[1][2]+5 = 0+6+5=11 。 k=1 ： left_sum = 3 （ sum(0,1)=3 ）， right_sum = 3 ， merge_score = 9 ，得分 = dp[0][1]+dp[2][2]+9 = 2+0+9=11 。 取最小值 11。 结果： dp[0][2] = 11 。 复杂度分析 时间复杂度：O(n³)，因为三层循环：区间长度 O(n)，起点 O(n)，分割点 O(n)。 空间复杂度：O(n²)，存储 DP 表。 思考扩展 如果要求最大总得分，只需将 min 改为 max 。 如果是环形石子（即 stones 是环状数组），常用技巧是将数组复制一份接在后面，然后枚举所有长度为 n 的区间，取最小值，时间复杂度升至 O(n³)。 这个问题的状态转移与“石子合并（得分是两堆石子数之和）”略有不同，那里得分是 sum(i, j) ，而这里是左右区间和的乘积，但 DP 框架类似。 通过以上步骤，你可以清晰地理解这个区间动态规划问题的求解过程。每一步都基于子问题的最优解，逐步构建出整个区间的最优解。