区间dp-蒲公英云

区间dp

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

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

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

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

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)
输出
输出最小合并代价

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
#define inf 0x3f3f3f
int dp[1010][1010];
int main()
{ 
    int n;
    while(cin>>n)
    { 
        int x;
        int a[1010];
        memset(dp,inf,sizeof(dp));//dp初始化为一个很大的值 
        a[0]=0;
        for(int i=1;i<=n;i++)
        { 
            scanf("%d",&x);
            a[i]=a[i-1]+x;
            dp[i][i]=0;//i到i区间值为0 
        }
        int i,j,k,endl;
        for(int i=1;i<=n;i++)//枚举长度 
        { 
            for(j=1;j<=n-i+1;j++)//枚举起点 
            { 
                endl=j+i-1;
                for(k=j;k<endl;k++)
                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] ,然后裂开了 
            } 
        }
        printf("%d\n",dp[1][n]); 
    }
}

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

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
#define inf 0x3f3f3f
int dp[1010][1010];
int main()
{ 
    int n,len;
    while(cin>>len>>n&&len)
    { 
        int x;
        int a[1010];
        //memset(dp,inf,sizeof(dp));//dp初始化为一个很大的值 
        a[0]=0;
        for(int i=1;i<=n;i++)
        { 
            scanf("%d",&a[i]);
            dp[i][i]=0;//i到i区间值为0 
        }
        n+=1;
        a[n]=len;
        int i,j,k,endl;
        for(int i=2;i<=n;i++)//枚举长度 
        { 
            for(j=0;j<=n-i;j++)//枚举起点 
            { 
                endl=j+i;
                dp[j][endl]=0x3f3f3f3f;
                for(k=j;k<=endl;k++)
                dp[j][endl]=min(dp[j][endl],dp[j][k]+dp[k][endl]+a[endl]-a[j]); 
            } 
        }
        printf("The minimum cutting is %d.\n",dp[0][n]); 
    }
}