这可爱的动态规划,短小精悍,太迷人了hhh。

y氏分析法

看了B站yxs的DP视频收获很大!!!

y氏分析法

  1. 根据集合的思想来考虑
  2. 思考元素类型,定义域和集合表示的属性
  3. 集合划分就是考虑集合可以怎样细分,包含那些元素
  4. sum属性必须保证不重不漏(图中写错了),最值只需要考虑不漏。
  5. 一般的DP问题只需要关注最后的状态或者说操作。(前提是你能看出这是DP问题并证明

背包问题

优化到一维的的重点当我们需要从上一层那就从大到小,如果是本层就从小到达。从大到小枚举体积就保证所用到的体积不会被用到过。

灵异背包

/*
二维写法
集合划分:前i个物品,选择i和不选择i的情况。
*/
For(i,1,n)
For(j,1,m){
    f[i][j]=f[i-1][j];
    if(j>=v[i])f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i])
}
/*
一维写法
因为二维中i这一维没有决定我们的集合范围
但是我们要保证在计算时保证i-1不能变成i
因为j-v[i]是严格小于j的,然后j是从小到大枚举的,所以计算j-v[i]时,已经被更新过了。
如果从大到小枚举,在计算j-v[i]时候,j-v[i]还没有被更新过。
*/
For(i,1,n)
for(int j = m;j>=v[i];j--){
    f[j]=max(f[j],f[j-v[i]]+w[i]);
}

完全背包

/*二维三循环*/
For(i,1,n)
For(j,1,m)
for(int k = 0;i*v[i]<=j;k++){
    f[i][j]=max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k);
}
/*二维二循环*/
For(i,1,n)
For(j,0,m){
    f[i][j]=f[i-1][j];//不选择
    if(j>=v[i])f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
}
/*一维*/
For(i,1,n)
for(int j = v[i];j<=m;j++){
    f[j]=max(f[j],f[j-v[i]]+w[i]);
}

多重背包问题

/*类似完全背包复杂版*/
For(i,1,n)
For(j,0,n)
for(int k = 0;k*v[i]<=j&&k<=s[i];k++)
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
/*二进制优化版本*/
int a,b,s;
while(n--){//二进制优化
    cin>>a>>b>>s;
    int k = 1;
    while(k<=s){
        v[++cnt]=k*a;
        w[cnt]=k*b;
        s-=k;
        k*=2;
    }
    if(s){
        v[++cnt]=s*a;
        w[cnt]=s*b;
    }
}
For(i,1,cnt)//01背包
for(int j = m;j>=v[i];j--)
f[j]=max(f[j],f[j-v[i]]+w[i]);

分组背包问题

For(i,1,n){
    cin>>s[i];
    for(int j = 0;j<s[i];j++)
    cin>>v[i][j]>>w[i][j];
}
For(i,1,n)//分组进行
for(int j = m;j>=0;j++)
For(k,1,s[i]){//枚举每个k
    if(v[i][k]<=j)
    f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
}

线性DP

线性DP就是我们的递推方程是有明显的线性关系的,就是有明显的顺序,可能有多个维度。
题目很杂,但是思路很好想,所以多做题只要能判断出这是个线性DP问题,然后就会很容易的做出来。

数字三角形

For(i,1,n){
    dp[i][0]=-INF;
    dp[0][1]=-INF;
    dp[i][i+1]=-INF;
For(i,1,n)
For(j,1,i){
    dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+dp[i][j];
}
int res = -INF;
For(i,1,n){
    res=dp[n][i]>res?dp[n][i]:res;
}
}

最长上升子序列-LIS

/*朴素版(完全够用了)*/
For(i,1,n){
    cin>>a[i];
    int res = 0;
    For(j,1,n-1){
        if(a[i]>a[j])res=max(res,f[j]);
    }
    f[i]=res+1;
}
int res=0;
For(i,1,n)res = max(res,f[i]);
cout<<res;
/*优化版*/
int res = 0;
For(i,1,n){
    cin>>a[i];
    int l = 0,r = res;
    while(l<r){
         int mid = l+r+1>>r;
         if(a[i]>q[mid])l=mid;
         else r = mid-1;
    }
    res = max(res,r+1);
    r+1=a[i];
}

最长公共子序列

/*只需要考虑同一个位置的状态*/
For(i,1,n)
For(j,1,m){
    f[i][j]=max(f[i-1][j],f[i][j-1]);
    if(a[i]==b[j])f[i][j]=max(f[i][j],f[i-1][j-1]);
}
int res = f[n][m];

最长编辑距离

For(i,1,n)f[i][0]=i;
For(i,1,m)f[0][i]=i;
For(i,1,n)
    For(i,1,m){
        f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);
        if(a[i]==a[j])f[i][j]=min(f[i-1][j-1],f[i][j]);
        else f[i][j]=min(f[i][j],f[i-1][j-1]+1);
    }
cout<<f[n][m];

编辑距离

/*这个题主要是体现二维数组的应用,以前真的没见过。。。*/
#include<bits/stdc++.h>
#define N 1010
#define For(i,l,r) for(int i = l;i<=r;i++)
using namespace std;
char str[N][N],s[N];
int n,m;
int f[N][N];
int edit_distance(char a[],char b[]){//传参划重点
    int al=strlen(a+1),bl=strlen(b+1);//因为下标从1开始的
    For(i,1,al)f[i][0]=i;
    For(i,1,bl)f[0][i]=i;
    For(i,1,al)
        For(j,1,bl){
            f[i][j]=min(f[i-1][j]+1,f[i][j-1]+i);
            f[i][j]=min(f[i][j],f[i-1][j-1]+(a[i]!=b[i]));
        }
    return f[al][bl];
}
int main(){
    cin>>n>>m;
    For(i,1,n)cin>>str[i]+1;//重点
    int limit,res;
    while(m--){
        res=0;
        cin>>s+1>>limit;
        For(i,1,n)if(edit_distance(str[i],s)<=limit)res++;//传参划重点
        cout<<res<<endl;
    }
}

区间DP

/*石子合并*/
//区间DP先枚举区间长度,在枚举左端点,根据右端点取值限制左端点,然后枚举k。
For(i,1,n)cin>>s[i],s[i]+=s[i-1];
For(len,2,n)
    for(int i = 1;i+len-1<=n;i++){
        int j = i+len-1;
        f[i][j]=INF;
        For(k,i,j-1)f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+a[j]-a[i-1]);
    }
int res = f[1][n];

计数类DP

这个必须保证不重不漏

整数划分

/*f[i][j]总和是i,可以分为j个数字*/
//所以可以划分为最小数字为1和最小数字不为1的划分f[i][j]=f[i-1][j-1]+f[i-j][j];
For(i,1,n)
    For(j,1,i)
        f[i][j]=f[i-1][j-1]+f[i-j][j];
int res;
For(i,1,n)
res+=f[n][i];
cout<<res;
name.com购买域名廉价稳定无需备案 年付.xyz.site.life$3点击购买赠送5$优惠券
racknerd购买无需备案CN2服务器,速度高速稳定节日优惠力度强 节日会推出各种优惠套餐【点击注册】目前推出3H2.5G40GB6T每年$27.80两年$55.60套餐【快来注册
Last modification:May 1st, 2020 at 06:47 pm
觉得好的话就评论,转发,投币。