区间DP问题

参考：https://www.bilibili.com/video/BV1Wf4y1R794?spm_id_from=333.337.search-card.all.click
区间DP：即在一个区间上求解dp元素值，比如dp[i][j]要在[i,j]区间上遍历一遍才能确定最优值；
问题：石子合并https://www.acwing.com/problem/content/284/
设有 N 堆石子排成一排，其编号为 1，2，3，…，N。
每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。求最小的总代价？
比如4堆石子重量是1，3，5，2；
动态规划一般用于求解最优解，且问题可分解，最终的结果可以由小问题的结果得到；考虑dp[left][right],表示从left到right的最小代价；
由于每次合并2堆，最后的一次合并也是2堆合并成一堆，因此可设置分割点划分整个集合为2堆，即
for(auto partition=left;partition<right;++partition)
{
dp[left][right]=min(dp[left][right],dp[left,partition]+dp[partition+1][right]+weight(left,right));
}
不使用递归时，要从小问题开始计算，初始时如果只有一堆，不用合并，代价是0，随着规模的不断增大，计算更大规模的代价，这里规模是集合的长度，当长度是1时，即right==left时，dp[left][right]=0;把长度len作为一个变量，把left作为一个变量，这样right=left+len-1;则外层的循环是
for(len=2;len<=n;++len)
{
for(left=0;left+len-1<n;++left)
{
right=left+len-1;
}
}
总的时间复杂度是O（N的3次方）；

最后

以上就是奋斗铃铛为你收集整理的区间DP问题的全部内容，希望文章能够帮你解决区间DP问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。