1000. 合并石头的最低成本
有 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解答：区间DP
class Solution {
private int[][][] memo;
private int[] s;
private int k;
public int mergeStones(int[] stones, int k) {
int n = stones.length;
if ((n - 1) % (k - 1) > 0) // 无法合并成一堆
return -1;
s = new int[n + 1];
for (int i = 0; i < n; i++)
s[i + 1] = s[i] + stones[i]; // 前缀和
this.k = k;
memo = new int[n][n][k + 1];
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
Arrays.fill(memo[i][j], -1); // -1 表示还没有计算过
return dfs(0, n - 1, 1);
}
private int dfs(int i, int j, int p) {
if (memo[i][j][p] != -1) return memo[i][j][p];
if (p == 1) // 合并成一堆
return memo[i][j][p] = i == j ? 0 : dfs(i, j, k) + s[j + 1] - s[i];
int res = Integer.MAX_VALUE;
for (int m = i; m < j; m += k - 1) // 枚举哪些石头堆合并成第一堆
res = Math.min(res, dfs(i, m, 1) + dfs(m + 1, j, p - 1));
return memo[i][j][p] = res;
}
}
