OI

【动态规划】各种DP模板(持续更新…)

今年的寒假作业是openjudge的DP题，打算在这里边做边记录。

一、最大不上升链（拦截导弹）

最早接触的DP（其实应该是数学三角形），比较好理解，然而也很基础，比如那个POLYGON就是一个变形（大概）。

设F[i]表示a[i]在链中的最大长度

F[i]=max{F[j]+1}, 1<j<i<=n, a[i]<a[j], f[1]=1(或者大于（等于），取决于啥链)

1
2
3
4
5
6
for(i=1;i<=n;i++){
  f[i]=1;
  for(j=1;j<i;j++)
    if(f[i]<f[j]+1&&a[i]>a[j])f[i]=f[j]+1;
  if(max<f[i])max=f[i];
}

另外，还可以由$O(n^2)$优化为$O(nlogn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int bisearch(int key,int l,int r){
    while(l<r){
      int mid=(l+r)>>1;
      if(key>=f[mid])l=mid+1;
      else r=mid;
    }
    return l;
}
f[1]=t;
for(i=2;i<=n;i++){
  scanf("%d",&t);
  if(f[ans]<t){j=ans+1;ans++;}
  else j=bisearch(t,1,ans);
  f[j]=t;
}
printf("%d",ans);

二、最长公共子序列

其实和不上升链差不多，只是因为两个链要分别记录，所以要二维动规了，转移方程也挺好懂的。

而且，C里面逻辑表达式可以直接加，所以写起来很方便。

设有二维数组f[i][j] 表示 X 的 i 位和 Y 的 j 位之前的最长公共子序列的长度，则有：

f[1][1] = same(1,1);

f[i][j] = max{f[i-1][j -1] + same(i,j),f[i-1][j],f[i][j-1]};

其中，same(a,b)当 X 的第 a 位与 Y 的第 b 位相同时为“1”，否则为“0”。

(摘自百度百科)

1
2
3
4
5
6
f[1][1]=(a[0]==b[0]);
for(i=1;i<=strlen(a);i++)
  for(j=1;j<=strlen(b);j++){
    f[i][j]=max(max(f[i][j-1],f[i-1][j]),f[i-1][j-1]+(a[i-1]==b[j-1]));
    m=max(m,f[i][j]);
  }

完整写法在这里

三、01背包

最经典的动规。给定的背包容量n,m件物品，体积为c[i],价值为w[i]。

设F[i][j]表示前i件物品放入容量为j的背包的最优值

转移方程为：

F[i][j]=max{F[i-1][j],F[i-1][j-c[i]]+w[i]}//对于第i件不放的情况和放了（减去第i件物品容量的包的最优值加上第i件的价值）

1
2
3
4
5
6
for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
        if(j>=c[i])
        f[i][j]=max(f[i-1][j],f[i-1][j-c[i]]+w[i]);
        else f[i][j]=f[i-1][j];
    }

同时，注意到每次只需取f[i-1][j]，因此还可以使用压成一维。因为要用到之前的数据，这里的内层循环遍历容量时要从大到小：

1
2
3
4
for(i=1;i<=n;i++)
  for(j=m;j>=0;j--)
    if(j>=c[i]&&f[j]<f[j-c[i]]+w[i])
      f[j]=f[j-c[i]]+w[i];

另外，增加约束条件的也是一样，增加维度即可

1
2
3
4
5
for(i=1;i<=n;i++)
  for(j=m1;j>=c1[i];j--)
    for(k=m2;k>=c2[i];k--)
      if(f[j][k]<f[j-c1[i]][k-c2[i]]+w[i])
        f[j][k]=f[j-c1[i]][k-c2[i]]+w[i];

四、完全背包

1
2
3
4
5
6
for(int i=1;i<=n;i++)
    for(int j=0;j<=m;j++){
        if (j<c[i])f[i][j]=f[i-1][j];
        else f[i][j]=max(f[i-1][j],f[i][j-c[i]]+w[i]);
    }
printf("%d",f[n][m]);
1
2
3
4
for(int i=1;i<=n;i++)
    for(int j=c[i];j<=m;j++)
        f[j]=max(f[j],f[j-c[i]]+w[i]);
printf("%d",f[m]);

五、树形DP

树形DP是一种特殊的DP，利用树形结构的无环、分层、有很好的递归性质的特点，进行状态转移。常用dfs整棵树+记忆化的方式实现。

详见