石子合并问题（线性版本） 题目描述： 有N堆石子排成一排，每堆石子有一定的数量。现要将所有石子合并成一堆。合并的规则是每次只能将相邻的两堆合并成一堆，每次合并的代价是这两堆石子的数量之和。经过N-1次合并后，最终合并为一堆。求将所有石子合并成一堆的最小总代价。 解题过程： 问题分析 这个问题需要将一排相邻的石子堆合并，每次合并相邻两堆，直到只剩一堆。关键点在于合并顺序会影响总代价。我们需要找到一种合并顺序，使得所有合并步骤的代价总和最小。 状态定义 定义dp[ i][ j]表示将第i堆到第j堆石子合并成一堆所需的最小代价。我们的目标是求dp[ 1][ N ]。 状态转移方程 要合并i到j堆，最后一次合并前一定是将i到k堆和k+1到j堆合并（i ≤ k < j）。因此： dp[ i][ j] = min(dp[ i][ k] + dp[ k+1][ j]) + sum(i,j)，其中i ≤ k < j 这里sum(i,j)表示第i堆到第j堆石子的总数。 预处理前缀和 为了快速计算sum(i,j)，我们预处理前缀和数组prefix，其中prefix[ i]表示前i堆石子的总和，那么sum(i,j) = prefix[ j] - prefix[ i-1 ]。 计算顺序 由于计算dp[ i][ j ]需要知道所有更小区间的结果，我们按区间长度从小到大计算： 先计算长度为1的区间（dp[ i][ i ] = 0，因为单堆无需合并） 再计算长度为2、3...直到N的区间 示例演示 假设有4堆石子：4, 5, 2, 6 前缀和：prefix = [ 0, 4, 9, 11, 17 ] 计算dp[ 1][ 2] = dp[ 1][ 1] + dp[ 2][ 2 ] + sum(1,2) = 0 + 0 + 9 = 9 计算dp[ 2][ 3 ] = 0 + 0 + 7 = 7 计算dp[ 3][ 4 ] = 0 + 0 + 8 = 8 计算dp[ 1][ 3] = min(dp[ 1][ 1]+dp[ 2][ 3], dp[ 1][ 2]+dp[ 3][ 3 ]) + sum(1,3) = min(0+7, 9+0) + 11 = min(7,9) + 11 = 18 计算dp[ 2][ 4] = min(dp[ 2][ 2]+dp[ 3][ 4], dp[ 2][ 3]+dp[ 4][ 4 ]) + sum(2,4) = min(0+8, 7+0) + 13 = min(8,7) + 13 = 20 最终dp[ 1][ 4] = min(dp[ 1][ 1]+dp[ 2][ 4], dp[ 1][ 2]+dp[ 3][ 4], dp[ 1][ 3]+dp[ 4][ 4 ]) + sum(1,4) = min(0+20, 9+8, 18+0) + 17 = min(20,17,18) + 17 = 34 算法复杂度 时间复杂度O(N³)，空间复杂度O(N²)，适用于N较小的情况（通常N ≤ 300）。