石子合并问题（每次合并得分等于两堆石子数量的乘积，求最大总得分）

题目描述

有一排 n 堆石子排成一行，其中第 i 堆有石子 stones[i] 个（stones[i] > 0）。
游戏规则：每次只能合并相邻的两堆石子，合并的得分等于这两堆石子的数量乘积。合并后，这两堆石子合并为一堆，其石子数为原来两堆石子数之和。不断重复合并操作，直到只剩下一堆石子为止。

要求：计算将所有石子合并为一堆的最大总得分。

示例：
输入：stones = [3, 2, 4, 1]
输出：最大总得分为某个值（我们后面计算）。

解题思路分析

这是一个典型的区间动态规划问题，因为：

1. 操作对象是数组中的一个连续区间。
2. 合并操作会导致区间长度减小，最终合并成整个区间。
3. 合并的得分与区间内的石子总数相关。

关键点与状态设计

假设我们合并区间 [i, j]（1 ≤ i ≤ j ≤ n），最后一步一定是将 [i, k] 与 [k+1, j] 两堆合并，其中 k 是分界点（i ≤ k < j）。

合并得分 = （[i, k] 的石子总数）×（[k+1, j] 的石子总数）。

由于合并顺序不同会导致乘积得分不同，我们需要枚举所有可能的分割点 k，找到最大得分。

状态定义

令：

• dp[i][j] 表示将区间 [i, j] 内的所有石子合并为一堆时，能获得的最大总得分。
• sum[i][j] 表示区间 [i, j] 的石子总数。

为了快速求区间和，可以预先计算前缀和数组 prefix，其中：

\[prefix[x] = stones[0] + stones[1] + \dots + stones[x-1] \]

约定 prefix[0] = 0，则：

\[sum[i][j] = prefix[j+1] - prefix[i] \]

状态转移方程

对于区间 [i, j]，我们枚举最后一个合并的分割点 k（i ≤ k < j）：

1. 先将 [i, k] 合并为一堆，得分为 dp[i][k]，这堆石子数为 sum[i][k]。
2. 再将 [k+1, j] 合并为一堆，得分为 dp[k+1][j]，石子数为 sum[k+1][j]。
3. 最后将这两堆合并，得分 = sum[i][k] * sum[k+1][j]。
4. 总得分 = dp[i][k] + dp[k+1][j] + sum[i][k] * sum[k+1][j]。

因此：

\[dp[i][j] = \max_{i \le k < j} \left( dp[i][k] + dp[k+1][j] + sum[i][k] \times sum[k+1][j] \right) \]

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

计算顺序

区间 DP 通常按区间长度从小到大的顺序计算：

1. 先计算长度为 1 的区间（dp[i][i] = 0）。
2. 再计算长度为 2 的区间（dp[i][i+1]）。
3. 逐步增加长度，直到长度为 n。

示例演算

以 stones = [3, 2, 4, 1] 为例（下标从 0 开始，但为方便理解，我们按 1-based 推导）：

n = 4，石子数组：[3, 2, 4, 1]
前缀和 prefix（1-based）：

• prefix[0] = 0
• prefix[1] = 3
• prefix[2] = 5
• prefix[3] = 9
• prefix[4] = 10

则：
sum[i][j] = prefix[j] - prefix[i-1] （1-based 下标）

计算 dp（1-based 下标）：

长度 L=1：

• dp[1][1] = 0, dp[2][2] = 0, dp[3][3] = 0, dp[4][4] = 0

长度 L=2：

• [1,2]: sum[1][1]=3, sum[2][2]=2, dp[1][2] = 0+0+3*2 = 6
• [2,3]: sum[2][2]=2, sum[3][3]=4, dp[2][3] = 0+0+2*4 = 8
• [3,4]: sum[3][3]=4, sum[4][4]=1, dp[3][4] = 0+0+4*1 = 4

长度 L=3：

• [1,3]：枚举 k=1,2
  • k=1: dp[1][1]+dp[2][3] + sum[1][1]sum[2][3] = 0+8 + 3(2+4)=8+18=26
  • k=2: dp[1][2]+dp[3][3] + sum[1][2]sum[3][3] = 6+0 + (3+2)4=6+20=26
  • max = 26
• [2,4]：枚举 k=2,3
  • k=2: dp[2][2]+dp[3][4] + sum[2][2]sum[3][4] = 0+4 + 2(4+1)=4+10=14
  • k=3: dp[2][3]+dp[4][4] + sum[2][3]sum[4][4] = 8+0 + (2+4)1=8+6=14
  • max = 14

长度 L=4：

• [1,4]：枚举 k=1,2,3
  • k=1: dp[1][1]+dp[2][4] + sum[1][1]sum[2][4] = 0+14 + 3(2+4+1)=14+21=35
  • k=2: dp[1][2]+dp[3][4] + sum[1][2]sum[3][4] = 6+4 + (3+2)(4+1)=10+25=35
  • k=3: dp[1][3]+dp[4][4] + sum[1][3]sum[4][4] = 26+0 + (3+2+4)1=26+9=35
  • max = 35

最终答案：dp[1][4] = 35

代码框架（C++风格）

#include <vector>
#include <algorithm>
using namespace std;

int maxScoreStoneMerge(vector<int>& stones) {
    int n = stones.size();
    vector<int> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + stones[i];
    }
    auto sum = [&](int i, int j) { // i,j 为 0-based 闭区间
        return prefix[j + 1] - prefix[i];
    };

    vector<vector<int>> dp(n, vector<int>(n, 0));
    // 区间长度从 2 开始
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            int best = 0;
            for (int k = i; k < j; k++) {
                int score = dp[i][k] + dp[k + 1][j] + sum(i, k) * sum(k + 1, j);
                if (score > best) best = score;
            }
            dp[i][j] = best;
        }
    }
    return dp[0][n - 1];
}

复杂度分析

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

总结

这道题是经典的“石子合并”问题的一个变种，区别在于合并得分是两堆石子数的乘积（常见变体是和或平方）。解题步骤：

1. 定义状态 dp[i][j] 为区间合并的最大得分。
2. 利用前缀和快速计算区间和。
3. 枚举最后一步的合并分割点，根据子区间得分与合并乘积得分相加得到当前区间得分。
4. 按区间长度从小到大递推。

这样，我们就得到了最大总得分。