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])

 //dp是从两两合并开始的，也就是说是长度先为2，然后3，....所以要枚举len的长度

        //dp[i][j],len=j-i

        for(int len=;len<n;len++)

        {

            for(int i=;i<=n-len;i++)

            {

                int j=i+len;

                for(int k=i;k<j;k++)

                {

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

                }

            }

        }

通过观察上面的例子，我们可以知道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])

for (len=;len<=n;++len){

        for (l=;l+len-<=n;++l)

        {

            r=l+len-;

            for (k=l;k<r;++k)

            {

                for (i=;i<=len;++i)

                {

                    f[l][r][i]=min(f[l][r][i],f[l][k][i-]+f[k+][r][]);

                }

            }

            f[l][r][]=min(f[l][r][K]+sum[r]-sum[l-],f[l][r][]);

        }

Leetcode1000 合并石头的最低成本 区间DP的相关教程结束。