合并石头的最低成本问题 问题描述 有 N 堆石头排成一排，第 i 堆有 stones[ i ] 块石头。每次操作需要将连续的 K 堆石头合并为一堆，这次操作的代价是这 K 堆石头的总数。找出把所有石头合并成一堆的最低成本。如果无法合并成一堆，返回 -1。 问题分析 这是一个典型的区间动态规划问题。我们需要考虑如何将大区间分解为小区间进行合并，并找到最优的合并顺序。 解题步骤 可行性检查 首先检查是否可能合并成一堆。每次合并减少 (K-1) 堆石头，从 N 堆到 1 堆需要减少 (N-1) 堆。因此需要满足：(N-1) % (K-1) == 0 前缀和数组 创建前缀和数组 prefix，其中 prefix[ i ] 表示前 i 堆石头的总重量，用于快速计算任意区间的石头总数。 状态定义 定义 dp[ i][ j] 表示将区间 [ i, j ] 内的石头合并到不能再合并时的最小成本。 状态转移 对于区间 [ i, j ]： 如果区间长度 len = j-i+1 < K，无法合并，dp[ i][ j ] = 0 否则，考虑所有可能的分割点 m，将区间分为 [ i, m] 和 [ m+1, j ] 当 (len-1) % (K-1) == 0 时，说明整个区间可以合并成一堆，此时需要加上整个区间的石头总数 状态转移方程：dp[ i][ j] = min(dp[ i][ m] + dp[ m+1][ j])，如果可合并则加上 prefix[ j+1]-prefix[ i ] 初始化 dp[ i][ i ] = 0（单堆石头不需要合并） 其他位置初始化为一个较大值 计算顺序 按区间长度从小到大计算，确保计算大区间时所有小区间都已计算完成。 示例演示 考虑 stones = [ 3,2,4,1 ], K = 2 可行性：(4-1) % (2-1) = 3 % 1 = 0，可行 前缀和：[ 0,3,5,9,10 ] 计算过程： 长度2：[ 0,1]成本=5, [ 1,2]成本=6, [ 2,3 ]成本=5 长度3：[ 0,2]成本=min(5+6, 0+5)+9=14, [ 1,3 ]成本=min(6+5, 0+5)+10=15 长度4：[ 0,3 ]成本=min(14+5, 5+5, 0+15)+10=20 复杂度分析 时间复杂度：O(N³) 空间复杂度：O(N²) 关键点 只有当区间长度满足特定条件时才能合并成一堆 分割点的步长可以优化为 K-1 的倍数 前缀和数组用于快速计算区间和