LeetCode 1000. 合并石头的最低成本

2026-03-23 HGNULB 约 11 分钟

文章信息 7 个分类 3 个标签

分类

题目描述

✅ 1000. 合并石头的最低成本

题意分析

有 n 堆石头排成一行，每次操作必须挑出相邻的 k 堆，把它们合成一堆，付出的代价等于这 k 堆石头数量之和。目标是把全部石头合成一堆，求最小总代价；如果做不到，返回 $-1$。

「相邻」两个字是全题的骨架。合并只能作用在连续的一段上，合并结果仍然占据这段原来的位置，所以整个过程始终保持着一维的区间结构，任何时刻的局面都是「原数组被切成若干连续段，每段已经合成一堆」。这就意味着答案天然可以按区间分解。

可行性不是随便的。一次操作把堆数从 m 变成 $m - (k - 1)$，堆数模 $k - 1$ 的余数永远不变。要从 n 堆走到 $1$ 堆，必须满足 $(n - 1) \bmod (k - 1) = 0$，否则无论怎么操作都到不了终点。

约束里 n 和 k 都不超过 $30$，每堆石头不超过 $100$。规模这么小，说明出题人允许一个三次方甚至更高次的做法，重点考的是状态怎么设计而不是常数怎么压。

边界上，$n = 1$ 时本来就只有一堆，$(1 - 1) \bmod (k - 1) = 0$ 成立，答案是 $0$，不能漏掉这条。另外任何长度小于 k 的区间根本无法发生哪怕一次合并，它的代价必须是 $0$ 而不是「不可达」。

解法：区间动态规划

核心思路

暴力做法是枚举每一步选哪 k 堆来合并，操作序列的数量随 n 呈指数增长，$n = 30$ 时完全不可能。瓶颈在于把「操作顺序」当成了搜索对象，而实际上很多不同顺序会到达同一个中间局面。

换成从结果倒推。看最后一次操作：它把 k 堆合成了一堆，这 k 堆分别覆盖了整个数组的 k 个连续段，且这 k 段首尾相接铺满全数组。最后一次操作的代价恰好是全部石头之和，与前面怎么合并毫无关系。所以真正需要优化的，是「把整个数组切成 k 段、每段各自压成一堆」的最小代价。这一步递归下去，就是区间动态规划。

但直接定义「把区间压成一堆的最小代价」会卡住：长度不合适的区间根本压不成一堆。于是状态改成：dp[i][j] 表示把区间 $[i, j]$ 合并到它所能达到的最少堆数时的最低代价。对长度 $len = j - i + 1$ 的区间，这个最少堆数由 $len$ 唯一确定，等于 $((len - 1) \bmod (k - 1)) + 1$，因为堆数模 $k - 1$ 是不变量。特别地，当 $(len - 1) \bmod (k - 1) = 0$ 时它能被压成 $1$ 堆。

转移分两步。第一步是切分：dp[i][j] = min{ dp[i][mid] + dp[mid + 1][j] }。这里的 mid 不能随便取，必须让左段 $[i, mid]$ 的长度满足 $(mid - i) \bmod (k - 1) = 0$，也就是从 mid = i 起以 $k - 1$ 为步长递增。这样左段能独自压成 $1$ 堆，右段承担剩下的堆数，两段的堆数相加恰好等于整段的最少堆数，拼接才是合法的。第二步是收口：如果整段能压成 $1$ 堆，就在切分得到的最优代价上加一次全段求和，代表最后那次把 k 堆并成一堆的操作。

区间和用前缀和 $O(1)$ 取出。计算顺序按区间长度从小到大，保证转移时用到的两个子区间都已经算完。

解题步骤

先做可行性判断：若 $(n - 1) \bmod (k - 1) \ne 0$ 直接返回 $-1$。放在最前面是因为这是一个全局不变量决定的结论，与石头的具体数值无关，提前挡掉能让后面的状态定义不必考虑「不可达」这种情况。

预处理前缀和数组 prefix，使 prefix[i + 1] - prefix[left] 就是区间和。收口那一步在每个可压成一堆的区间上都要用到区间和，不预处理就要重复扫描，白白多一层循环。

开 $n \times n$ 的 dp，所有长度小于 k 的区间保持默认值 $0$。这不是「未初始化」，而是正确的语义：这样的区间一次操作都做不了，代价确实为 $0$，它已经处在自己能达到的最少堆数（也就是原始堆数）上。

外层按区间长度 len 从 k 递增到 n，内层枚举左端点 left 并算出右端点 right。必须以长度为第一层循环，因为 dp[left][right] 依赖的两个子区间都比它短，按长度递增才能保证依赖先于被依赖者算出。

进入某个区间时先把 dp[left][right] 置为一个足够大的哨兵值，再用切分转移取最小。哨兵取 Integer.MAX_VALUE / 4 而不是最大值本身，是为了给后面的加法留出余量，避免两个哨兵相加溢出成负数。

内层从 mid = left 开始、每次加 $k - 1$ 地枚举切分点，用 dp[left][mid] + dp[mid + 1][right] 更新最小值。步长必须是 $k - 1$：只有这样左段的长度才满足除以 $k - 1$ 余 $1$，能独立压成一堆，两段的剩余堆数才拼得成一个合法局面。

若 $(len - 1) \bmod (k - 1) = 0$，把区间和加到 dp[left][right] 上。这一步是有条件的，因为只有能压成一堆的区间才真的会发生那最后一次合并；对压不成一堆的区间加区间和相当于凭空多付一次代价。

全部算完后返回 dp[0][n - 1]。由于开头已经确认可行，这个区间必然满足收口条件，返回值就是把全部石头合成一堆的最小代价。

以 stones = [3, 5, 1, 2, 6]、k = 3 走一遍：$n = 5$，$(5 - 1) \bmod 2 = 0$，可行。前缀和为 $[0, 3, 8, 9, 11, 17]$。所有长度为 $1$ 和 $2$ 的区间 dp 均为 $0$。

长度为 $3$ 的区间：$[0, 2]$ 的切分点只有 mid = 0（下一个是 $2$，已不小于 right），得到 dp[0][0] + dp[1][2] = 0 + 0 = 0；$(3 - 1) \bmod 2 = 0$ 可收口，加上区间和 $9 - 0 = 9$，所以 dp[0][2] = 9。同理 $[1, 3]$ 只有 mid = 1，得 $0$，加区间和 $11 - 3 = 8$，dp[1][3] = 8。$[2, 4]$ 只有 mid = 2，得 $0$，加区间和 $17 - 8 = 9$，dp[2][4] = 9。

长度为 $4$ 的区间：$[0, 3]$ 的切分点为 mid = 0 与 mid = 2。mid = 0 给出 dp[0][0] + dp[1][3] = 0 + 8 = 8；mid = 2 给出 dp[0][2] + dp[3][3] = 9 + 0 = 9。取最小得 $8$。$(4 - 1) \bmod 2 = 1$ 不为 $0$，不收口，dp[0][3] = 8，它的含义是「把这 $4$ 堆压到 $2$ 堆的最低代价是 $8$」。同理 $[1, 4]$：mid = 1 给出 $0 + 9 = 9$，mid = 3 给出 $8 + 0 = 8$，取 $8$，不收口，dp[1][4] = 8。

长度为 $5$ 的整段 $[0, 4]$：切分点为 mid = 0 与 mid = 2。mid = 0 给出 dp[0][0] + dp[1][4] = 0 + 8 = 8；mid = 2 给出 dp[0][2] + dp[3][4] = 9 + 0 = 9。取最小得 $8$。$(5 - 1) \bmod 2 = 0$ 可收口，加上区间总和 $17$，dp[0][4] = 25。

返回 $25$。对照一下真实操作：先合并 $[3, 5, 1]$ 花费 $9$ 得到 $[9, 2, 6]$，再合并这三堆花费 $17$，总计 $26$；换个顺序，先合并 $[1, 2, 6]$ 花费 $9$ 得到 $[3, 5, 9]$，再合并花费 $17$，总计 $26$；而最优是先合并 $[5, 1, 2]$ 花费 $8$ 得到 $[3, 8, 6]$，再合并花费 $17$，总计 $25$，与推演结果一致。

代码实现

class Solution {
    // 区间 DP 记录的是把一段石头合并到“当前能达到的最少堆数”的最低成本，只有这段长度允许继续压成一堆时才额外加区间和。
    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 {
    // 区间 DP 记录的是把一段石头合并到“当前能达到的最少堆数”的最低成本，只有这段长度允许继续压成一堆时才额外加区间和。
    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]
}

复杂度分析

时间复杂度：$O(n^3 / k)$，其中 n 是石头堆数。状态是所有区间，共 $O(n^2)$ 个；每个状态枚举切分点时步长为 $k - 1$，最多 $O(n / k)$ 个候选，每个候选只做一次加法和一次比较；区间和靠前缀和 $O(1)$ 取出。$n = k = 30$ 时总量在万级以内。

空间复杂度：$O(n^2)$，二维 dp 要保留全部区间的结果，因为长区间的转移会回查任意更短区间，无法按行滚动；前缀和数组只占 $O(n)$，量级更低。

关键点总结

先找不变量再设计状态。堆数模 $k - 1$ 恒定既给出了 $-1$ 的判据，又决定了任意区间「最少能压到几堆」是由长度唯一确定的，这两件事合起来才让二维状态足以描述问题，不必再加一维记录堆数。

状态的定义要能覆盖所有子问题，而不是只覆盖你关心的那些。把 dp[i][j] 定义成「压成一堆的代价」会在长度不合适时无解，改成「压到最少堆数的代价」之后每个区间都有定义，转移才连得起来。

切分点的枚举步长不是优化技巧而是正确性要求。步长 $k - 1$ 保证了左段恰好压成一堆，两段的剩余堆数能拼成整段的剩余堆数；随意切分会得到根本不存在的合并方案。

「最后一次操作的代价与前面的顺序无关」是把指数搜索降到多项式的关键观察。凡是代价只依赖区间本身、不依赖内部合并历史的题目，都值得往区间动态规划上想。

面试视角：面试官会先问「什么情况下返回 $-1$」。能从「一次操作减少 $k - 1$ 堆」推出模不变量，而不是背结论，是这题最容易拉开差距的一问。

面试视角：另一个高频追问是「为什么 mid 要跳着走」。要能当场举出反例说明步长为 $1$ 会把不合法的切分当成候选并低估代价，光说「模板就这么写」是拿不到分的。

易错点总结

错误写法：省略 $(n - 1) \bmod (k - 1) \ne 0$ 的可行性判断 → 以 stones = [3, 2, 4, 1]、k = 3 为例，整段长度 $4$ 无法收口，dp[0][3] 停留在切分代价上，返回一个正数而不是题目要求的 $-1$。

错误写法：切分点步长写成 $1$ → 左右两段各自的剩余堆数之和可能超过 k，这种切分对应不了任何真实操作，却被当成候选参与取最小值。以 stones = [3, 5, 1, 2, 6]、k = 3 为例会算出 $17$，而正确答案是 $25$。

错误写法：无条件地给每个区间加上区间和 → 压不成一堆的区间凭空多付了一次合并代价。同样以 [3, 5, 1, 2, 6]、k = 3 为例，dp[0][3] 变成 $19$、dp[1][4] 变成 $22$，最终返回 $26$ 而不是 $25$。

错误写法：进入区间时不把 dp[left][right] 重置为哨兵值 → 数组默认值 $0$ 会直接成为切分代价的最小值，所有切分转移形同虚设。以 [3, 5, 1, 2, 6]、k = 3 为例返回 $0 + 17 = 17$，同样低估。

错误写法：把长度小于 k 的区间初始化为哨兵大值 → 这些区间的真实代价是 $0$（一次操作都做不了），置为大值后它们参与的每一次转移都被污染，dp[0][n - 1] 最终停留在哨兵量级。

错误写法：哨兵取 Integer.MAX_VALUE → 转移里两个子区间的值相加立刻溢出为负数，最小值被负数抢走，结果变成一个荒谬的负代价。

错误写法：外层循环按左端点而不是按区间长度递增 → 计算 dp[left][right] 时它依赖的 dp[mid + 1][right] 还是初始值，转移读到的是垃圾数据，结果不可预期。

错误写法：可行性判据写成 $(n - 1) \bmod k = 0$ 或 $n \bmod (k - 1) = 0$ → 以 [3, 2, 4, 1]、k = 2 为例，真实判据 $(4 - 1) \bmod 1 = 0$ 可行，但前一种写法算出 $3 \bmod 2 = 1$ 而误返回 $-1$。

错误写法：认为可以合并任意 k 堆而不要求相邻 → 那样问题会退化成每次取最小的 k 堆的贪心，与本题完全不同；题目明确要求这 k 堆连续，区间结构正是动态规划成立的前提。

相似题目

题目	难度	考察点
312. 戳气球	困难	按「最后一个被戳破的气球」划分区间，需要给两端补虚拟节点
516. 最长回文子序列	中等	转移只看区间两端字符是否相等，是区间动态规划里最简的形态
486. 预测赢家	中等	引入博弈双方，状态存的是先手净收益差而非绝对代价
877. 石子游戏	中等	与预测赢家同构，但堆数为偶且总数为奇，存在跳过动态规划的奇偶结论
1690. 石子游戏 VII	中等	每步得分是剩余区间和，需把前缀和与博弈取最大值结合
887. 鸡蛋掉落	困难	同样枚举分割点，但目标是最坏情况下的最少次数，可用决策单调性优化
面试题 08.14. 布尔运算	中等	按运算符切分表达式，状态要同时记录结果为真和为假的方案数