Leetcode1000 合并石头的最低成本 区间DP
2024-10-16 04:50:35
有 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][]); }
最新文章
- 【231】◀▶ 利用 IDL 读取 TIFF 数据
- PHP 将json的stdClass Object转成数组array
- AVR JTAG MKii 引脚布局 ( JTAG 和 ISP )
- Ajax提交打开新窗口,浏览器拦截处理
- 百度云推送 pem
- gitHub远程分支创建
- [RxJS] Reactive Programming - What is RxJS?
- Eclipse 中,web项目在Tomcat运行时填写不了Server name
- Itext简绍及操作PDF文件
- Java Breakpoint
- Linux下检测内存泄露的工具 valgrind
- docker 一键安装zabbix server、zabbix agent
- Java线程池详解,看这篇就够了!
- 学习笔记之C / C++
- zoj3820
- 一句话shell
- pandas的set_index和reset_index方法
- go语言入门(三)
- scrapy添加 请求头
- python 获取某个月的全部日期