题目描述

有 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

(动态规划) $O(N^3*K)$

用dp[i][j][k]表示把从第i个石子到第j个石子合并为k堆需要最少花费，则题目最终所要求得的结果为dp[1][n][1]。先枚举区间长度，再枚举区间起始点，然后枚举合并堆数，再枚举最后一个分割点。状态转移方程为dp[i][j][k] = min(dp[i][j][k], dp[i][t][k - 1] + dp[t + 1][j][1])。设pre[i]表示前i堆石子的总和，则将从i到j的K堆石子合并的总花费为dp[i][j][1] = min(dp[i][j][1], dp[i][j][K] + pre[j] - pre[i - 1])。

时间复杂度分析：枚举区间长度、起始点和分割点的复杂度都为N，枚举合并堆数复杂度为K，所以总时间复杂度为$O(N^3*K)$

Python3代码

class Solution(object):
    def mergeStones(self, stones, K):
        """
        :type stones: List[int]
        :type K: int
        :rtype: int
        """
        n = len(stones)
        if (n - 1) % (K - 1) != 0:
            return -1
        pre = [0 for _ in range(n + 1)]
        for i in range(1, n + 1):
            pre[i] = pre[i - 1] + stones[i - 1]
        m = pre[n] * (n - 1) // (K - 1)
        dp = [[[m for _ in range(K + 1)] for _ in range(n + 1)] for _ in range(n + 1)]
        for i in range(1, n + 1):
            dp[i][i][1] = 0
        for l in range(1, n + 1):
            for i in range(1, n - l + 2):
                j = i + l - 1
                for k in range(2, min(K + 1, l + 1)):
                    for t in range(i, j):
                        dp[i][j][k] = min(dp[i][j][k], dp[i][t][k - 1] + dp[t + 1][j][1])
                dp[i][j][1] = min(dp[i][j][1], dp[i][j][K] + pre[j] - pre[i - 1])
        return dp[1][n][1]