合并石头的最低成本问题（K堆合并，K≥2）

题目描述

你面前有 n 堆石头排成一列，第 i 堆有 stones[i] 个石子。
你的目标是将所有石头合并成一堆。
合并规则如下：

1. 每次必须合并 恰好 K 堆连续的相邻石头（K ≥ 2，固定给出）。
2. 合并成本 = 被合并的 K 堆石子的数量之和。
3. 合并后，原来的 K 堆变成一堆，其石子数 = 那 K 堆石子总数，新的一堆放在原来的最左侧位置（但顺序不影响后续计算）。

问：将所有石头合并成一堆的 最小总成本，如果不可能合并成一堆，返回 -1。

示例
输入：stones = [3,2,4,1], K = 3
输出：-1
解释：n=4, K=3，第一次合并3堆，变成2堆，然后无法再合并3堆，所以不可能合并成一堆。

输入：stones = [3,2,4,1], K = 2
输出：20
解释：K=2 是经典相邻两堆合并，最优合并方式为：
(3+2)=5, 成本5, 数组→[5,4,1]
(4+1)=5, 成本5, 数组→[5,5]
(5+5)=10, 成本10, 总成本=5+5+10=20。

输入：stones = [3,5,1,2,6], K = 3
输出：25
解释：合并顺序：
先合并 [3,5,1] → 成本9, 数组→[9,2,6]
再合并 [9,2,6] → 成本17, 总成本=9+17=25。

解题思路

这是经典的“K 堆相邻合并”问题的推广，K=2 时就是标准的“石子合并”问题。
难点在于：

1. 判断可行性。
2. 合并时必须一次合并 K 堆，不能多不能少，因此状态转移需要考虑中间状态。

步骤 1：可行性判断

设初始有 n 堆，每次合并 K 堆会减少 (K-1) 堆。
最终要变成 1 堆，总共要减少 (n-1) 堆。
所以必须有：

\[n-1 \ \text{能被} \ (K-1) \ \text{整除} \]

否则返回 -1。

步骤 2：区间 DP 定义

设 dp[i][j] 表示将区间 [i, j] 内的所有石头合并成尽可能少的堆所需的最小成本。
注意：我们最终要将整个区间合并成一堆，但中间状态可以允许不是一堆，而是若干堆，但这些堆的数量必须满足某种约束，使得最终能继续合并成一堆。

关键观察：

• 如果 len = j-i+1 是原始的一段石头，我们要把它合并成一堆，必须满足合并过程中的堆数变化规律。
• 更通用的定义是：dp[i][j] 表示将区间 [i, j] 合并成尽可能少的堆数时的最小成本。这个“尽可能少的堆数”是多少？
  合并过程的堆数变化：初始堆数 = len，每次合并 K 堆 → 堆数减少 (K-1) 堆。
  所以最后剩下的堆数 m 必须满足：

\[ len - t(K-1) = m \]

其中 t 是合并次数，m 是 1 ~ K-1 之间的整数，且 m=1 时刚好能完全合并成一堆。
实际上 m = (len-1) mod (K-1) + 1。
例如 K=3, len=4: 4 → 合并一次3堆 → 剩下 2 堆，无法再合并成1堆。
所以我们允许 dp 记录合并成 m 堆的最小成本，m 是 len 对应的最少可能堆数。

但为了方便，另一种更常见的 DP 定义是：
dp[i][j] 表示将区间 [i, j] 合并成尽可能少的堆，并且这个堆数 = 1 时（即能完全合并成一堆）的最小成本，否则为无穷大（表示这段区间内无法完全合并成一堆）。

但这样定义的话，我们需要在中间步骤允许区间合并成多堆，因为最后一步才能合并成一堆。
所以更好的方法是增加一维表示堆数：
dp[i][j][m] 表示将区间 [i, j] 合并成 m 堆的最小成本（1 ≤ m ≤ K）。
但我们最终只需要 dp[0][n-1][1]。

这个三维 DP 复杂度 O(n³·K)，比较高，但可以优化成二维。

步骤 3：二维 DP 定义（优化）

设 dp[i][j] 表示将区间 [i, j] 合并成可能的最少堆数时的最小成本，并且这个堆数 = (j-i) mod (K-1) + 1（即按规则能减少到的最少堆数）。

为什么这样定义可行？
因为对于任意区间，我们只关心在最优合并过程中，最后一次合并前的状态：那时一定是 K 堆，然后合并成一堆。
所以我们只需要保证在中间状态，子区间合并成的堆数能拼成 K 堆，而不必记录堆数维度。

具体转移思路：

• 如果区间长度 len 满足 (len-1) % (K-1) == 0，则这段区间可以完全合并成一堆，它的最小成本可以从更小的区间合并得到。
• 我们总是可以将区间分成左右两部分，左区间合并成若干堆，右区间合并成若干堆，如果左区间的堆数 + 右区间的堆数 = K，则可以将它们合并成一堆，成本增加左右区间总石子数之和。
• 但为了不增加堆数维度，我们可以用另一种等价方法：
  设 dp[i][j] 表示合并区间 [i, j] 到不能再合并（即堆数 = 1 或 小于K堆但无法再合并）时的最小成本。但这样不方便直接转移。

实际上标准解法是：
定义 dp[i][j] 为将区间 [i, j] 合并成尽可能少的堆的最小成本，并且允许不合并成一堆，但记录合并过程中的成本。
我们引入前缀和 sum[i..j] 表示区间石子总数，则合并一次 K 堆时，成本会增加这 K 堆石子总数，这个总数是若干子区间的和。

正确的二维 DP 状态：
dp[i][j] 表示将区间 [i, j] 合并到不能继续合并（即堆数 = 1 或 (len-1) mod (K-1) != 0 时的最少堆数）的最小总成本。
转移时，我们枚举最后一个合并点，但最后一个合并必须合并 K 堆，所以我们要考虑将区间分成 K 段。

但这样会变成 O(n^K)，不可行。

步骤 4：标准二维 DP 解法

标准解法如下（无需堆数维度）：

1. 计算前缀和 prefix，prefix[i] 表示 stones[0..i-1] 的和（prefix[0]=0）。
2. 定义 dp[i][j] 表示将区间 [i, j] 合并到不能再合并的最小成本。
   “不能再合并”意思是堆数 = 1 或 堆数 < K。
   最终目标是 dp[0][n-1] 且长度满足可合并成一堆。

转移方程：

• 如果区间长度 len 满足 (len-1) % (K-1) == 0，则这段可以合并成一堆，它的成本是：

\[ dp[i][j] = \min_{t} \left( dp[i][t] + dp[t+1][j] \right) + (prefix[j+1]-prefix[i]) \]

其中 t 从 i 到 j-1 以步长 (K-1) 枚举。为什么步长是 K-1？因为左区间合并后的堆数必须满足与右区间合并后的堆数之和为 K。
实际上，我们只需枚举分割点，使得左区间长度满足 (lenL-1) % (K-1) == 0 和右区间长度满足 (lenR-1) % (K-1) == 0 同时成立，但这样太麻烦。更简单的办法是：
我们并不在状态中记录堆数，而是在合并时，只在区间长度满足 (len-1)%(K-1)==0 时才加上区间和，否则不加。

实际上标准做法是：
dp[i][j] 表示将区间 [i, j] 合并到最少堆数时的最小成本，而这段区间的堆数是确定的 = (len-1) mod (K-1) + 1。
转移时，我们枚举中间点 m，将区间分成 [i, m] 和 [m+1, j]，那么：

• 合并 [i, m] 的成本是 dp[i][m]，堆数 p = (m-i) mod (K-1) + 1。
• 合并 [m+1, j] 的成本是 dp[m+1][j]，堆数 q = (j-(m+1)) mod (K-1) + 1。
• 如果 p+q ≥ K，则可以继续合并，但为了不增加维度，我们可以这样处理：
  在 dp[i][j] 的计算中，只有在 (len-1) % (K-1) == 0 时才加上区间和，否则不加。
  为什么？因为加上区间和意味着这 K 堆被合并成一堆，此时成本增加区间石子总数。而合并 K 堆的操作只发生在最后一步合并时。

所以最终方程：

\[dp[i][j] = \min_{m} \left( dp[i][m] + dp[m+1][j] \right) + \begin{cases} sum(i,j) & \text{if } (j-i) \bmod (K-1) == 0 \\ 0 & \text{otherwise} \end{cases} \]

其中 sum(i,j) 是 stones[i]+...+stones[j]。

步骤 5：举例说明方程

例：stones=[3,5,1,2,6], K=3, n=5。
检查可行性：(5-1)%(3-1)=0，可行。

初始化 dp 全 0（因为单个石子不需要合并，成本0）。

区间长度 len=2:
(i,j)=(0,1): (2-1)%2=1≠0，所以 dp=dp[0][0]+dp[1][1]+0=0。
(i,j)=(1,2): 同样 0。
... 所有 len=2 的 dp=0 且不加和。

区间长度 len=3:
(0,2): (3-1)%2=0 → 要加和 sum=3+5+1=9。
dp[0][2] = min over m:

• m=0: dp[0][0]+dp[1][2]=0+0=0
• m=1: dp[0][1]+dp[2][2]=0+0=0
  所以 dp=0+9=9。
  这意味着合并 [3,5,1] 成本 9，可以合并成一堆。

区间长度 len=4:
(1,4): (4-1)%2=1≠0 → 不加和。
枚举 m，取最小。
最后计算 (0,4): (5-1)%2=0 → 加和 sum=3+5+1+2+6=17。
枚举分割点 m，看 dp[0][m]+dp[m+1][4] 最小。
最终得到 25。

步骤 6：算法步骤

1. 如果 (n-1) % (K-1) != 0，返回 -1。
2. 计算前缀和 prefix，prefix[k] = sum(stones[0..k-1])。
3. 初始化 dp[n][n]=0。
4. 按长度 len 从 2 到 n 枚举：
   对于每个起点 i=0..n-len，j=i+len-1：
   • 先设 dp[i][j] = ∞。
   • 枚举分割点 m 从 i 到 j-1，步长 (K-1)（因为这样能保证左右区间合并后的堆数能匹配）：
     dp[i][j] = min(dp[i][j], dp[i][m] + dp[m+1][j])。
   • 如果 (len-1) % (K-1) == 0，则 dp[i][j] += prefix[j+1]-prefix[i]。
5. 返回 dp[0][n-1]。

步骤 7：代码（思路示意，非完整实现）

def mergeStones(stones, K):
    n = len(stones)
    if (n - 1) % (K - 1) != 0:
        return -1
    
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + stones[i]
    
    dp = [[0] * n for _ in range(n)]
    
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for m in range(i, j, K - 1):
                dp[i][j] = min(dp[i][j], dp[i][m] + dp[m + 1][j])
            if (length - 1) % (K - 1) == 0:
                dp[i][j] += prefix[j + 1] - prefix[i]
    
    return dp[0][n - 1]

步骤 8：复杂度分析

• 时间复杂度：O(n³ / K)，因为内层循环 m 的步长是 K-1。
• 空间复杂度：O(n²)。

总结

这个问题的核心在于理解“每次合并 K 堆”对区间长度和合并堆数的约束，并用前缀和计算合并成本。
状态转移时，只在区间长度满足“可合并成一堆”时才加上区间和，其余情况只记录子区间合并成本的最小和。