合并石头的最低成本

难度: Hard

有 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

Submission

运行时间: 32 ms

内存: 16.8 MB

class Solution:
    def mergeStones(self, nums: List[int], k: int) -> int:
        n = len(nums)
        # f[i][j] 表示把区间[i,j]合成为一堆的最小成本。
        # 可以成功合并的前提是 (n / x * (k - 1)) // k == 1
        # 整理一下就是 (n - k) % (k - 1) == 0
        f = [[inf] * (n + 1) for _ in range(n + 1)]
        for i in range(n): f[i][i] = 0
        if (n - k) % (k - 1) != 0:
            return -1
        s = list(accumulate(nums, initial=0))
        for l in range(2, n + 1):
            for i in range(n - l + 1):
                j = i + l - 1
                for u in range(i, j + 1, k - 1):
                    f[i][j] = min(f[i][j], f[i][u] + f[u + 1][j])
                if (l - k) % (k - 1) == 0:
                    f[i][j] += s[j + 1] - s[i]
        return f[0][n - 1]

Explain

本题解采用动态规划方法解决合并石头的问题。动态规划数组 f[i][j] 用于存储从 i 到 j 合并成一堆的最小成本。首先检查 (n - k) % (k - 1) 是否为 0，如果不为 0 则返回 -1，因为这意味着不能通过 k 堆合并的方式最终合并成一堆。定义一个前缀和数组 s 以便快速计算任意区间的石头总数。核心的动态规划过程是考虑所有可能的分割方法，即对于每个区间 [i, j]，考虑所有可能的中间点 u，通过这些中间点将问题拆解为两个子问题。当区间长度 l 符合可以整体合并的条件时，累加整个区间的石头总量到成本中。

时间复杂度: O(n^3)

空间复杂度: O(n^2)

class Solution:
    def mergeStones(self, nums: List[int], k: int) -> int:
        n = len(nums)
        if (n - k) % (k - 1) != 0:
            return -1 # 如果不能合并成一堆，直接返回-1
        f = [[float('inf')] * (n + 1) for _ in range(n + 1)] # 初始化动态规划表
        for i in range(n):
            f[i][i] = 0 # 单独一堆的合并成本为0
        s = list(accumulate(nums, initial=0)) # 计算前缀和，方便快速区间求和
        for l in range(2, n + 1): # 从长度为2开始尝试所有长度
            for i in range(n - l + 1):
                j = i + l - 1
                for u in range(i, j + 1, k - 1):
                    f[i][j] = min(f[i][j], f[i][u] + f[u + 1][j]) # 尝试不同的中间点
                if (l - k) % (k - 1) == 0:
                    f[i][j] += s[j + 1] - s[i] # 如果长度符合合并要求，加上区间内的总石头数
        return f[0][n - 1] # 返回合并整个数组的最小成本

Explore

前缀和数组s的主要作用是快速计算任意子数组的和，以减少重复计算，提高效率。定义s[i]为从数组开始到索引i-1的元素的和。因此，任意区间[i, j]的石头总数可通过s[j+1] - s[i]快速得到。在动态规划中，当要考虑合并整个区间[i, j]时，需要知道这个区间内所有石头的总和来计算合并成本。使用前缀和数组，可以在O(1)时间内得到这个和，从而优化整个动态规划的计算过程。

在动态规划中设置步长为k-1是为了确保每次合并操作后，剩余的堆数仍然能够以k个一组继续合并。这是因为每次合并k个堆成1堆，减少的堆数是k-1。如果不按照k-1的步长分割，则可能导致无法将剩余的堆数继续按k个一组合并。这种分割方式是为了符合题目的合并要求，但并不一定是最优的，因为它主要是按照题目设定的规则来确保合并的可能性，而不是从成本最小化的角度出发。

当数组长度n等于k时，这是一个特殊情况，因为整个数组可以直接合并成一堆，不需要进一步的分割。在动态规划的初始化过程中，已经将长度为1的区间的合并成本设置为0。对于长度为n的区间，只需要计算一次合并成本，即整个区间的石头总和。因此，这种情况下的处理比较直接，只需在动态规划中考虑将整个区间合并的情况即可。

如果`(n-k) % (k-1) != 0`，意味着将数组中的n个元素减去一个初始的k个一组的合并后，剩余的元素无法再按照每次减少k-1的规则继续整合为更少的堆数。这是因为每次合并k个堆减少的堆数正好是k-1，如果n-k与k-1的余数不为0，那么在经过若干次合并后，会剩下无法再进行k堆合并的剩余堆数。因此在这种情况下，无法通过规定的合并方式最终合并成一堆，故直接返回-1表示无法完成合并任务。