石子合并的升级版，简单版题解-> AcWing 282. 石子合并

题目描述

有 N 堆石头排成一排，第 i 堆中有stones[i]块石头。
每次移动（move）需要将连续K堆石头合并为一堆，而这个移动的成本为这K堆石头的总数。
找出把所有石头合并成一堆的最低成本。如果不可能，返回 -1 。

提示：
1 <= stones.length <= 30
2 <= K <= 30
1 <= stones[i] <= 100

样例

示例 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，这是可能的最小值。

算法

(动态规划) $O(n^3 * K)$

集合 f(i,j,k)

• 表示
  • 定义 ：把区间为 i 到 j的石子合并成k堆的所有方案的集合
  • 属性 ： 这些方案中的代价最小值 所求答案为f(1, n, K)

• 计算

  • 最后一步 : 把k-1堆 和 最后1堆合并成k堆 然后把k堆合并成1堆

    • 首先 ：合并成k堆
      • 枚举分界点p，把区间[i,j]分为[i, p] 和 [ p+1, j]左右两端，把左边合并成k-1堆，右边合并成1堆即可
      • 从2到K枚举合并的堆数k ，f(i,j,k) = min (f(i,p,k-1)+(p+1,j,1))
    • 其次 ：再把k堆合并成1堆
      • f(i,j,1) = min(f(i,j,1)，f(i,j,K) + sum(i,j))

  • 最终所求为 f(1, n, K)

时间复杂度

• 时间复杂度：$o(n ^ 3 * K)$
  - 枚举长度 起点 区间分割点 都要 $o(n)$ 枚举堆数 $0(K)$
• 空间复杂度：$o(n ^ 2 * K + n)$
  - dp三维数组 以及 前缀和数组

C++ 代码

class Solution {
public:
    int dp[31][31][31]; //dp[i][j][k] 把 i 到 j 合并成k堆的最小代价  初始化为无穷大
    int sum[31];  //前缀和数组 便于求代价
    int mergeStones(vector<int>& stones, int K) 
    {
        // 特判
        int n = stones.size();
        if ((n - 1) % (K - 1)) return -1;
        if(n < 2) return 0 ;

        // dp初始化 求前缀和
        memset(dp, 0x3f, sizeof(dp));
        for(int i = 1; i <= n; i ++)
        {
            sum[i] = sum[i - 1] + stones[i - 1];
            dp[i][i][1] = 0;  // 代价为0
        }

        // 枚举区间 惯用手法: 枚举区间长度 + 区间起点
        for (int len = 2; len <= n; len++)           
        {
            for (int i = 1; i + len - 1 <= n ; i++)  
            {
                int j = i + len - 1;                 

                for (int k = 2; k <= K; k++)      // 枚举连续堆数
                { 
                    for (int p = i; p < j; p ++ )   // 枚举分界点
                    {
                        dp[i][j][k] = min(dp[i][j][k], dp[i][p][k - 1] + dp[p + 1][j][1]);
                    }
                }
                dp[i][j][1] = min(dp[i][j][1], dp[i][j][K] + sum[j] - sum[i - 1]);
            }
        }
        return dp[1][n][1]; //把1到n堆合并成1堆的最小代价
    }
};

参考文献

https://zxi.mytechroad.com/blog/dynamic-programming/leetcode-1000-minimum-cost-to-merge-stones/