带权重的石子合并（最大化乘积和）
字数 3275 2025-12-24 13:44:27

带权重的石子合并（最大化乘积和）

题目描述
有 n 堆石子排成一列，每堆石子有重量 w[i]（w[i] > 0）。每次操作可以合并相邻的两堆石子，合并的得分为这两堆石子的重量乘积。合并后，新的一堆石子的重量为原来两堆石子重量之和。重复合并直到只剩下一堆石子。要求设计一种合并顺序，使得总得分最大，并输出这个最大总得分。

例如，石子重量数组为 [3, 4, 2, 5]：

  • 一种合并顺序：先合并 4 和 2（得分 4×2 = 8），得到 [3, 6, 5]；再合并 3 和 6（得分 3×6 = 18），得到 [9, 5]；最后合并 9 和 5（得分 9×5 = 45），总得分 = 8 + 18 + 45 = 71。
  • 另一种顺序：先合并 3 和 4（得分 12），得到 [7, 2, 5]；再合并 2 和 5（得分 10），得到 [7, 7]；最后合并 7 和 7（得分 49），总得分 = 12 + 10 + 49 = 71。
    需要找到所有顺序中的最大总得分。

注意：合并顺序不同会导致总得分不同，目标是最优化合并顺序。

解题思路分析

这个问题属于区间动态规划的经典变体。在普通石子合并问题中，合并得分通常是两堆石子重量之和，而这里是两堆石子重量的乘积。这导致合并的价值不仅依赖于当前两堆的重量，还影响后续合并的基数（因为新堆重量是两堆之和）。

关键观察：

  1. 最后一次合并的得分是最后两堆的重量乘积。这两堆各自是原序列某个连续子区间合并的结果。
  2. 大区间的最优解依赖于其划分成两个小区间的最优解。
  3. 状态设计：dp[l][r] 表示将区间 [l, r] 内的石子合并为一堆时，能获得的最大总得分。但注意合并需要知道区间内石子的总重量（因为新堆重量为两子区间总重量之和），因此还需要维护区间和。

详细解题步骤

步骤 1：定义状态

  • 设 dp[l][r] 表示将区间 [l, r] 内的石子合并成一堆的过程中，能获得的最大总得分（不包括合并成最终一堆之后的操作，因为已经是一堆了，不再有合并得分）。
  • 设 sum[l][r] 表示区间 [l, r] 内石子的总重量。为方便，可用前缀和数组 preSum 快速计算：sum[l][r] = preSum[r] - preSum[l-1]。

注意：这里 dp[l][r] 的定义是“合并区间 [l, r] 成为一堆的过程中的最大得分”，那么最后一步合并是将左右两堆合并成一堆，此时得分是 sum[left] * sum[right]，其中 left 和 right 是左右两堆的重量，也就是左右子区间的总重量。

步骤 2：状态转移方程

考虑区间 [l, r] 如何通过一次合并得到最终一堆。最后一次合并一定是将 [l, k] 合并成的一堆与 [k+1, r] 合并成的一堆进行合并，其中 k 是分割点（l ≤ k < r）。

合并过程：

  • 左子区间 [l, k] 合并成一堆，总重量为 sum[l][k]，此过程最大得分为 dp[l][k]。
  • 右子区间 [k+1, r] 合并成一堆，总重量为 sum[k+1][r]，此过程最大得分为 dp[k+1][r]。
  • 最后将左右两堆合并，得分为 sum[l][k] * sum[k+1][r]。

因此，区间 [l, r] 的最大得分是：

dp[l][r] = max{ dp[l][k] + dp[k+1][r] + sum[l][k] * sum[k+1][r] }，其中 l ≤ k < r

边界条件：当 l == r 时，区间只有一堆石子，不需要合并，得分为 0，即 dp[l][l] = 0。

步骤 3：计算顺序

由于大区间依赖小区间，我们需要按照区间长度从小到大进行动态规划。

  1. 先计算长度为 1 的区间（得分均为 0）。
  2. 再计算长度为 2、3、…、n 的区间。

具体循环：

  • 外层循环：区间长度 len 从 2 到 n。
  • 内层循环：左端点 l 从 1 到 n - len + 1，右端点 r = l + len - 1。
  • 在内层循环中，枚举分割点 k 从 l 到 r-1，更新 dp[l][r]。

步骤 4：前缀和预处理

为了快速得到区间和，预处理前缀和数组 prefix，其中 prefix[i] 表示前 i 堆石子的总重量（下标从 1 开始）。

  • sum[l][r] = prefix[r] - prefix[l-1]。

步骤 5：最终答案

整个区间 [1, n] 合并成一堆的最大得分就是 dp[1][n]。

举例说明

以石子重量 [3, 4, 2, 5] 为例（n=4）。

前缀和：prefix = [0, 3, 7, 9, 14]。

  1. 初始化：dp[i][i] = 0。

  2. 长度 len=2：

    • [1,2]：k=1，dp[1][2] = dp[1][1] + dp[2][2] + sum[1][1]*sum[2][2] = 0 + 0 + 3*4 = 12。
    • [2,3]：k=2，dp[2][3] = 0 + 0 + 4*2 = 8。
    • [3,4]：k=3，dp[3][4] = 0 + 0 + 2*5 = 10。

  3. 长度 len=3：

    • [1,3]：
      • k=1：dp[1][1] + dp[2][3] + sum[1][1]*sum[2][3] = 0 + 8 + 3*(4+2) = 8 + 18 = 26。
      • k=2：dp[1][2] + dp[3][3] + sum[1][2]*sum[3][3] = 12 + 0 + (3+4)*2 = 12 + 14 = 26。
      • 取 max = 26。
    • [2,4]：
      • k=2：dp[2][2] + dp[3][4] + sum[2][2]*sum[3][4] = 0 + 10 + 4*(2+5) = 10 + 28 = 38。
      • k=3：dp[2][3] + dp[4][4] + sum[2][3]*sum[4][4] = 8 + 0 + (4+2)*5 = 8 + 30 = 38。
      • 取 max = 38。

  4. 长度 len=4：[1,4]：

    • k=1：dp[1][1] + dp[2][4] + sum[1][1]*sum[2][4] = 0 + 38 + 3*(4+2+5) = 38 + 33 = 71。
    • k=2：dp[1][2] + dp[3][4] + sum[1][2]*sum[3][4] = 12 + 10 + (3+4)*(2+5) = 22 + 49 = 71。
    • k=3：dp[1][3] + dp[4][4] + sum[1][3]*sum[4][4] = 26 + 0 + (3+4+2)*5 = 26 + 45 = 71。
    • 取 max = 71。

最终答案：dp[1][4] = 71。

算法复杂度

  • 状态数：O(n²)。
  • 每个状态枚举分割点：O(n)。
  • 总时间复杂度：O(n³)。
  • 空间复杂度：O(n²) 用于存储 dp 数组。

为什么这样设计是合理的？

因为在最后一次合并时，左右两堆的重量是它们对应区间的总重量，乘积就是最后一次合并的得分。而左右子区间内部的合并得分已经由子问题的最优解给出。这样，通过枚举所有可能的分割点，我们可以保证找到全局最优的合并顺序。

思考扩展

如果题目改为最小化总得分，状态转移方程中的 max 改为 min 即可。
如果石子排列成环形，只需将原数组复制一份接在后面，然后对每个长度为 n 的区间求 dp[i][i+n-1]，取最大值，复杂度升为 O((2n)³) = O(8n³)，可用四边形不等式优化到 O(n²)（但此题乘积形式不一定满足单调性，一般仍用 O(n³)）。

希望这个分步讲解能帮助你理解这个区间动态规划问题。如果有不清楚的步骤，欢迎继续提问。

带权重的石子合并（最大化乘积和） 题目描述 有 n 堆石子排成一列，每堆石子有重量 w[i] （ w[i] > 0 ）。每次操作可以合并 相邻 的两堆石子，合并的 得分 为这两堆石子的重量 乘积 。合并后，新的一堆石子的重量为原来两堆石子重量之和。重复合并直到只剩下一堆石子。要求设计一种合并顺序，使得 总得分最大 ，并输出这个最大总得分。 例如，石子重量数组为 [3, 4, 2, 5] ： 一种合并顺序：先合并 4 和 2（得分 4×2 = 8），得到 [3, 6, 5] ；再合并 3 和 6（得分 3×6 = 18），得到 [9, 5] ；最后合并 9 和 5（得分 9×5 = 45），总得分 = 8 + 18 + 45 = 71。 另一种顺序：先合并 3 和 4（得分 12），得到 [7, 2, 5] ；再合并 2 和 5（得分 10），得到 [7, 7] ；最后合并 7 和 7（得分 49），总得分 = 12 + 10 + 49 = 71。 需要找到所有顺序中的最大总得分。 注意 ：合并顺序不同会导致总得分不同，目标是最优化合并顺序。 解题思路分析 这个问题属于 区间动态规划 的经典变体。在普通石子合并问题中，合并得分通常是两堆石子重量之和，而这里是 两堆石子重量的乘积 。这导致合并的价值不仅依赖于当前两堆的重量，还影响后续合并的基数（因为新堆重量是两堆之和）。 关键观察： 最后一次合并的得分是最后两堆的重量乘积。这两堆各自是原序列某个连续子区间合并的结果。 大区间的最优解依赖于其划分成两个小区间的最优解。 状态设计： dp[l][r] 表示将区间 [l, r] 内的石子合并为一堆时，能获得的最大总得分。但注意合并需要知道区间内石子的总重量（因为新堆重量为两子区间总重量之和），因此还需要维护区间和。 详细解题步骤 步骤 1：定义状态 设 dp[l][r] 表示将区间 [l, r] 内的石子 合并成一堆 的过程中，能获得的最大总得分（不包括合并成最终一堆之后的操作，因为已经是一堆了，不再有合并得分）。 设 sum[l][r] 表示区间 [l, r] 内石子的总重量。为方便，可用前缀和数组 preSum 快速计算： sum[l][r] = preSum[r] - preSum[l-1] 。 注意 ：这里 dp[l][r] 的定义是“合并区间 [l, r] 成为一堆的过程中的最大得分”，那么最后一步合并是将左右两堆合并成一堆，此时得分是 sum[left] * sum[right] ，其中 left 和 right 是左右两堆的重量，也就是左右子区间的总重量。 步骤 2：状态转移方程 考虑区间 [l, r] 如何通过一次合并得到最终一堆。最后一次合并一定是将 [l, k] 合并成的一堆与 [k+1, r] 合并成的一堆进行合并，其中 k 是分割点（ l ≤ k < r ）。 合并过程： 左子区间 [l, k] 合并成一堆，总重量为 sum[l][k] ，此过程最大得分为 dp[l][k] 。 右子区间 [k+1, r] 合并成一堆，总重量为 sum[k+1][r] ，此过程最大得分为 dp[k+1][r] 。 最后将左右两堆合并，得分为 sum[l][k] * sum[k+1][r] 。 因此，区间 [l, r] 的最大得分是： 边界条件 ：当 l == r 时，区间只有一堆石子，不需要合并，得分为 0，即 dp[l][l] = 0 。 步骤 3：计算顺序 由于大区间依赖小区间，我们需要按照区间长度从小到大进行动态规划。 先计算长度为 1 的区间（得分均为 0）。 再计算长度为 2、3、…、n 的区间。 具体循环： 外层循环：区间长度 len 从 2 到 n。 内层循环：左端点 l 从 1 到 n - len + 1 ，右端点 r = l + len - 1 。 在内层循环中，枚举分割点 k 从 l 到 r-1 ，更新 dp[l][r] 。 步骤 4：前缀和预处理 为了快速得到区间和，预处理前缀和数组 prefix ，其中 prefix[i] 表示前 i 堆石子的总重量（下标从 1 开始）。 sum[l][r] = prefix[r] - prefix[l-1] 。 步骤 5：最终答案 整个区间 [1, n] 合并成一堆的最大得分就是 dp[1][n] 。 举例说明 以石子重量 [3, 4, 2, 5] 为例（n=4）。 前缀和 ： prefix = [0, 3, 7, 9, 14] 。 初始化 ： dp[i][i] = 0 。 长度 len=2 ： [1,2] ： k=1 ， dp[1][2] = dp[1][1] + dp[2][2] + sum[1][1]*sum[2][2] = 0 + 0 + 3*4 = 12 。 [2,3] ： k=2 ， dp[2][3] = 0 + 0 + 4*2 = 8 。 [3,4] ： k=3 ， dp[3][4] = 0 + 0 + 2*5 = 10 。 长度 len=3 ： [1,3] ： k=1 ： dp[1][1] + dp[2][3] + sum[1][1]*sum[2][3] = 0 + 8 + 3*(4+2) = 8 + 18 = 26 。 k=2 ： dp[1][2] + dp[3][3] + sum[1][2]*sum[3][3] = 12 + 0 + (3+4)*2 = 12 + 14 = 26 。 取 max = 26。 [2,4] ： k=2 ： dp[2][2] + dp[3][4] + sum[2][2]*sum[3][4] = 0 + 10 + 4*(2+5) = 10 + 28 = 38 。 k=3 ： dp[2][3] + dp[4][4] + sum[2][3]*sum[4][4] = 8 + 0 + (4+2)*5 = 8 + 30 = 38 。 取 max = 38。 长度 len=4 ： [1,4] ： k=1 ： dp[1][1] + dp[2][4] + sum[1][1]*sum[2][4] = 0 + 38 + 3*(4+2+5) = 38 + 33 = 71 。 k=2 ： dp[1][2] + dp[3][4] + sum[1][2]*sum[3][4] = 12 + 10 + (3+4)*(2+5) = 22 + 49 = 71 。 k=3 ： dp[1][3] + dp[4][4] + sum[1][3]*sum[4][4] = 26 + 0 + (3+4+2)*5 = 26 + 45 = 71 。 取 max = 71。 最终答案 ： dp[1][4] = 71 。 算法复杂度 状态数：O(n²)。 每个状态枚举分割点：O(n)。 总时间复杂度：O(n³)。 空间复杂度：O(n²) 用于存储 dp 数组。 为什么这样设计是合理的？ 因为在最后一次合并时，左右两堆的重量是它们对应区间的总重量，乘积就是最后一次合并的得分。而左右子区间内部的合并得分已经由子问题的最优解给出。这样，通过枚举所有可能的分割点，我们可以保证找到全局最优的合并顺序。 思考扩展 如果题目改为 最小化总得分 ，状态转移方程中的 max 改为 min 即可。 如果石子排列成 环形 ，只需将原数组复制一份接在后面，然后对每个长度为 n 的区间求 dp[i][i+n-1] ，取最大值，复杂度升为 O((2n)³) = O(8n³)，可用四边形不等式优化到 O(n²)（但此题乘积形式不一定满足单调性，一般仍用 O(n³)）。 希望这个分步讲解能帮助你理解这个区间动态规划问题。如果有不清楚的步骤，欢迎继续提问。