区间dp

Bertha 。 2023-07-10 08:18 146阅读 0赞

概念
区间dp就是在区间上进行动态规划,求解一段区间上的最优解。主要是通过合并小区间的 最优解进而得出整个大区间上最优解的dp算法。
借鉴大佬总结:猛戳

过程
区间dp的过程其实就是三步(就是三个for循环)
区间长度==>起始点==>分割点
从求小区间的最优解,再合并小区间到大区间。

状态转移方程
dp[i][j]表示从i到j区间的最优解,所以一般情况下要得到的结果就是dp[1][n] (感觉我个人最费解的就是这个部分,所以就直接点描述dp数组)。按照区间长度,起始点以及分割点的思路可以得到状态转移方程

  1. dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+价值数组)

题目

石子归并
N堆石子摆成一条线。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的代价。计算将N堆石子合并成一堆的最小代价。
例如: 1 2 3 4,有不少合并方法
1 2 3 4 => 3 3 4(3) => 6 4(9) => 10(19)
1 2 3 4 => 1 5 4(5) => 1 9(14) => 10(24)
1 2 3 4 => 1 2 7(7) => 3 7(10) => 10(20)
括号里面为总代价可以看出,第一种方法的代价最低,现在给出n堆石子的数量,计算最小合并代价。
输入
第1行:N(2 <= N <= 100) 第2 - N + 1:N堆石子的数量(1 <= Ai <= 10000)
输出
输出最小合并代价

  1. #include<cstdio>
  2. #include<iostream>
  3. #include<cstring>
  4. using namespace std;
  5. #define inf 0x3f3f3f
  6. int dp[1010][1010];
  7. int main()
  8. {
  9. int n;
  10. while(cin>>n)
  11. {
  12. int x;
  13. int a[1010];
  14. memset(dp,inf,sizeof(dp));//dp初始化为一个很大的值
  15. a[0]=0;
  16. for(int i=1;i<=n;i++)
  17. {
  18. scanf("%d",&x);
  19. a[i]=a[i-1]+x;
  20. dp[i][i]=0;//i到i区间值为0
  21. }
  22. int i,j,k,endl;
  23. for(int i=1;i<=n;i++)//枚举长度
  24. {
  25. for(j=1;j<=n-i+1;j++)//枚举起点
  26. {
  27. endl=j+i-1;
  28. for(k=j;k<endl;k++)
  29. dp[j][endl]=min(dp[j][endl],dp[j][k]+dp[k+1][endl]+a[endl]-a[j-1]);//这里的a[endl]-a[j-1]要注意,因为是求j~endl的和 ,我一开始就写的a[j] ,然后裂开了
  30. }
  31. }
  32. printf("%d\n",dp[1][n]);
  33. }
  34. }

**Cutting Sticks **
(题目全是英语的就不做搬运工了)
题意:一个len(木块长度),一个n(木块上可以切割的地方),然后n个数字,表示切割点。每次切割的代价是待切割木块的总长度。
问:最小代价
做完石子合并后做这个差点裂开了,学完区间dp,按照daolao的指导先ac了石子合并,但这个题目感觉和石子合并就反着来,特别是求价值数组的时候。

  1. #include<cstdio>
  2. #include<iostream>
  3. #include<cstring>
  4. using namespace std;
  5. #define inf 0x3f3f3f
  6. int dp[1010][1010];
  7. int main()
  8. {
  9. int n,len;
  10. while(cin>>len>>n&&len)
  11. {
  12. int x;
  13. int a[1010];
  14. //memset(dp,inf,sizeof(dp));//dp初始化为一个很大的值
  15. a[0]=0;
  16. for(int i=1;i<=n;i++)
  17. {
  18. scanf("%d",&a[i]);
  19. dp[i][i]=0;//i到i区间值为0
  20. }
  21. n+=1;
  22. a[n]=len;
  23. int i,j,k,endl;
  24. for(int i=2;i<=n;i++)//枚举长度
  25. {
  26. for(j=0;j<=n-i;j++)//枚举起点
  27. {
  28. endl=j+i;
  29. dp[j][endl]=0x3f3f3f3f;
  30. for(k=j;k<=endl;k++)
  31. dp[j][endl]=min(dp[j][endl],dp[j][k]+dp[k][endl]+a[endl]-a[j]);
  32. }
  33. }
  34. printf("The minimum cutting is %d.\n",dp[0][n]);
  35. }
  36. }

发表评论

表情:
评论列表 (有 0 条评论,146人围观)

还没有评论,来说两句吧...

相关阅读

    相关 区间dp

    概念 区间dp就是在区间上进行动态规划,求解一段区间上的最优解。主要是通过合并小区间的 最优解进而得出整个大区间上最优解的dp算法。 借鉴大佬总结:[猛戳][Link

    相关 区间dp问题

    区间dp一般有以下几种类型的题目: 如何将环形区间问题转换为线性dp问题 如何记录方案数目 区间dp与高精度的结合 高维区间dp问题 一般区间dp有

    相关 整数划分 区间dp

    题目链接[点击打开链接][Link 1] 题目大意是说有一个不超过二十位的数字,要将这个数字划分成n段,最后让这n段数字相乘,问怎么划分使乘积最大。 分析: 一

    相关 『金字塔 区间dp

    -------------------- 金字塔 Description 虽然探索金字塔是极其老套的剧情,但是这一队 探险家还是到了某金字塔脚下。经过多年的研究,

    相关 区间dp

    让我求解在一个区间上的最优解,那么我把这个区间分割成一个个小区间,求解每个小区间的最优解,再合并小区间得到大区间即可。所以在代码实现上,我可以枚举区间长度len为每次分割成的小