石子合并问题（相邻合并，最小成本） 题目描述： 有N堆石子排成一排，每堆石子有一定的数量。现要将所有石子合并成一堆，合并的规则是：每次只能选择相邻的两堆石子合并成一堆，合并的代价为这两堆石子的数量之和。经过N-1次合并后，所有石子合并成一堆，求最小的总合并代价。 例如，有4堆石子，数量分别为[ 1, 3, 2, 4 ]，合并过程如下： 合并前两堆：代价1+3=4，石子变为[ 4, 2, 4 ] 合并前两堆：代价4+2=6，石子变为[ 6, 4 ] 合并最后两堆：代价6+4=10，石子变为[ 10 ] 总代价=4+6+10=20 解题过程： 问题分析 这是一个典型的区间动态规划问题。我们需要找到一种合并顺序，使得总代价最小。关键观察是：最后一次合并的代价总是所有石子的总和，但中间过程的合并顺序会影响总代价。 状态定义 定义dp[ i][ j ]表示合并第i堆到第j堆石子的最小代价。 状态转移方程 对于区间[ 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堆石子的总数。 边界条件 当i = j时，dp[ i][ j ] = 0（只有一堆石子，不需要合并） 当i < j时，按状态转移方程计算 计算顺序 由于计算dp[ i][ j]需要知道dp[ i][ k]和dp[ k+1][ j ]，其中k在i和j之间，所以我们应该按区间长度从小到大的顺序计算： 先计算长度为1的区间（即单堆石子） 然后计算长度为2的区间 接着计算长度为3的区间 依此类推，直到计算整个区间[ 1,n ] 前缀和优化 为了快速计算sum[ i][ j ]，我们可以预先计算前缀和数组prefix，其中： prefix[ i ] = 石子1到石子i的总和 那么sum[ i][ j] = prefix[ j] - prefix[ i-1 ] 算法实现步骤 以石子数量[ 1, 3, 2, 4 ]为例： 步骤1：初始化 n = 4 stones = [ 1, 3, 2, 4 ] prefix = [ 0, 1, 4, 6, 10] // prefix[ 0]=0, prefix[ i ]表示前i堆的和 步骤2：初始化dp数组 dp[ i][ i ] = 0（对角线） 步骤3：计算长度为2的区间 dp[ 1][ 2] = dp[ 1][ 1] + dp[ 2][ 2] + sum[ 1][ 2 ] = 0 + 0 + 4 = 4 dp[ 2][ 3 ] = 0 + 0 + 5 = 5 dp[ 3][ 4 ] = 0 + 0 + 6 = 6 步骤4：计算长度为3的区间 dp[ 1][ 3 ] = min( dp[ 1][ 1]+dp[ 2][ 3]+sum[ 1][ 3 ] = 0+5+6=11, dp[ 1][ 2]+dp[ 3][ 3]+sum[ 1][ 3 ] = 4+0+6=10 ) = 10 dp[ 2][ 4 ] = min( dp[ 2][ 2]+dp[ 3][ 4]+sum[ 2][ 4 ] = 0+6+9=15, dp[ 2][ 3]+dp[ 4][ 4]+sum[ 2][ 4 ] = 5+0+9=14 ) = 14 步骤5：计算长度为4的区间（整个区间） dp[ 1][ 4 ] = min( dp[ 1][ 1]+dp[ 2][ 4]+sum[ 1][ 4 ] = 0+14+10=24, dp[ 1][ 2]+dp[ 3][ 4]+sum[ 1][ 4 ] = 4+6+10=20, dp[ 1][ 3]+dp[ 4][ 4]+sum[ 1][ 4 ] = 10+0+10=20 ) = 20 最终结果为dp[ 1][ 4 ] = 20，与示例一致。 时间复杂度 时间复杂度：O(n³)，需要遍历所有区间和所有分割点 空间复杂度：O(n²)，用于存储dp数组 这个算法通过动态规划系统地考虑了所有可能的合并顺序，确保找到最优解。在实际实现时，可以通过四边形不等式等优化技巧将时间复杂度降低到O(n²)。