1000. 合并石头的最低成本

Difficulty
Hard
Tags
动态规划
URL
https://leetcode.cn/problems/minimum-cost-to-merge-stones/
Star
有 N 堆石头排成一排，第 i 堆中有 stones[i] 块石头。
每次移动（move）需要将连续的 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，这是可能的最小值。
提示：
  • 1 <= stones.length <= 30
  • 2 <= K <= 30
  • 1 <= stones[i] <= 100

法 1 动态规划 第一类区间 + 第二类区间

思路
notion imagenotion image
notion imagenotion image
dp[i][j][k] 表示 将 nums[i:j+1] 分为k 组需要的代价。
这就有第一类区间型DP的影子了，需要枚举第 k 堆的最后一个元素位置m，即将nums[i:j+1] 分为 nums[i:m+1] 和 nums[m+1:j]两部分，前一部分为新分出来的第 k 堆， 后一部分为 k-1 堆。图示如下：
notion imagenotion image
即 dp[i][j][k] = dp[i][m][1] + dp[m+1][j][k-1]
这个状态转移方程有一个问题需要理解：合并成 k 堆为什么是由 1 和 k-1 堆生成，不能是 2 和 k-2 堆生成？ 其实这两者一致，可以相互转换。合成 k 堆的最小花费可以由 2 和 k-2 堆生成，但是可以把 2 分为两半这样就可以表示成 1 和 k-1 堆生成。
需要注意的点：
  • 首先需要判断长度为 n 的nums能否 k 个 一堆的合并。要保证能 k 个 一堆的合并，必须要满足 (n-1) % (k-1) == 0，因为总共需要 (n-1) % (k-1) 次合并
      • 计算过程: n - x * k + x = 1 , x 为石子堆合并的总次数，合并 k 堆将产生 1 堆，合并 x 个 k 堆产生 x 堆, 而最后要合并成 1 堆。
      结果：x = (n - 1) / (k - 1) , x >= 0, 且为整数
  • dp[i][j][1] 只能由 dp[i][j][K] 转化得到，因为我们只能合并 K 堆，具体的 dp[i][j][1] = dp[i][j][K] + sum(nums[i:j+1]。最后合并为一堆的时候，是一定要把这一大堆的 代价都相加的，和之前K小堆怎么划分的 无关。
  • 初始化的时候，dp[i][i][1] = 0 因为此时不需要划分！
时间复杂度 为 ，空间复杂度为
题解
class Solution:
    def mergeStones(self, stones: List[int], k: int) -> int:
        K = k
        # 总共需要 合并 (n-1)//(K-1)次，所以需要为整数，否则，就不能合并了
        if (len(stones)-1) % (k-1) != 0:
            return -1
        #dp[i][j][k] 表示 stones[i:j+1]  分为 k 堆 需要的代价
        dp = [[[float("inf")]*(k+1) for _ in range(len(stones))] for _ in range(len(stones))]

        # dp[i][i][1] 是不用合并的，代价为 0
        for i in range(0, len(stones)):
            dp[i][i][1] = 0

        # i, j 枚举起点终点
        for i in range(len(stones)-1, -1, -1):
            for j in range(i+1, len(stones), 1):
                # 枚举分割长度
                for k in range(2, K+1):
                    # 枚举 第 k 堆的终点 
                    for m in range(i, j):
                        dp[i][j][k] = min(dp[i][j][k], 
                                        dp[i][m][1] + dp[m+1][j][k-1])
                # 这 一步是判断 nums[i:j+1] 能否分为 K 堆
                # 不加也可以，因为最终取的是min, 且最开始已经保证了能分 K 堆
                if dp[i][j][K] < float("inf"):
                    dp[i][j][1] = dp[i][j][K] + sum(stones[i:j+1])

        return dp[0][-1][1]
优化：
  • 可以通过前缀和来计算 sum(stones[i:j+1])
  • 观察最里面的两层循环：遍历 分组长度 k 和 分割点 m ,其实有很多不能分的。
      • 在将 分为 组的时候， 通过枚举分割点 ， 将nums[i:j+1]分为nums[i:m+1] 和 nums[m+1:j] 两部分，前一部分 组，后一部分是 组。要求前一部分能分成 1 组，其实是需要很强的条件的：(m+1-i-1)%(k-1) == 0 . 但是很多不一定满足。所以m 可以 跳 k-1 走。