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

字数 3076 2025-12-17 22:22:05

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

问题描述

假设有一排 n 堆石子，排成一行，每堆石子的数量用一个正整数表示，记为数组 stones[0..n-1]。现在你需要通过一系列操作，将这些石子合并成一堆。每次操作，你可以选择相邻的两堆石子，将它们合并成一堆。合并一堆新的石子，其数量等于原来两堆石子的数量之和。每次合并操作会产生一个“得分”，这个得分定义为两堆石子的数量之积。目标是找出一种合并顺序，使得所有操作的总得分之和最大，并返回这个最大总得分。

例如，石子堆为 [3, 1, 5, 2]：

一种可能的合并顺序是：先合并 (1, 5) 得 15=5 分，新堆为 6，序列变为 [3, 6, 2]；再合并 (3, 6) 得 36=18 分，新堆为 9，序列变为 [9, 2]；最后合并 (9, 2) 得 9*2=18 分。总得分 = 5+18+18=41。
另一种顺序：先合并 (3, 1) 得 31=3 分，新堆为 4，序列变为 [4, 5, 2]；再合并 (5, 2) 得 52=10 分，新堆为 7，序列变为 [4, 7]；最后合并 (4, 7) 得 4*7=28 分。总得分 = 3+10+28=41。
但可能有顺序能得到更高得分，我们需要找到最大值。

这个问题是典型的区间DP，因为合并操作会改变相邻关系，且最终结果依赖于如何划分最后一步合并的边界。

核心思路

状态定义：设 dp[i][j] 表示合并区间 [i, j] 内的所有石子堆成一堆时，能获得的最大总得分。其中 0 ≤ i ≤ j < n。
最终目标：求 dp[0][n-1]。
状态转移：考虑最后一次合并区间 [i, j] 时，一定是将 [i, j] 分成左右两个区间 [i, k] 和 [k+1, j] 分别合并成两堆，再将这两堆合并。设区间 [i, j] 的石子总数为 sum(i, j)（前缀和可快速计算）。
- 左区间合并成一堆，石子总数为 sum(i, k)。
- 右区间合并成一堆，石子总数为 sum(k+1, j)。
- 最后合并这两堆的得分为：sum(i, k) * sum(k+1, j)。
- 因此，总得分 = dp[i][k] + dp[k+1][j] + sum(i, k) * sum(k+1, j)。
- 我们需要枚举分界点 k，取最大值。
边界条件：当区间长度为1（即 i == j）时，只有一堆石子，无需合并，得分 dp[i][i] = 0。
计算顺序：因为区间长度从短到长计算，所以先枚举区间长度 len 从 2 到 n，再枚举左端点 i，计算出右端点 j = i+len-1，最后枚举分界点 k 从 i 到 j-1。

详细步骤

步骤1：预处理前缀和
为了方便计算任意区间 [i, j] 的石子总数，我们先计算前缀和数组 prefix：

prefix[0] = stones[0]
prefix[t] = stones[0] + stones[1] + ... + stones[t] （t 从 0 到 n-1）
则区间和 sum(i, j) = prefix[j] - (i > 0 ? prefix[i-1] : 0)。

步骤2：初始化DP表
创建一个二维数组 dp[n][n]，所有值初始化为0。对于长度为1的区间，dp[i][i] 已为0（无需操作）。

步骤3：按区间长度递推

遍历 len = 2 到 n：
- 遍历左端点 i = 0 到 n - len：
  - 右端点 j = i + len - 1。
  - 初始化 dp[i][j] 为一个很小的数（如 -∞）或0，因为我们要求最大值。
  - 遍历分界点 k = i 到 j-1：
    - 计算左区间和 sum_left = sum(i, k)
    - 计算右区间和 sum_right = sum(k+1, j)
    - 当前得分 = dp[i][k] + dp[k+1][j] + sum_left * sum_right
    - 用当前得分更新 dp[i][j] 的最大值。

步骤4：返回结果
dp[0][n-1] 即为最大总得分。

例子演示

以 stones = [3, 1, 5, 2] 为例：
n=4，前缀和 prefix = [3, 4, 9, 11]。

len=2：
- [0,1]: i=0, j=1, k 只能=0。
  sum_left = sum(0,0)=3, sum_right=sum(1,1)=1 → 得分=0+0+3*1=3，dp[0][1]=3。
- [1,2]: i=1, j=2, k=1 → sum_left=1, sum_right=5 → 得分=5，dp[1][2]=5。
- [2,3]: i=2, j=3, k=2 → sum_left=5, sum_right=2 → 得分=10，dp[2][3]=10。
len=3：
- [0,2]: i=0, j=2。
  k=0: 左[0,0]右[1,2] → sum_left=3, sum_right=1+5=6 → 得分=dp[0][0]+dp[1][2]+36=0+5+18=23。
  k=1: 左[0,1]右[2,2] → sum_left=3+1=4, sum_right=5 → 得分=dp[0][1]+dp[2][2]+45=3+0+20=23。
  取最大值 23，dp[0][2]=23。
- [1,3]: i=1, j=3。
  k=1: 左[1,1]右[2,3] → sum_left=1, sum_right=5+2=7 → 得分=0+10+1*7=17。
  k=2: 左[1,2]右[3,3] → sum_left=1+5=6, sum_right=2 → 得分=5+0+12=17。
  dp[1][3]=17。
len=4：
- [0,3]: i=0, j=3。
  k=0: 左[0,0]右[1,3] → sum_left=3, sum_right=1+5+2=8 → 得分=0+17+24=41。
  k=1: 左[0,1]右[2,3] → sum_left=3+1=4, sum_right=5+2=7 → 得分=3+10+28=41。
  k=2: 左[0,2]右[3,3] → sum_left=3+1+5=9, sum_right=2 → 得分=23+0+18=41。
  取最大值 41，dp[0][3]=41。

最终结果：41。

算法复杂度

时间复杂度：O(n³)，因为三层循环：区间长度、左端点、分界点。
空间复杂度：O(n²)，存储 dp 表。

关键点总结

定义 dp[i][j] 为合并区间 [i, j] 的最大得分。
状态转移时，最后一次合并的得分是左右两堆石子总数之积。
必须用前缀和快速计算区间和，否则会超时。
枚举分界点 k 时，k 的范围是 [i, j-1]，因为左右区间至少各有一堆石子。

这个问题的变体是“合并石子最小得分”，通常得分定义为两堆石子数量之和，此时合并得分与合并顺序无关（最终总得分固定）。但本题得分定义为数量之积，顺序会影响结果，因此需要用动态规划寻找最优顺序。

合并石子获得最大得分问题（每次合并的得分是两堆石子数量之积，求最大总得分）问题描述假设有一排 n 堆石子，排成一行，每堆石子的数量用一个正整数表示，记为数组 stones[ 0..n-1]。现在你需要通过一系列操作，将这些石子合并成一堆。每次操作，你可以选择相邻的两堆石子，将它们合并成一堆。合并一堆新的石子，其数量等于原来两堆石子的数量之和。每次合并操作会产生一个“得分”，这个得分定义为两堆石子的数量之积。目标是找出一种合并顺序，使得所有操作的总得分之和最大，并返回这个最大总得分。例如，石子堆为 [ 3, 1, 5, 2 ]：一种可能的合并顺序是：先合并 (1, 5) 得 1 5=5 分，新堆为 6，序列变为 [ 3, 6, 2]；再合并 (3, 6) 得 3 6=18 分，新堆为 9，序列变为 [ 9, 2]；最后合并 (9, 2) 得 9* 2=18 分。总得分 = 5+18+18=41。另一种顺序：先合并 (3, 1) 得 3 1=3 分，新堆为 4，序列变为 [ 4, 5, 2]；再合并 (5, 2) 得 5 2=10 分，新堆为 7，序列变为 [ 4, 7]；最后合并 (4, 7) 得 4* 7=28 分。总得分 = 3+10+28=41。但可能有顺序能得到更高得分，我们需要找到最大值。这个问题是典型的区间DP，因为合并操作会改变相邻关系，且最终结果依赖于如何划分最后一步合并的边界。核心思路状态定义：设 dp[ i][ j] 表示合并区间 [ i, j] 内的所有石子堆成一堆时，能获得的最大总得分。其中 0 ≤ i ≤ j < n。最终目标：求 dp[ 0][ n-1 ]。状态转移：考虑最后一次合并区间 [ i, j] 时，一定是将 [ i, j] 分成左右两个区间 [ i, k] 和 [ k+1, j] 分别合并成两堆，再将这两堆合并。设区间 [ i, j ] 的石子总数为 sum(i, j)（前缀和可快速计算）。左区间合并成一堆，石子总数为 sum(i, k)。右区间合并成一堆，石子总数为 sum(k+1, j)。最后合并这两堆的得分为：sum(i, k) * sum(k+1, j)。因此，总得分 = dp[ i][ k] + dp[ k+1][ j] + sum(i, k) * sum(k+1, j)。我们需要枚举分界点 k，取最大值。边界条件：当区间长度为1（即 i == j）时，只有一堆石子，无需合并，得分 dp[ i][ i ] = 0。计算顺序：因为区间长度从短到长计算，所以先枚举区间长度 len 从 2 到 n，再枚举左端点 i，计算出右端点 j = i+len-1，最后枚举分界点 k 从 i 到 j-1。详细步骤步骤1：预处理前缀和为了方便计算任意区间 [ i, j ] 的石子总数，我们先计算前缀和数组 prefix： prefix[ 0] = stones[ 0 ] prefix[ t] = stones[ 0] + stones[ 1] + ... + stones[ t ] （t 从 0 到 n-1）则区间和 sum(i, j) = prefix[ j] - (i > 0 ? prefix[ i-1 ] : 0)。步骤2：初始化DP表创建一个二维数组 dp[ n][ n]，所有值初始化为0。对于长度为1的区间，dp[ i][ i ] 已为0（无需操作）。步骤3：按区间长度递推遍历 len = 2 到 n：遍历左端点 i = 0 到 n - len：右端点 j = i + len - 1。初始化 dp[ i][ j ] 为一个很小的数（如 -∞）或0，因为我们要求最大值。遍历分界点 k = i 到 j-1：计算左区间和 sum_ left = sum(i, k) 计算右区间和 sum_ right = sum(k+1, j) 当前得分 = dp[ i][ k] + dp[ k+1][ j] + sum_ left * sum_ right 用当前得分更新 dp[ i][ j ] 的最大值。步骤4：返回结果 dp[ 0][ n-1 ] 即为最大总得分。例子演示以 stones = [ 3, 1, 5, 2 ] 为例： n=4，前缀和 prefix = [ 3, 4, 9, 11 ]。 len=2： [ 0,1 ]: i=0, j=1, k 只能=0。 sum_ left = sum(0,0)=3, sum_ right=sum(1,1)=1 → 得分=0+0+3* 1=3，dp[ 0][ 1 ]=3。 [ 1,2]: i=1, j=2, k=1 → sum_ left=1, sum_ right=5 → 得分=5，dp[ 1][ 2 ]=5。 [ 2,3]: i=2, j=3, k=2 → sum_ left=5, sum_ right=2 → 得分=10，dp[ 2][ 3 ]=10。 len=3： [ 0,2 ]: i=0, j=2。 k=0: 左[ 0,0]右[ 1,2] → sum_ left=3, sum_ right=1+5=6 → 得分=dp[ 0][ 0]+dp[ 1][ 2]+3 6=0+5+18=23。 k=1: 左[ 0,1]右[ 2,2] → sum_ left=3+1=4, sum_ right=5 → 得分=dp[ 0][ 1]+dp[ 2][ 2]+4 5=3+0+20=23。取最大值 23，dp[ 0][ 2 ]=23。 [ 1,3 ]: i=1, j=3。 k=1: 左[ 1,1]右[ 2,3] → sum_ left=1, sum_ right=5+2=7 → 得分=0+10+1* 7=17。 k=2: 左[ 1,2]右[ 3,3] → sum_ left=1+5=6, sum_ right=2 → 得分=5+0+12=17。 dp[ 1][ 3 ]=17。 len=4： [ 0,3 ]: i=0, j=3。 k=0: 左[ 0,0]右[ 1,3] → sum_ left=3, sum_ right=1+5+2=8 → 得分=0+17+24=41。 k=1: 左[ 0,1]右[ 2,3] → sum_ left=3+1=4, sum_ right=5+2=7 → 得分=3+10+28=41。 k=2: 左[ 0,2]右[ 3,3] → sum_ left=3+1+5=9, sum_ right=2 → 得分=23+0+18=41。取最大值 41，dp[ 0][ 3 ]=41。最终结果：41。算法复杂度时间复杂度：O(n³)，因为三层循环：区间长度、左端点、分界点。空间复杂度：O(n²)，存储 dp 表。关键点总结定义 dp[ i][ j] 为合并区间 [ i, j ] 的最大得分。状态转移时，最后一次合并的得分是左右两堆石子总数之积。必须用前缀和快速计算区间和，否则会超时。枚举分界点 k 时，k 的范围是 [ i, j-1 ]，因为左右区间至少各有一堆石子。这个问题的变体是“合并石子最小得分”，通常得分定义为两堆石子数量之和，此时合并得分与合并顺序无关（最终总得分固定）。但本题得分定义为数量之积，顺序会影响结果，因此需要用动态规划寻找最优顺序。