合并石头的最低成本

题目描述：

有 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

思路:

时间复杂度：O(n^2),空间复杂度O(n^2)

区间dp经典题

代码:

func mergeStones(stones []int, k int) int {
	n := len(stones)
	if (n-1)%(k-1) != 0 {
		return -1
	}
	dp := make([][]int, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = make([]int, n+1)
	}
	sum := make([]int, n+1)
	for i := 1; i <= n; i++ {
		sum[i] = sum[i-1] + stones[i-1]
	}
	for l := k; l <= n;l++ { // 枚举区间长度
		for i := 1;i+l-1 <= n;i++ { // 枚举区间起点
			j := i + l - 1
			dp[i][j] = math.MaxInt32
			for p := i; p < j;p += k - 1 { // 枚举分界点
				if dp[i][j]> dp[i][p]+dp[p+1][j]{
					dp[i][j] = dp[i][p]+dp[p+1][j]
				}
			}
			if (j-i)%(k-1) == 0 {
				dp[i][j] += sum[j] - sum[i-1]
			}
		}
	}
	return dp[1][n]
}

代码效率：

执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：2.2 MB, 在所有 Go 提交中击败了71.43%的用户