LeetCode 1000. 合并石头的最低成本
题目描述
题意分析
石头按顺序排列成若干堆，每次只能把当前相邻的恰好
k堆合成一堆，费用等于这k堆的石头总数。要求最终只剩一堆，并使所有操作费用之和最小；不能完成时返回-1。合并后的堆可以继续参与后续操作，所以同一批石头可能在多次合并中产生费用。限制是相邻且每次恰好
k堆，不能任意选堆，也不能只计算一次全体石头总和。
解法：区间动态规划
核心思路
[!blue]
每次操作把
k堆变成一堆，堆数减少k - 1。从n堆变成一堆，必须满足(n - 1) % (k - 1) == 0。这也足以保证可合并：当剩余堆数还大于一时，它仍是“一加上若干个k - 1”，至少还有k堆，可以继续选相邻的k堆合并。用区间动态规划描述每段石头的最小费用，但不能把所有区间都定义为合成一堆，因为某些区间长度做不到。长度为
len的区间反复合并后，能达到的最少堆数为1 + (len - 1) % (k - 1)，它处于一到k - 1之间；dp[left][right]就表示合并到这个最少堆数所需的最低费用。相邻合并保证每一堆都来自原区间中一段连续石头。若目标保留多堆，就观察最终的这些堆；若目标是一堆，就先观察最后一次合并之前的
k堆。其中第一堆覆盖的左段必须能独立合成一堆，所以左段长度只能是一、再加若干个k - 1。因此枚举分界mid时，从left开始，每次增加k - 1，而不是任意切分。对每个合法分界，先取
dp[left][mid] + dp[mid + 1][right]。若整段的目标剩余堆数大于一，左段的一堆与右段的最少堆数相加，恰好达到整段目标，直接比较这些费用即可。若整段能够合成一堆，最后一次操作之前必然还有
k堆。上述切分会先让左段得到一堆、右段得到k - 1堆，正好凑齐最后一次合并的输入。此时还要支付一次整个区间的石头总数，所以取最小分界费用后，再加区间和。任意最优合并过程都能按“最终第一堆的边界”这样划分，因此枚举没有遗漏；子区间已经取最小费用，组合后也得到当前区间的最小费用。长度小于
k时无法进行任何操作，目标就是保持原有堆数，初始费用为零。按长度递增计算，所需的更短区间都已完成；区间和用前缀和常数时间取得。
解题步骤
- 检查
(n - 1) % (k - 1)，不为零则直接返回-1。- 建立石头数量的前缀和，创建初始为零的区间状态表。
- 从长度
k开始递增枚举区间，先将当前费用设为足够大的值。- 分界从区间左端开始，每次跳过
k - 1，用两个子区间费用之和更新最小值。- 当前长度能合成一堆时，再加上整个区间的石头数量，表示最后一次实际合并。
- 返回整个区间的费用；原本只有一堆时无需操作，答案自然为零。
代码实现
class Solution {
public int mergeStones(int[] stones, int k) {
int n = stones.length;
if ((n - 1) % (k - 1) != 0) {
return -1;
}
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + stones[i];
}
int[][] dp = new int[n][n];
int inf = Integer.MAX_VALUE / 4;
for (int len = k; len <= n; len++) {
for (int left = 0; left + len <= n; left++) {
int right = left + len - 1;
dp[left][right] = inf;
// 左段必须能压成一堆，因此分界每次跨过若干个整组。
for (int mid = left; mid < right; mid += k - 1) {
dp[left][right] = Math.min(dp[left][right], dp[left][mid] + dp[mid + 1][right]);
}
// 整段可压成一堆时，额外支付最后一次合并的区间和。
if ((len - 1) % (k - 1) == 0) {
dp[left][right] += prefix[right + 1] - prefix[left];
}
}
}
return dp[0][n - 1];
}
}
func mergeStones(stones []int, k int) int {
n := len(stones)
if (n-1)%(k-1) != 0 {
return -1
}
prefix := make([]int, n+1)
for i := 0; i < n; i++ {
prefix[i+1] = prefix[i] + stones[i]
}
dp := make([][]int, n)
for i := range dp {
dp[i] = make([]int, n)
}
inf := int(^uint(0)>>1) / 4
for length := k; length <= n; length++ {
for left := 0; left+length <= n; left++ {
right := left + length - 1
dp[left][right] = inf
// 左段必须能压成一堆，因此分界每次跨过若干个整组。
for mid := left; mid < right; mid += k - 1 {
cost := dp[left][mid] + dp[mid+1][right]
if cost < dp[left][right] {
dp[left][right] = cost
}
}
// 整段可压成一堆时，额外支付最后一次合并的区间和。
if (length-1)%(k-1) == 0 {
dp[left][right] += prefix[right+1] - prefix[left]
}
}
}
return dp[0][n-1]
}
复杂度分析
设初始堆数为 $n$。
- 时间复杂度：上界为 $O(n^2+n^3/(k-1))$。二维状态初始化需要 $O(n^2)$，每个区间按步长 $k-1$ 枚举分界，区间和查询为常数时间。
- 辅助空间复杂度：$O(n^2)$，用于区间状态表，前缀和另占 $O(n)$。
关键点总结
[!green]
- 剩余堆数由区间长度模
k - 1决定，因此二维状态就能表达所需目标。- 分界步长保证左段能合成一堆，右段再提供其余目标堆。
- 只有整段实际进行最后一次合并时才加区间和。
- 短于
k的区间不做操作，零费用是合法状态，不是未计算标记。
易错点总结
[!yellow]
- 把每个
dp都解释为合成一堆，会让许多本来有意义的中间状态被误判为不可达。- 分界逐个移动而不限制左段堆数，可能拼出多余的堆，却漏算继续合并的费用。
- 每个区间都加总和，会给尚未合成一堆的区间凭空增加一次操作费用。
- 能合成一堆时忘记加区间和，又会漏掉最后一次合并。
- 将所有短区间初始化为无穷大，会破坏“保持原有堆数、费用为零”的递推起点。
- 必须先按长度从短到长计算，不能在子区间尚未得到最优值时使用它。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1547. 切棍子的最小成本 | 困难 | 同样选择分割结构并累计区间总成本，原题切开木棍，本题合并相邻石堆。 |