合并石子获得最小得分问题（线性版本）
题目描述：
有N堆石子排成一排，每堆石子有一定的质量。现在需要将这些石子合并成一堆，合并规则是每次只能合并相邻的两堆石子，合并的代价是这两堆石子的质量之和。请设计一个算法，计算出将所有石子合并成一堆的最小总代价。
解题过程：
让我们用dp[i][j]表示将第i堆到第j堆石子合并成一堆的最小代价。
-
状态定义：
- dp[i][j]：合并从第i堆到第j堆石子的最小代价
- prefix[i]：前i堆石子的质量前缀和，用于快速计算区间和
-
状态转移方程：
对于区间[i,j]，我们可以枚举最后一次合并的位置k，将区间分为[i,k]和[k+1,j]两部分：
dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum(i,j))，其中i ≤ k < j
这里sum(i,j)表示从第i堆到第j堆石子的总质量，可以通过前缀和计算：prefix[j] - prefix[i-1] -
边界条件：
- 当i = j时，dp[i][j] = 0（只有一堆石子，不需要合并）
- 当i < j时，初始化为一个较大值
-
计算顺序：
由于计算大区间需要用到小区间的结果，我们需要按照区间长度从小到大进行计算：- 先计算长度为1的区间（即单堆石子）
- 然后计算长度为2的区间
- 依此类推，直到计算整个区间[1,n]
-
具体步骤示例：
假设有4堆石子，质量分别为[1, 2, 3, 4]步骤1：初始化
dp[1][1] = 0, dp[2][2] = 0, dp[3][3] = 0, dp[4][4] = 0步骤2：计算长度为2的区间
dp[1][2] = dp[1][1] + dp[2][2] + (1+2) = 0 + 0 + 3 = 3
dp[2][3] = 0 + 0 + (2+3) = 5
dp[3][4] = 0 + 0 + (3+4) = 7步骤3：计算长度为3的区间
dp[1][3] = min{
dp[1][1] + dp[2][3] + (1+2+3) = 0 + 5 + 6 = 11,
dp[1][2] + dp[3][3] + 6 = 3 + 0 + 6 = 9
} = 9dp[2][4] = min{
dp[2][2] + dp[3][4] + (2+3+4) = 0 + 7 + 9 = 16,
dp[2][3] + dp[4][4] + 9 = 5 + 0 + 9 = 14
} = 14步骤4：计算整个区间[1,4]
dp[1][4] = min{
dp[1][1] + dp[2][4] + (1+2+3+4) = 0 + 14 + 10 = 24,
dp[1][2] + dp[3][4] + 10 = 3 + 7 + 10 = 20,
dp[1][3] + dp[4][4] + 10 = 9 + 0 + 10 = 19
} = 19 -
时间复杂度：O(n³)，空间复杂度：O(n²)
这个算法通过动态规划系统地考虑了所有可能的合并顺序，确保找到最优的合并方案，是解决此类区间合并问题的经典方法。