区间动态规划例题：合并石头的最低成本问题（K堆合并版本） 问题描述 有 N 堆石头排成一行，第 i 堆石头的重量为 stones[i] 。每次操作需要将 连续的 K 堆石头 合并为一堆，合并的成本为这 K 堆石头的总重量。重复合并操作直到只剩下一堆石头，求合并的最小总成本。若无法合并到只剩一堆，返回 -1 。 示例 输入： stones = [3,2,4,1], K = 2 输出： 20 解释： 合并 [ 3,2]，成本=5，数组变为 [ 5,4,1 ] 合并 [ 4,1]，成本=5，数组变为 [ 5,5 ] 合并 [ 5,5 ]，成本=10，总成本=5+5+10=20 解题步骤 1. 问题分析 每次合并需选择连续的 K 堆 ，合并后堆数减少 K-1 。 初始堆数为 N ，最终目标为1堆，需满足： \[ N - m(K-1) = 1 \quad \Rightarrow \quad (N-1) \bmod (K-1) = 0 \] 若不满足，直接返回 -1 。 2. 定义状态 设 dp[i][j] 表示将区间 [i, j] 的石头合并到 无法再合并 时的最小成本（注意：此处不一定合并到只剩1堆，而是合并到满足 (len-1) % (K-1) == 0 的堆数）。 区间长度 len = j-i+1 。 若 (len-1) % (K-1) == 0 ，则区间可合并到1堆；否则会剩余多堆。 3. 状态转移方程 预处理前缀和 prefix ，方便计算区间和。 枚举分割点 m ，将 [i, j] 分成 [i, m] 和 [m+1, j] 。 关键思路： 若 [i, m] 可合并到1堆，且 [m+1, j] 的堆数满足 (len2-1) % (K-1) == 0 ，则两部分合并为一堆的成本为 dp[i][m] + dp[m+1][j] + sum(i, j) 。 但更通用的方法是： \[ dp[ i][ j] = \min_ {m} \left( dp[ i][ m] + dp[ m+1][ j ] \right) \] 若 (j-i) % (K-1) == 0 ，说明区间可合并到1堆，需加上区间和 sum(i, j) 。 4. 初始化与边界 单堆石头无需合并： dp[i][i] = 0 。 其他状态初始化为较大值（如 INT_MAX ）。 5. 计算顺序 按区间长度 len 从小到大计算： len 从 2 到 N 。 对每个 len ，枚举起点 i ，终点 j = i+len-1 。 枚举分割点 m ，步长为 K-1 ，确保左右子区间可合并。 6. 实现细节 检查 (N-1) % (K-1) == 0 。 前缀和： sum(i, j) = prefix[j+1] - prefix[i] 。 状态转移时，若 (j-i) % (K-1) == 0 ，则加上 sum(i, j) 。 7. 示例推导（stones = [ 3,2,4,1], K=2） 前缀和: [0,3,5,9,10] 区间长度2： dp[0][1] = 0+0+5=5 dp[1][2] = 0+0+6=6 dp[2][3] = 0+0+5=5 区间长度3： dp[0][2] = min(dp[0][1]+dp[2][2], dp[0][0]+dp[1][2]) = min(5+0, 0+6)+9=15 dp[1][3] = min(6+0, 0+5)+10=15 区间长度4： dp[0][3] = min(dp[0][1]+dp[2][3], dp[0][0]+dp[1][3], dp[0][2]+dp[3][3]) = min(5+5, 0+15, 15+0) + 10 = 20 最终答案 ： dp[0][N-1] = 20 。 总结 本题通过区间DP处理连续K堆合并，核心在于理解区间合并的可行条件（堆数变化需符合 K-1 的倍数），并通过前缀和优化成本计算。