leetcode1000. 合并石头的最低成本

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

每次移动（move）需要将连续的 K 堆石头合并为一堆，而这个移动的成本为这 K 堆石头的总数。

找出把所有石头合并成一堆的最低成本。如果不可能，返回 -1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-cost-to-merge-stones

解决

经典的石子归并的题目，不过是三维的dp，想清楚是比较复杂的。记录一下。
dp状态和递推方程不难想到，但是怎么遍历想了很久，毕竟3维。子问题是解决小区间的合并，再大区间。

const INF = 1e8 + 7

var n int
var dp [][][]int

func Init(k int) {
	dp = make([][][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([][]int, n)
		for j := 0; j < n; j++ {
			dp[i][j] = make([]int, k+1)
			for p := 0; p < k+1; p++ {
				dp[i][j][p] = INF
			}
		}
	}
}

func mergeStones(stones []int, k int) int {
	n = len(stones)
	Init(k)

	pre := make([]int, n+1)
	for i := 0; i < n; i++ {
		pre[i+1] = pre[i] + stones[i]
		dp[i][i][1] = 0
	}

	for ll := 1; ll <= n; ll++ { // 确定该轮遍历的区间长度
		for l := 0; l < n && l+ll < n; l++ { // 确定左，右边界
			r := l + ll
			for p := 2; p <= k; p++ { // 区间分p堆
				for s := l; s < r; s++ {
					dp[l][r][p] = min(dp[l][r][p], dp[l][s][1]+dp[s+1][r][p-1]) // dp[l][r][p] = min{ dp[l][s][1] + dp[s+1][r][p-1] }
					// fmt.Println("cp2", l, r, s, p, dp[l][r][p])
				}
			}
			dp[l][r][1] = min(dp[l][r][1], dp[l][r][k]+pre[r+1]-pre[l]) // dp[l][r][1] = dp[l][r][k] + sum[l,r]
		}
	}

	if dp[0][n-1][1] == INF {
		return -1
	}
	return dp[0][n-1][1]
}

func min(j, k int) int {
	if j < k {
		return j
	}
	return k
}

func main() {
	//stones := []int{1, 2, 3}
	//K := 2
	//fmt.Println(mergeStones(stones, K))

	stones := []int{3, 5, 1, 2, 6}
	K := 3
	fmt.Println(mergeStones(stones, K))

	stones = []int{1}
	K = 2
	fmt.Println(mergeStones(stones, K))

	stones = []int{5, 4}
	K = 3
	fmt.Println(mergeStones(stones, K))
}