1.最长公共子序列

for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        f[i][j]=max(f[i-1][j],f[i][j-1]);  //不包含a[i]包含b[j] 和包含a[i]不包含b[j]取最大值
        if(a[i]==b[j])f[i][j]=max(f[i][j],f[i-1][j-1]+1);//当前和(不包含a[i]不包含b[j])+1 取最大值
    }
    cout<<f[n][m];

2.最长上升子序列

for(int i=1;i<=n;i++)
    {
        h[i]=1;
        for(int j=1;j<i;j++)
        if(a[i]>a[j])
        h[i]=max(h[i],h[j]+1);

        ans=max(ans,h[i]);
    }
    cout<<ans;

3.01背包

for(int i=1;i<=n;i++)
    for(int j=0;j<=m;j++)
    {
        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]);
    }
//空间优化
for(int i=1;i<=n;i++)
    for(int j=m;j>=v[i];j--)
    {
        f[j]=max(f[j],f[j-v[i]]+w[i]);
    }

完全背包

for(int i=1;i<=n;i++)
    for(int j=0;j<=m;j++)
    {
        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(int i=1;i<=n;i++)
    for(int j=v[i];j<=m;j++)
        f[j]=max(f[j],f[j-v[i]]+w[i]);

多重背包

for(int i=1;i<=n;i++)
    for(int j=0;j<=m;j++)
    for(int k=0;k<=s[i]&&v[i]*k<=j;k++)
    f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);

多重背包优化

    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        int a,b,s;
        cin>>a>>b>>s;
        int k=1;
        while(k<=s)
        {
            cnt++;
            v[cnt]=a*k,w[cnt]=b*k;
            s-=k;
            k*=2;
        }
        if(s>0)
        {
            cnt++;
            v[cnt]=s*a,w[cnt]=s*b;
        }
    }
    n=cnt;
    for(int i=1;i<=n;i++)
    for(int j=m;j>=v[i];j--)
    f[j]=max(f[j],f[j-v[i]]+w[i]);

分组背包

 for(int i=1;i<=n;i++)
        for(int j=m;j>=0;j--)
            for(int k=0;k<s[i];k++)   //s[i]是每组物品数
            if(j>=v[i][k])
            f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);