合并石头的最低成本问题（K堆合并版本） 题目描述 有 N 堆石头排成一行，第 i 堆有 stones[i] 个石子。每次你可以将 连续的 K 堆 石头合并为一堆，这次合并的成本是这 K 堆石子的总数。请你找出把所有石头合并成一堆的最低成本。如果无法合并成一堆，则返回 -1。 示例 输入： stones = [3,2,4,1] , K = 2 输出： 20 解释： 从 [3, 2, 4, 1] 开始。 合并前两堆，成本 3+2=5，得到 [5, 4, 1] 。 合并前两堆，成本 5+4=9，得到 [9, 1] 。 合并最后两堆，成本 9+1=10，得到 [10] 。 总成本 = 5 + 9 + 10 = 20。 输入： stones = [3,2,4,1] , K = 3 输出： -1 解释：无法合并成一堆（因为每次必须合并连续的 3 堆，最终无法变成 1 堆）。 解题思路 这个问题是“石子合并”的推广，但合并的堆数从 2 变为 K，因此需要判断能否合并成功，并且状态转移会更复杂。我们可以用区间 DP 来解决。 步骤 1：判断可行性 每次合并 K 堆会减少 (K-1) 堆，初始有 N 堆，最终要剩 1 堆，因此需要减少 (N-1) 堆。 设合并次数为 m，则每次减少 (K-1) 堆，总共减少 m* (K-1) 堆，应等于 N-1。 所以必须有： (N-1) % (K-1) == 0 ，否则返回 -1。 步骤 2：定义 DP 状态 设 dp[i][j] 表示将区间 [i, j] 的石头合并成 若干堆 的最小成本，但要求合并后剩余的堆数必须满足 (len - 1) % (K-1) == 0 （len 是区间长度），因为我们需要在区间内逐步合并，直到最后一步可以合并成一堆。 但最终目标是整个区间合并成一堆，即 dp[0][n-1] 。 步骤 3：状态转移 考虑区间 [i, j] ： 如果这个区间长度 len = 1，则 dp[i][j] = 0 （不需要合并）。 否则，我们需要将这个区间分成左右两部分，但注意：合并 K 堆时，我们可能会在中间某个点将左边合并成若干堆，右边合并成若干堆，然后最后一步将左边若干堆和右边若干堆合并成 K 堆。 更简单的做法是：我们枚举一个分割点 m ，将区间分成 [i, m] 和 [m+1, j] ，并考虑将这两个子区间合并后的剩余堆数。 但这样直接枚举合并点会比较复杂，因为合并 K 堆需要知道子区间合并后的堆数。 一个更清晰的思路是： 我们只考虑在 [i, j] 内进行合并，直到最后一步将 K 堆合并成 1 堆。 我们可以枚举一个分割点 m ，使得左边 [i, m] 合并成 1 堆，右边 [m+1, j] 合并成 (K-1) 堆，然后最后一步合并这 K 堆。但这样会限制合并方式。 实际上，标准解法是： 预处理前缀和 prefix ，方便计算区间和。 定义 dp[i][j] 为合并区间 [i, j] 的最小成本，不要求合并成一堆，但要求合并后的堆数为 (len-1) % (K-1) + 1 （这是区间合并后可能剩余的堆数，因为每次合并减少 K-1 堆）。 转移时，我们枚举一个分割点 m ，将区间分成 [i, m] 和 [m+1, j] ，然后考虑将这两个子区间合并： 如果 (m-i) % (K-1) == 0 且 (j-(m+1)) % (K-1) == 0 ，那么左边可以合并成一堆，右边也可以合并成一堆，但这样最后一步合并两堆时，如果 K>2 就不对。 所以更通用的方法是： 我们只在可以合并成一堆的时候才加上区间和 。 更准确的状态转移是： 然后，如果区间长度满足 (len-1) % (K-1) == 0 ，说明可以合并成一堆，那么最后一次合并的成本是整个区间和，所以： 因为区间长度 len = j-i+1，所以 (len-1) % (K-1) == 0 等价于 (j-i) % (K-1) == 0。 步骤 4：初始化 dp[i][i] = 0 ，因为一个石头不需要合并。 步骤 5：计算顺序 按区间长度从小到大计算。 步骤 6：最终答案 dp[0][n-1] 就是整个区间合并成一堆的最小成本。 示例推导 stones = [3,2,4,1] , K=2 , N=4, (4-1)%(2-1)=3%1=0，可行。 前缀和: [ 0,3,5,9,10 ] 区间长度 1: dp[ i][ i ]=0 区间长度 2: [ 0,1]: dp[ 0][ 1] = dp[ 0][ 0]+dp[ 1][ 1 ] + sum(0,1) = 0+0+5=5 [ 1,2]: dp[ 1][ 2 ] = 0+0+6=6 [ 2,3]: dp[ 2][ 3 ] = 0+0+5=5 区间长度 3: [ 0,2 ]: 枚举 m=0,1 m=0: dp[ 0][ 0]+dp[ 1][ 2 ] = 0+6=6 m=1: dp[ 0][ 1]+dp[ 2][ 2 ] = 5+0=5 取 min=5，但长度 3 不满足 (j-i)%(K-1)=0（即 2%1=0 满足？这里 j-i=2, 2%1=0 满足，因为 K=2 时总是满足，所以每个区间合并都能成一堆？不对，K=2 时每次合并两堆，所以任何长度区间都能合并成一堆，所以每次都加区间和）。 检查：(j-i)=2, (2)%(2-1)=0，所以加区间和 sum(0,2)=9，dp[ 0][ 2 ]=5+9=14？这里要注意：我们是先取子区间最小和，然后如果满足条件就加整个区间和。 重新算：dp[ 0][ 2 ]=min(6,5)=5，然后 (j-i)%(K-1)=2%1=0，所以加 sum=9，得到 5+9=14。 [ 1,3]: m=1: 0+5=5; m=2: 6+0=6 → min=5; 加 sum(1,3)=7 → dp[ 1][ 3 ]=12 区间长度 4: [ 0,3 ]: m=0: 0+12=12 m=1: 5+5=10 m=2: 14+0=14 min=10, 加 sum(0,3)=10 → dp[ 0][ 3 ]=20 结果 20，与示例一致。 复杂度 时间复杂度 O(N³)，空间复杂度 O(N²)。