一、题目
有 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 <= 302 <= K <= 301 <= stones[i] <= 100
二、代码
class Solution {
public int mergeStones(int[] stones, int k) {
// 过滤无效参数
if (stones == null || stones.length == 0 || k == 0) {
return -1;
}
// 数组长度
int n = stones.length;
// 这个条件很重要，存在一些数组长度n和k的组合压根就合并不成1个，直接返回-1
if ((n - 1) % (k - 1) > 0) {
return -1;
}
// 构造前缀和数组，加速求任意区间累加和的速度
int[] preSum = new int[n];
preSum[0] = stones[0];
for (int i = 1; i < n; i++) {
preSum[i] = preSum[i - 1] + stones[i];
}
// 构造三维dp缓存 第三维下标在递归中最多赋值就是k，所以长度开到k+1即可
int[][][] dp = new int[n][n][k + 1];
// 将数组0~n-1范围合并成1份，每一次将相邻的k个合并
return process(stones, 0, n - 1, 1, k, preSum, dp);
}
// arr[l..r] 一定要弄出p份，返回最低代价
// 固定参数是k和preSum，preSum是用来加快求累加和速度的
public int process(int[] stones, int l, int r, int p, int k, int[] preSum, int[][][] dp) {
// 先看是否有缓存，有的话直接返回
if (dp[l][r][p] != 0) {
return dp[l][r][p];
}
// basecase 如果此时l==r，说明本身就是1个数了，如果要划分的目标p也是1，那么就不需要再合并了，代价直接返回0，如果目标p不是1，但是因为此时l~r范围只有一个数了，肯定是合并不出来p目标了，直接返回-1
if (l == r) {
dp[l][r][p] = p == 1 ? 0 : -1;
return dp[l][r][p];
}
// 说明当前就是最后一次合并了，合并完就要求是1个，如果无法一次合并成1个，就返回-1
if (p == 1) {
// 当前是最后一次合并了，如果要想是最后一次合并，此时合并完只能由k个数，所以要判断当前的状况能不能合并出k份
int next = process(stones, l, r, k, k, preSum, dp);
// 如果不能合并成k份，那么一定就无法最后合并成一份，直接返回-1
if (next == -1) {
dp[l][r][p] = -1;
return dp[l][r][p];
// 可以合并出三份
} else {
// 代价就是合并出三分所需要的总代价，加上l~r范围的累加和，因为将3份数合并，合并代价就是这三部分的累加和
dp[l][r][p] = next + (l == 0 ? preSum[r] : preSum[r] - preSum[l - 1]);
return dp[l][r][p];
}
// 当前目标并不是分成1份，说明合并还没有到最后
} else {
// 先将最小代价初始化为系统最大
int min = Integer.MAX_VALUE;
// 开始遍历，尝试所有可能的左右部分划分情况，我们就规定左部分划分出1份，右部分划分出p-1份
// 划分遍历步长就是k - 1，l最多到r - (p - 1)，因为要保证右部分至少有p-1个数，不然就不可能划分出p-1个目标了
for (int mid = l; mid <= r - (p - 1); mid += (k - 1)) {
// 看左部分合并成1份最低代价
int leftCost = process(stones, l, mid, 1, k, preSum, dp);
int rightCost = -1;
// 如果左部分确实可以划分出1份，就去看右部分能不能划分出p-1份。剪枝
if (leftCost != -1) {
// 右部分合并出p-1份的最低代价
rightCost = process(stones, mid + 1, r, p - 1, k, preSum, dp);
}
// 如果右部分也可以划分出来，则计算这两部分的合并代价，是否是l~r范围所有划分情况中最低的
if (rightCost != -1) {
// 这里我们就是要将l~r范围合并出p份，并不会对这p份再做合并，所以这里的代价就是leftCost+rightCost，不需要加上l~r的累加和
min = Math.min(min, leftCost + rightCost);
}
}
// 返回所有划分中合并代价最小的值
dp[l][r][p] = min;
return dp[l][r][p];
}
}
}
三、解题思路
定义process函数：让L...R一定变为P份，返回合并成P份的最少代价是啥。
枚举最左边的一份是什么范围，这样就可以递归出左部分和右部分的最低代价。我们将每一层递归的所有可能的范围都枚举尝试一遍，最后就能求出来结果。
这里我们就认为左边搞成1份，右边搞成P-1份，因为总归是存在一种划分能让左边搞出来1份，我们把所有可能的左部分范围都尝试一遍，就能得到全部左部分和右部分的情况。而且必须要来一个左右部分，因为只有划分为1份的时候才是递归出口，所以我们就要想到让左边固定搞1份，这样才能让整个递归过程结束返回。
