合并石头的最低成本问题（K堆合并版本，每轮需合并恰好K堆，最后一轮可少于K堆的特殊规则） 题目描述 给定一个整数数组 stones 表示一堆石子的重量，以及一个整数 K （K ≥ 2）。 你每次可以 合并连续的 K 堆石子 成为一堆，合并的成本是这 K 堆石子的重量总和。 合并后，新堆的重量是这些石子的重量和，新堆和左右相邻的石子保持顺序。 重复合并，直到只剩下一堆石子。 注意 ：如果最后剩余堆数小于 K，可以一次性合并（即使不是 K 堆），这是本题的特殊规则。 问：将所有石子合并成一堆的 最低总成本 。 如果无法通过合并恰好剩下一堆，则返回 -1。 示例 ： stones = [3,2,4,1], K = 2 合并过程（K=2 时即为经典“相邻两堆合并”问题）： 合并 (3,2) 成本 5 → [ 5,4,1 ] 合并 (4,1) 成本 5 → [ 5,5 ] 合并 (5,5) 成本 10 总成本 = 5+5+10 = 20（最优） K=2 时总是可以合并到只剩一堆，但 K>2 时可能无法合并到只剩一堆。 解题思路 这个问题是“石子合并”的推广，但 K 可以大于 2，且允许最后一次合并少于 K 堆。 我们需要判断可行性，并用区间 DP 计算最小成本。 1. 可行性判断 设总堆数 n。 每次合并 K 堆会减少 (K-1) 堆。 最后剩 1 堆，总共减少 (n-1) 堆。 因此必须满足 (n-1) % (K-1) == 0 才能最终合并到 1 堆。 但本题允许最后一轮合并少于 K 堆，意味着 最终合并时堆数可以小于 K ，所以实际上只要 n ≥ 1 就可行吗？ 不对，要仔细分析： 假设最后一次合并前有 m 堆，1 ≤ m < K，可以一次合并成 1 堆。 那倒数第二次合并前堆数必须是 m+(K-1) 吗？不一定，因为每次合并是选连续 K 堆。 实际上，每次合并减少 (K-1) 堆，最终减少 (n-1) 堆，所以 (n-1) 必须能被 (K-1) 整除。 因此可行条件：(n-1) % (K-1) == 0 在这里仍然适用，因为最后一次合并少于 K 堆只是“一次合并”，仍然减少 m-1 堆，总减少量还是 (n-1)，所以必须满足这个整除条件。 但题目说“如果最后剩余堆数小于K，可以一次性合并” ，意味着最后一次合并可以不满足“恰好K堆”的限制。 那这样 (n-1) 不一定能被 (K-1) 整除。 例如 n=4, K=3，每次合并3堆减少2堆，4→1 需要减少3堆，但3不能被2整除，似乎不行。 但我们可以这样做：先合并任意3堆（连续），剩下2堆，最后一轮合并这2堆（小于K=3，允许），这样总合并次数2次，减少3堆，是可行的。 所以可行性条件放宽了：只要 n>1，就总可以合并到1堆（因为最后一轮可以少于K堆）。 但为了 DP 方便，我们仍然可以沿用经典的条件判断吗？ 我们先不判断不可行，DP 过程中能合并到1堆就得到解，否则最后返回-1。 实际上 ，如果 K>n 且 n>1，一次合并（少于K堆）就可以完成，成本是总和。 所以 永远可行 。 但注意：如果 n=1，成本为0。 那我们 DP 目标就是求最小成本，不需要先判断可行性。 2. DP 状态定义 dp[i][j] 表示将区间 [i, j] 内的石子合并到 不能再合并 的状态时的最小成本，这里的“不能再合并”指当前区间内堆数小于 K（但 j-i+1 可能大于等于K，我们需要考虑合并的中间状态）。 更精确的定义（经典 K 堆合并 DP）： dp[i][j] 表示将 [i, j] 合并到 堆数最少 时的最小成本，且最后堆数 = (len-1) % (K-1) + 1 （即合并到不能再合并为止，剩下1堆或多堆）。 但我们想求合并到1堆的成本，所以额外用 cost[i][j] 表示合并到1堆的成本，但这样复杂。 更好的定义 （常见解法）： dp[i][j] 表示将 [i, j] 合并到 堆数小于 K 时的最小成本，并且如果区间长度满足 (len-1) % (K-1) == 0 则最终可合并到1堆，否则合并到多堆。 但这样我们不知道最终是否合并到1堆。 为了知道合并到1堆的成本，我们可以在转移时判断：如果某次合并后区间可合并到1堆，则加上区间总和（最后一次合并的成本）。 标准状态定义 ： dp[i][j] 表示将 [i, j] 合并到不能再合并（堆数 = 1 或 小于K但大于1）的最小成本。 但最终我们只关心合并到1堆的情况，所以我们用 len 判断：当 (len-1) % (K-1) == 0 时，这个区间可合并到1堆，最后一次合并成本是区间总和 sum[i][j] 。 转移方程思路 ： 将 [i, j] 分成左部分 [i, m] 和右部分 [m+1, j] ，左部分合并到堆数 a ，右部分合并到堆数 b ，如果 a+b >= K ，则可以再合并一次，成本增加 sum[i][j] 。 堆数计算： a = (lenL-1) % (K-1) + 1 ， b = (lenR-1) % (K-1) + 1 。 但这样很复杂。 更简单的通用 DP 定义 （常见解法）： dp[i][j] 表示将区间 [i, j] 合并到 堆数最少 的最小成本，堆数 = (len-1) % (K-1) + 1 。 如果 dp[i][j] 的堆数是1，则其值已经包含了所有合并成本。 转移时枚举分割点，但不需要考虑堆数相加，而是直接用： dp[i][j] = min(dp[i][m] + dp[m+1][j]) 对于所有 m，然后如果 (j-i) % (K-1) == 0 则还需要加上 sum[i][j] 。 理由 ： 因为每次合并 K 堆减少 K-1 堆，所以区间长度 len 减少到 (len-1) % (K-1) + 1 堆时无法再合并。 当区间长度 len 满足 (len-1) % (K-1) == 0 时，这个区间可以合并到1堆，并且最后一次合并成本是区间和。 在 DP 中，我们按长度递增计算，当 (len-1) % (K-1) == 0 时，我们在所有分割中选最小 dp[ i][ m]+dp[ m+1][ j] 再加上 sum[ i][ j]；否则不加 sum[ i][ j ]。 3. DP 递推公式 设 prefix[i] 为前 i 个元素和， sum(i,j) = prefix[j+1] - prefix[i] 。 初始化： dp[i][i] = 0 ，区间长度为1时已经是1堆，成本0。 对于区间 [i, j] ，长度 len = j-i+1 ： 枚举分割点 m 从 i 到 j-1，使得 dp[i][j] = min(dp[i][m] + dp[m+1][j]) 。 如果 (len-1) % (K-1) == 0 ，则这个区间可以最终合并到1堆，其最后一次合并成本是 sum(i,j) ，所以： dp[i][j] += sum(i,j) 。 注意：当 (len-1) % (K-1) != 0 时， dp[i][j] 表示合并到多堆的最小成本，但此时不加 sum，因为我们并没有在最后一次合并它们（它们还多堆，不能合并）。 4. 算法步骤 计算前缀和 prefix 。 初始化 dp[n][n] 为0，长度为1的区间成本0。 按长度 len 从 2 到 n 遍历： 对于每个起点 i，终点 j = i+len-1。 初始化 dp[i][j] = INF 。 枚举分割点 m 从 i 到 j-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] 。 答案 = dp[0][n-1] 。 5. 示例 stones = [3,2,4,1], K=3, n=4 。 前缀和: [ 0,3,5,9,10 ]。 len=2: [ 0,1 ]: (2-1)%(3-1)=1%2=1≠0 → 不加 sum。 m=0: dp=0+0=0 → dp[ 0][ 1 ]=0。 [ 1,2 ]: 同理 dp=0。 len=3: [ 0,2 ]: (3-1)%2=2%2=0 → 可合并到1堆。 枚举 m=0: dp[ 0][ 0]+dp[ 1][ 2 ]=0+0=0 m=1: dp[ 0][ 1]+dp[ 2][ 2 ]=0+0=0 min=0，加 sum=3+2+4=9 → dp[ 0][ 2 ]=9。 [ 1,3]: 同理 sum=2+4+1=7 → dp[ 1][ 3 ]=7。 len=4: (4-1)%2=3%2=1≠0 → 不加 sum。 枚举 m=0: dp[ 0][ 0]+dp[ 1][ 3 ]=0+7=7 m=1: dp[ 0][ 1]+dp[ 2][ 3 ]=0+0=0 m=2: dp[ 0][ 2]+dp[ 3][ 3 ]=9+0=9 min=0 → dp[ 0][ 3 ]=0。 最后答案 dp[ 0][ 3]=0？这显然不对，因为我们最终要合并到1堆，但 len=4 不满足加 sum 条件，所以 dp[ 0][ 3 ] 表示合并到多堆的成本，但我们最终要1堆，所以答案应该在 len=4 时能合并到1堆吗？ 检查：4 堆合并到1堆需要一次合并少于K=3堆（允许），所以最后一轮合并2堆，成本 sum=10。 那么我们 dp[ 0][ 3] 应该是先合并成2堆（成本 dp[ 0][ 3 ] 多堆状态），再加最后一次合并成本 10。 所以我们修改： 最终答案 = 对所有可能的合并方式，最终合并到1堆的总成本。 那我们的 dp 只合并到不能再合并（堆数 < K），最终还要一次合并。 所以答案 = min( dp[ i][ j ] 其中区间是整个数组，但最后一次合并是任意的 )，不好算。 正确做法 （标准 K 堆合并 DP，允许最后一次少于K堆）： 我们可以放宽，dp[ i][ j ] 表示合并到1堆的最小成本，如果不可合并到1堆则 INF。 判断区间能否合并到1堆的条件：存在一种划分使得左右合并后堆数相加为 K 或小于K但最后一轮合并。 但这样很复杂。 已知标准解法是： dp[i][j] 表示将区间合并到堆数最少的最小成本，如果 (len-1)%(K-1)==0 则堆数=1，否则堆数>1。 最终答案就是 dp[ 0][ n-1]，但此时如果 (n-1)%(K-1)!=0 怎么办？我们允许最后一轮少于K，所以最终总能合并到1堆，但 dp[ 0][ n-1 ] 没有加最后一次合并成本。 所以我们在 len 满足条件时才加 sum，否则不加，最终 dp[ 0][ n-1 ] 还需再加一次 sum 吗？ 这会产生重复加。 实际上， 允许最后一次少于K堆 意味着： 我们可以在任何区间长度下，最后一步合并任意堆数（≤K）。 所以可以简化： dp[ i][ j] 直接表示合并到1堆的最小成本 ，不管中间步骤。 转移时，我们考虑将 [ i,j ] 分成 K 段（因为最终合并K堆成1堆），但这 K 段不一定连续等长，而是连续 K 个区间，每个区间都已经合并到1堆。 所以转移： dp[i][j] = min(dp[i][m1] + dp[m1+1][m2] + ... + dp[m_{K-1}+1][j]) + sum(i,j) ，其中划分成 K 个连续区间。 这样枚举复杂度高 O(n^K)。 但我们可以优化： 设 dp[i][j][p] 表示将 [ i,j ] 合并成 p 堆的最小成本。 最终答案是 dp[ 0][ n-1][ 1 ]。 转移： dp[i][j][1] = dp[i][j][K] + sum(i,j) （因为 K 堆合并成1堆，加成本 sum）。 dp[i][j][p] = min(dp[i][m][1] + dp[m+1][j][p-1]) 对 m 在 i 到 j-1 枚举。 初始化： dp[i][i][1] = 0 ，其它为 INF。 计算时 p 从 2 到 K。 这是三维 DP，复杂度 O(n^3 * K)。 6. 最终采用的三维DP 定义： dp[i][j][p] = 将 stones[ i..j ] 合并成 p 堆的最小成本（1 ≤ p ≤ K）。 最终目标： dp[0][n-1][1] 。 转移： 当 p == 1： dp[i][j][1] = dp[i][j][K] + sum(i,j) 。 因为要先合并成 K 堆，再合并成 1 堆，加最后一次合并成本。 当 p > 1： dp[i][j][p] = min(dp[i][m][1] + dp[m+1][j][p-1]) 对所有 m 从 i 到 j-1。 意思是左边合并成 1 堆，右边合并成 p-1 堆，组合成 p 堆。 初始化： dp[i][i][1] = 0 （1堆成本0）。 其它为 INF。 计算顺序： 先枚举区间长度 len 从 1 到 n，再枚举 i，j=i+len-1，再枚举 p 从 2 到 K，计算 dp[ i][ j][ p]，最后计算 dp[ i][ j][ 1 ]。 7. 示例计算 stones = [3,2,4,1], K=3 。 n=4, prefix=[ 0,3,5,9,10 ]。 初始化 dp[ i][ i][ 1 ]=0。 len=1: 已初始化。 len=2: 区间[ 0,1 ]，p=2: m=0: dp[ 0][ 0][ 1]+dp[ 1][ 1][ 1]=0+0=0 → dp[ 0][ 1][ 2 ]=0。 p=3: 不可能，因为区间长度2不能合并成3堆，INF。 p=1: dp[ 0][ 1][ 1] = dp[ 0][ 1][ 3 ] + sum=INF+5=INF（不可行）。 所以 [ 0,1 ] 不能合并成1堆，只能成2堆。 区间[ 1,2] 同理 dp[ 1][ 2][ 2 ]=0。 区间 2,3 同理 dp[ 2][ 3][ 2 ]=0。 len=3: 区间[ 0,2 ]，p=2: m=0: dp[ 0][ 0][ 1]+dp[ 1][ 2][ 1] 但 dp[ 1][ 2][ 1] 还未算，因为[ 1,2 ]长度2不能成1堆，所以 INF。 m=1: dp[ 0][ 1][ 1]+dp[ 2][ 2][ 1 ]=INF+0=INF。 所以 dp[ 0][ 2][ 2 ]=INF。 p=3: 需要左边1堆+右边2堆： m=0: dp[ 0][ 0][ 1]+dp[ 1][ 2][ 2]=0+0=0 → dp[ 0][ 2][ 3 ]=0。 p=1: dp[ 0][ 2][ 1] = dp[ 0][ 2][ 3 ] + sum=0+9=9。 区间[ 1,3 ] 同理： p=3: m=1: dp[ 1][ 1][ 1]+dp[ 2][ 3][ 2]=0+0=0 → dp[ 1][ 3][ 3 ]=0。 p=1: dp[ 1][ 3][ 1 ] = 0+7=7。 len=4: 区间[ 0,3 ] p=2: 枚举 m: m=0: dp[ 0][ 0][ 1]+dp[ 1][ 3][ 1 ]=0+7=7 m=1: dp[ 0][ 1][ 1 ] 是 INF，跳过 m=2: dp[ 0][ 2][ 1]+dp[ 3][ 3][ 1 ]=9+0=9 min=7 → dp[ 0][ 3][ 2 ]=7。 p=3: 左边1堆+右边2堆： m=0: dp[ 0][ 0][ 1]+dp[ 1][ 3][ 2]，dp[ 1][ 3][ 2] 未算，因为[ 1,3]长度3，p=2 需要：m=1: dp[ 1][ 1][ 1]+dp[ 2][ 3][ 1]=0+INF=INF，m=2: dp[ 1][ 2][ 1]+dp[ 3][ 3][ 1 ]=INF+0=INF，所以 INF。 m=1: dp[ 0][ 1][ 1 ] INF。 m=2: dp[ 0][ 2][ 1]+dp[ 3][ 3][ 2 ]=9+0=9。 所以 dp[ 0][ 3][ 3 ]=9。 p=1: dp[ 0][ 3][ 1] = dp[ 0][ 3][ 3 ] + sum=9+10=19。 最终答案 dp[ 0][ 3][ 1 ] = 19。 8. 总结 这个问题是“合并石子”的K堆推广，允许最后合并少于K堆。 用三维 DP dp[i][j][p] 表示区间合并成 p 堆的最小成本。 转移分两种情况： 合并成1堆 = 先合并成K堆再加区间和。 合并成p堆（p>1）= 左边1堆 + 右边p-1堆的最小和。 复杂度 O(n^3 * K)，空间可优化。 最终答案是 dp[0][n-1][1] ，如果为 INF 则返回 -1（但本题允许最后少于K堆，所以总是可行，除非n=0）。