关于dp的几个模板的简记_dp基础模板

01背包的模板套用，一维数组 样题

​
  int dp[MAXN];
  for(int i=0;i<n;i++)
  for(int j=W;j>=w[i];j--)//这里要记住，是j=w,j--，后面在处理完全背包问题时，就会反过来，在这里不在多说，只是提醒一下
  dp[j]=max(dp[j],dp[j-w[i]]+v[i]);//dp[i][j]表示的是第i个物品在容积为j时的价值。
  printf("%d\n",dp[W]);
 
​

完全背包  一维数组  样题，密码就是hpuacm

int dp[MAXN];
for(int i=0;i<n;i++)
for(int j=w[i];j<=W;j++)//看这里就是我上面是说的不同之处，首先这样的处理可以实现在容积w的限制下，物品i的多次使用，而01背包的逆向处理就无法实现这个无限次利用，想不明白可以自己拿纸试一下
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
printf("%d\n",dp[W]);

多重背包  

for(int i=0;i<n;i++)
{
    int num=m[i];// 用来找a
    for(int k=1;num >0;k< <=1)
    {
        int mul=min(k,num);
        for(int j=W;j>=w[i]*mul;j--)
         {
           dp[j]=max(dp[j],dp[j-w[i]*mul]+v[i]*mul);
         }
    num -=mul;
    }
}
printf("%d\n",dp[W]);

先溜了，回寝室，有时间再补

——————————————分割线————————————

对于最大公共公共子序列：

for(int i=0;i<s.size();i++)//s，s2表示两个字符，这里是使用的string类
        {
            for(int j=0;j<s2.size();j++)
            {
                if(s[i]==s2[j]) dp[i+1][j+1]=dp[i][j]+1;如果两个字符各自在第i个位置和第j个位置相等，那么dp[i][j]的状态一定是从他们各自相等的字符的状态+1得到
                else dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
            }
        }