What is the main pattern used to solve the Minimum Cost to Merge Stones problem?

The main pattern is state transition dynamic programming, where we track the minimum cost of merging stones using recursive relations and optimized calculations.

How can dynamic programming optimize the solution for merging stones?

Dynamic programming allows us to reuse previously computed solutions, which reduces redundant calculations and helps achieve an optimal merge sequence.

What is the importance of prefix sums in this problem?

Prefix sums help optimize the cost calculation by providing a fast way to compute the sum of any subarray of stones, avoiding repetitive calculations.

How do we handle cases where it is impossible to merge stones?

In such cases, the solution should immediately return -1. We detect these situations through checks in the DP approach or via basic logic, such as when there are not enough piles to merge with the given k.

Can the problem be solved efficiently for larger values of n?

Yes, with dynamic programming and prefix sum optimizations, the problem can be solved efficiently even for the maximum constraint (n = 30).

#1000

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

合并石头的最低成本

有 n 堆石头排成一排，第 i 堆中有 stones[i] 块石头。每次移动需要将连续的 k 堆石头合并为一堆，而这次移动的成本为这 k 堆中石头的总数。返回把所有石头合并成一堆的最低成本。如果无法合并成一堆，返回 -1 。示例 1：输入： stones = [3,2,4,1], K …

数组动态规划前缀和

题目描述

有 n 堆石头排成一排，第 i 堆中有 stones[i] 块石头。

每次移动需要将 连续的 k 堆石头合并为一堆，而这次移动的成本为这 k 堆中石头的总数。

返回把所有石头合并成一堆的最低成本。如果无法合并成一堆，返回 -1 。

示例 1：

输入：stones = [3,2,4,1], K = 2
输出：20
解释：
从 [3, 2, 4, 1] 开始。
合并 [3, 2]，成本为 5，剩下 [5, 4, 1]。
合并 [4, 1]，成本为 5，剩下 [5, 5]。
合并 [5, 5]，成本为 10，剩下 [10]。
总成本 20，这是可能的最小值。

示例 2：

输入：stones = [3,2,4,1], K = 3
输出：-1
解释：任何合并操作后，都会剩下 2 堆，我们无法再进行合并。所以这项任务是不可能完成的。.

示例 3：

输入：stones = [3,5,1,2,6], K = 3
输出：25
解释：
从 [3, 5, 1, 2, 6] 开始。
合并 [5, 1, 2]，成本为 8，剩下 [3, 8, 6]。
合并 [3, 8, 6]，成本为 17，剩下 [17]。
总成本 25，这是可能的最小值。

提示：

n == stones.length
1 <= n <= 30
1 <= stones[i] <= 100
2 <= k <= 30

lightbulb

解题思路

方法一：动态规划（区间 DP）+ 前缀和

我们不妨记题目中的 $k$ 为 $K$ ，石头的堆数为 $n$ 。

定义 $f[i][j][k]$ 表示将区间 $[i, j]$ 中的石头合并成 $k$ 堆的最小成本。初始时 $f[i][i][1] = 0$ ，其他位置的值均为 $\infty$ 。

注意到 $k$ 的取值范围为 $[1, K]$ ，因此我们需要枚举 $k$ 的值。

对于 $f[i][j][k]$ ，我们可以枚举 $i \leq h \lt j$ ，将区间 $[i, j]$ 拆分成两个区间 $[i, h]$ 和 $[h + 1, j]$ ，然后将 $[i, h]$ 中的石头合并成 $1$ 堆，将 $[h + 1, j]$ 中的石头合并成 $k - 1$ 堆，最后将这两堆石头合并成一堆，这样就可以将区间 $[i, j]$ 中的石头合并成 $k$ 堆。因此，我们可以得到状态转移方程：

f[i][j][k] = \min_{i \leq h < j} \{f[i][h][1] + f[h + 1][j][k - 1]\}

我们将区间 $[i, j]$ 的 $K$ 堆石头合并成一堆，因此 $f[i][j][1] = f[i][j][K] + \sum_{t = i}^j stones[t]$ ，其中 $\sum_{t = i}^j stones[t]$ 表示区间 $[i, j]$ 中石头的总数。

最后答案即为 $f[1][n][1]$ ，其中 $n$ 为石头的堆数。

时间复杂度 $O(n^3 \times k)$ ，空间复杂度 $O(n^2 \times k)$ 。其中 $n$ 为石头的堆数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def mergeStones(self, stones: List[int], K: int) -> int:
        n = len(stones)
        if (n - 1) % (K - 1):
            return -1
        s = list(accumulate(stones, initial=0))
        f = [[[inf] * (K + 1) for _ in range(n + 1)] for _ in range(n + 1)]
        for i in range(1, n + 1):
            f[i][i][1] = 0
        for l in range(2, n + 1):
            for i in range(1, n - l + 2):
                j = i + l - 1
                for k in range(1, K + 1):
                    for h in range(i, j):
                        f[i][j][k] = min(f[i][j][k], f[i][h][1] + f[h + 1][j][k - 1])
                f[i][j][1] = f[i][j][K] + s[j] - s[i - 1]
        return f[1][n][1]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for understanding of dynamic programming and optimization techniques like prefix sums.
question_mark
Evaluate the candidate's ability to handle edge cases where merging is impossible.
question_mark
Assess the candidate’s familiarity with state transitions and how it applies to minimizing cost.

warning

常见陷阱

外企场景

error
Failing to handle the case where merging isn't possible, leading to incorrect answers.
error
Not optimizing the prefix sum calculations, leading to excessive time complexity.
error
Overcomplicating the DP state transitions or missing a straightforward recursive relation.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allowing a different number of consecutive piles (e.g., changing k).
arrow_right_alt
Solving the problem under stricter time constraints for larger inputs.
arrow_right_alt
Extending the problem to handle multiple groups of k piles simultaneously.

help

常见问题

外企场景

继续练习

#1140 石子游戏 II #813 最大平均值和的分组 #689 三个无重叠子数组的最大和