【LeetCode】合并石头的最低成本 [H]（动态规划）

1000. 合并石头的最低成本 - 力扣（LeetCode）

一、题目

有 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

二、代码

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份，这样才能让整个递归过程结束返回。