合并石头的最低成本问题（K堆合并，每轮合并K堆的推广问题）
1. 问题描述
你面前有 n 堆石头排成一行，第 i 堆有 stones[i] 颗石头。
每次操作，你可以将 连续的 K 堆石头 合并为一堆，这次操作的成本等于这 K 堆石头的总数。
你需要将所有的石头合并成一堆，如果无法做到，则返回 -1，否则返回最小总成本。
示例
stones = [3,2,4,1]，K = 3
- 第一次合并
[3,2,4]→ 得到9，成本 9，数组变为[9,1] - 此时只有 2 堆，K=3 无法合并，所以这个操作顺序不可行。
- 实际上正确的顺序是：先合并
[2,4,1]→ 成本 7，得到[3,7]，再合并这两堆（K=3 无法合并）？这里 K=3，最后必须 3 堆一起合并，但最终只剩 2 堆，所以不可能完成。
实际上，这个例子在 K=3 时最终不可能合并成一堆。
条件
- 1 <= K <= n
- 如果不能通过若干次合并成一堆，则返回 -1
2. 能否合并的判断
考虑每次合并 K 堆变成 1 堆，相当于每次减少 K-1 堆。
开始有 n 堆，合并一次后变成 n - (K-1) 堆。
要最终变成 1 堆，需要满足：
n - m*(K-1) = 1，其中 m 是合并次数，m 是整数。
即 (n-1) % (K-1) == 0 才能合并成一堆。
结论：如果不满足这个条件，直接返回 -1。
3. 定义动态规划状态
设 dp[i][j] 表示将区间 [i, j] 内的石头合并到不能再合并（即合并到尽可能少的堆数）的最小成本。
注意这里并不是要求区间必须合并成 1 堆，因为可能区间长度不足 K 堆，无法合并成 1 堆，只能合并到 (len-1) % (K-1) + 1 堆。
我们引入另一个状态：piles[i][j] 表示区间 [i, j] 合并后剩下的堆数。但我们可以用 (len-1) % (K-1) + 1 知道最后剩几堆。
更简单的方法是，在 DP 转移时，我们只合并那些能合并成 1 堆的子区间，然后累加成本。
标准做法：
dp[i][j] 表示合并区间 [i, j] 到不能继续合并的最小成本。
我们可以枚举最后一次合并的位置，但最后一次合并是合并 K 堆成 1 堆，这 K 堆每一堆自身可能是由更小区间合并而来的。
4. 动态规划转移方程
设 pref[i] 表示前 i 堆石头的重量和（前缀和），则区间和 sum(i,j) = pref[j+1] - pref[i] 方便计算。
我们定义 dp[i][j] 为将 [i, j] 合并到尽可能少的堆数的最小成本。
如果区间长度 len = j-i+1 小于 K，则不能合并成 1 堆，只能保持原样（成本 0），但如果我们要合并整个大区间，我们需要在内部先合并一些子区间，使它们能组成 K 堆再合并。
关键观察：
如果 (len-1) % (K-1) == 0，则这个区间能合并成 1 堆，否则会剩下 (len-1) % (K-1) + 1 堆。
转移思路：
我们先不管最终能否合并成 1 堆，我们考虑在区间 [i, j] 中，最后一次合并发生在哪里？
我们可以从 i 开始，每次取一个分界点 mid，将区间分成 [i, mid] 和 [mid+1, j]，但这两个子区间不一定能各自合并成 1 堆，它们可能分别剩下若干堆，加起来堆数等于 K 时，就可以合并一次，成本等于这两个子区间的总石头数（即 sum(i, j)）。
更直接的 DP 设计：
设 dp[i][j] 表示将 [i, j] 合并到不能合并的最小成本。
转移时，我们枚举一个分界点 mid，将区间分成 [i, mid] 和 [mid+1, j]，并计算它们的成本之和。
但这样会漏掉合并成本，因为合并 K 堆成 1 堆时，需要额外加上这 K 堆的总和。
正确方法：
我们让 dp[i][j] 表示将 [i, j] 合并到堆数尽可能少的最小成本，但合并操作的成本只在“最后一次合并”时加上。
为了知道何时能合并，我们可以用另一个状态 m 表示将区间合并成 m 堆的最小成本，但这样状态太多。
常用技巧：
dp[i][j] 表示合并区间 [i, j] 到只剩一堆的最小成本（如果区间长度不足以合并成一堆，则 dp=无穷大）。
但我们只对 (len-1) % (K-1) == 0 的区间计算合并成一堆的成本。
标准转移方程（K 堆合并推广问题的常见解法）：
dp[i][j] = min(dp[i][mid] + dp[mid+1][j]) for mid from i to j-1 step (K-1)
为什么 step 是 K-1？
因为左区间合并后剩下的堆数如果是 (lenL-1) % (K-1) + 1，右区间剩下的堆数是 (lenR-1) % (K-1) + 1，我们希望左右合并时，它们加起来堆数 >= K 时才可能合并。
但为了简化，我们只考虑 mid 的步长为 K-1，这样左区间长度 mid-i+1 满足 (lenL-1) % (K-1) == 0 时左区间可合并成 1 堆，右区间同理，但这样不够通用。
更准确的方法（标准解法）：
我们令 dp[i][j] 表示将 [i, j] 合并到堆数最少时的最小成本。
如果区间长度 len 满足 (len-1) % (K-1) == 0，则这个区间可以合并成 1 堆，并且合并的最后一步成本是 sum(i, j)，这个成本要加上。
转移方程：
dp[i][j] = min(dp[i][m] + dp[m+1][j]) for m = i, i+1, ..., j-1
但只有当 (lenL-1) % (K-1) == 0 时，左右子区间合并成 1 堆，然后左右加起来是 2 堆，但我们需要 K 堆才能合并，所以这里不匹配。
真正的关键：
我们不需要在 DP 状态里区分剩下几堆，我们只关心合并成本。当左右子区间合并后的堆数加起来等于 K 时，我们可以将它们合并成一堆，成本是 sum(i, j)。
但如何知道左右子区间合并后各剩几堆？
- 区间长度 L 合并后最少堆数 =
(L-1) % (K-1) + 1。
所以，如果我们把区间分成 [i, m] 和 [m+1, j]，左区间剩 (lenL-1) % (K-1) + 1 堆，右区间剩 (lenR-1) % (K-1) + 1 堆。
如果这两个数加起来大于等于 K，我们就可以合并一次，但每次合并是 K 堆合并成 1 堆，所以需要等于 K 时才合并。
但这里我们可以在 DP 时，只在左右子区间剩下的堆数加起来等于 K 时，才加上合并成本 sum(i, j)。
最终标准方程（LeetCode 1000. Minimum Cost to Merge Stones 解法）：
定义 dp[i][j] 为将 [i, j] 合并到不能再合并的最小成本。
转移：
dp[i][j] = min(dp[i][m] + dp[m+1][j]) for m = i, i+1, ..., j-1
如果 (j-i) % (K-1) == 0，说明这个区间最后可以合并成一堆，那么最后一步的成本是 sum(i, j)，要额外加上。
但这样会重复加成本，因为子区间合并成本已经包含了它们内部合并的成本，最后一步合并 K 堆时，成本是这 K 堆的总和，即整个区间和，这个成本只在最后一步加一次。
所以正确的处理是：
在 dp[i][j] 转移时，不直接加 sum(i, j)，而是当 (j-i) % (K-1) == 0 时，dp[i][j] += sum(i, j)。
算法步骤：
- 如果
(n-1) % (K-1) != 0，返回 -1。 - 计算前缀和
pref。 - 初始化
dp[n][n]为 0，长度 1 的区间成本为 0。 - 按长度从小到大枚举区间长度
len从 2 到 n。 - 枚举左端点 i，右端点 j = i+len-1。
- 初始化
dp[i][j] = INF。 - 枚举分割点 m 从 i 到 j-1，步长 1，
dp[i][j] = min(dp[i][j], dp[i][m] + dp[m+1][j])。 - 如果
(len-1) % (K-1) == 0，则dp[i][j] += sum(i, j)。 - 最终
dp[0][n-1]即为答案。
5. 举例说明
stones = [3,5,1,2,6], K=3
n=5, (5-1)%(3-1)=0，可以合并。
前缀和: 0,3,8,9,11,17
len=2:
- [0,1]: 分割 m=0, dp=0+0=0, (2-1)%2=1≠0，不加区间和。
- 同理其他 len=2 区间 dp=0。
len=3:
[0,2]: m=0 左[0,0]右[1,2]，dp=0+?
先算[1,2]: len=2, dp=0, (2-1)%2=1≠0，不加和。
所以 dp[0,2] = min(dp[0,0]+dp[1,2]=0, dp[0,1]+dp[2,2]=0) = 0
然后检查 (3-1)%2=0，所以加 sum(0,2)=3+5+1=9，dp[0,2]=9。
继续计算到 len=5:
[0,4]: 枚举分割 m，取最小成本分割，最后 (5-1)%2=0，加 sum(0,4)=17。
最终结果就是最小总成本。
6. 时间复杂度
区间 DP 三层循环：O(n³)。
空间复杂度 O(n²)。
7. 核心思想总结
- 先判断是否能合并成一堆：
(n-1) % (K-1) == 0。 - 定义 dp[i][j] 为合并区间 [i,j] 到不能再合并的最小成本。
- 转移时，枚举中间分割点，将区间分成左右两部分，成本相加。
- 如果当前区间长度满足可以合并成一堆（即 (len-1)%(K-1)==0），则加上整个区间和的成本，这对应最后一次合并 K 堆成 1 堆的操作成本。
- 最终 dp[0][n-1] 就是答案。
这个解法避免了记录区间合并后的堆数，通过条件判断何时加合并成本，从而得到最小总成本。