Leetcode1000 合并石头的最低成本 区间DP

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

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

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

找出把所有石头合并成一堆的最低成本。如果不可能，返回 -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，这是可能的最小值。

输入：stones = [3,2,4,1], K = 3
输出：-1
解释：任何合并操作后，都会剩下 2 堆，我们无法再进行合并。所以这项任务是不可能完成的。.

输入：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

当K=2时，每次合并都是相邻的两堆进行合并。用dp[i][j]表示从i到j这个区间合并为1个堆时的最小代价。那么有转移方程：

dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1])

通过观察上面的例子，我们可以知道K=2时，我们做的其实是将一部分合并为1堆，另一部分合并为1堆，最后形成一堆。典型的子问题划分问题，可以想象归并排序的过程。

现在K!=2了，那么我们就将一部分合并成K-1堆，另一部分合并成1堆，然后合并。

至于为什么不是K-2堆和2堆以及K-3堆和3堆是因为我们的子问题是合并成1堆，当前状态是由前一状态得到的。而我们最初只有dp[i][i][1]=0这个条件

现在K可以为任意值，由样例我们可以得到如果(n-1)%(k-1)不等于0的话，说明最终无法形成一堆。

现在考虑正常的情况，我们用dp[i][j][m]表示从i到j这个区间形成m堆所需的最小代价

初始化 dp[i][i][1]=0

dp[i][j][K]=min(dp[i][j][k],dp[i][k][K-1]+dp[k+1][j][1])

dp[i][j][1]=min(dp[i][j][K]+sum[j]-sum[k-1])