五、动态规划
(一).背包问题
1.01背包（每个物品最多用一次）(AcWing 2. 01背包问题)
二维朴素版
(1)算法思想：
见上图
(2)代码实现思路：
求f(i,j)，i从0开始枚举到n件物品，再用j从0开始枚举到最大体积m，由于包含i的集合可能不存在，因此先计算不包含i的集合，即f(i,j)=f(i-1,j)，若当前的状态可以划分包含i的状态，即j>=v[i],那么就计算当前枚举的f(i,j)最终值，即max(f((i-1),j),f(i-1,j-v[i])+w[i]))，当全部枚举结束后，计算的就是f[n][m]，即前n个物品中总体积不超过m的最大价值。
(3)代码实现：
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N],f[N][N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>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-1][j-v[i]]+w[i]);
}
cout<<f[n][m]<<endl;
return 0;
}一维优化版
(1)算法思想：
从代码逻辑考虑删去第一维使得代码表示含义与原代码含义一致，而不是从实际逻辑重新写代码。
(2)代码实现思路：
删去f[i][j]的[i]，逆序枚举的原因简单来说就是，若正序更新，则在本轮循环i中对j进行枚举时小的j会被先更新，即j-v[i]会被先更新，因此f[j]=max(f[j],f[j-v[i]]+w[i])中f[j-v[i]]使用的就是本轮循环的i，若采用逆序更新，j就会被先更新，此时的j-v[i]就是未在本轮i更新过的数据，也就是上一轮i-1的数据，因此符合原来的公式。
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
{
f[j]=f[j];//删去一维后仍然能够保证f[i][j]=f[i-1][j]，因为对该等式而言，右侧的值赋给左侧的值，就是将原来的第i-1层的f[j]赋值给了现在的第i层f[j]，其中右侧的值没有被更新过，因此可以这样更改
if(j>=v[i]) f[j]=max(f[j],f[j-v[i]]+w[i]);//我们期待删去一维后仍能保证f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i])，分析该等式，对该等式而言左侧的f[j]和右侧的f[j]显然能保证原来的性质，因此重点考虑f[j-v[i]]是否为原来的f[i-1][j-v[i]]，由于j是从小到大开始枚举，每次枚举都会更新，而j-v[i]肯定小于j，因此j-v[i]先于j更新，因此对于j-v[i]而言，它也是在本次循环中更新的，即i,而不是之前的循环，即i-1，而我们期待的是用上一层（i-1）的f[j-v[i]]来更新f[j]，因此我们令j先于j-v[i]更新，也就是将j从大到小开始枚举。
}
//最终由于f[j]=f[j]为恒等式，可以删去，if(j>=v[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]);(3)代码实现：
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N],f[N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>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]);
}
cout<<f[m]<<endl;
return 0;
}2.完全背包（每个物品不限制次数）(AcWing 3. 完全背包问题)
二维朴素版（会超时）
(1)算法思想：
与01背包思路相同，只是在集合划分上有所区别，以f(i,j)为例，对其进行下一步划分，考虑以取i物品的次数k次划分集合，若k等于0，则相当于f(i-1,j)，若k不等于0，则采取01背包类似的办法，将i物品先全部取出，不影响最终选法的求解，即求f(i-1,j-k*v[i]),最后再加上k*w[i]，即f(i-1,j-k*v[i])+k*w[i],不难发现k=0情况可以与之合并，最终就是取从0枚举到k的最大值中f(i-1,j-k*v[i])+k*w[i]的最大值，k的最大值可以通过j>=k*v[i]求解。
(2)代码实现思路：
通过三层循环更新最大值即可，第一层枚举物品数量，第二层枚举背包容量，第三层枚举k的可能取值。
(3)代码实现：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int v[N],w[N],f[N][N];
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
for(int k=0;k*v[i]<=j;k++)
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
cout<<f[n][m]<<endl;
return 0;
}二维优化版
(1)算法思想：
考虑将k展开，然后对f(i,j)和f(i,j-v[i])进行比较发现规律。如下图，最终f(i,j)可以通过max(f(i-1,j),f(i,j-v[i])+w)来得出。可以看出该式与01背包朴素版很像，只是i和i-1的区别。
(2)代码实现思路：
与01背包朴素版类似，将i-1改为i。
(3)代码实现：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int v[N],w[N],f[N][N];
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>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]);
}
cout<<f[n][m]<<endl;
return 0;
}一维优化版
(1)算法思想：
对二维优化版进行类似于01背包的改进，注意此时j-v[i]为第i轮，即需要更新后的数，因此为正序。
(2)代码实现思路：
无。
(3)代码实现：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int v[N],w[N],f[N];
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>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]);
cout<<f[m]<<endl;
return 0;
}3.多重背包（每件物品取的数量有限制）
二维朴素版(AcWing 4. 多重背包问题 I)
(1)算法思想：
与完全背包问题几乎一致，在枚举k的时候加上一个条件判断（k<=给定的数量）即可
(2)代码实现思路：
无
(3)代码实现：
#include <iostream>
#include <algorithm>
using namespace std;
const int N=110;
int n,m;
int v[N],w[N],s[N],f[N][N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>s[i];
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
for(int k=0;k<=s[i]&&k*v[i]<=j;k++)
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
cout<<f[n][m];
return 0;
}二进制优化版(AcWing 5. 多重背包问题II)
(1)算法思想：
由于按照完全背包的二维优化版会出现多出来一项无法处理的情况，因此考虑对物品选择个数进行优化，对于任意选择的数量s而言，可以考虑将若干个物品化为一个整体，即将s拆分成1，2，4，8，...2^k，C（C<2^(k+1),C=s-(2^(k+1)-1),2^(k+2)<s）如假设s为1000，我们可以将其分为每1，2，4，8，...,256,489个为一组，因此对于每一种取法，我们都可做到取某些组以达到目的，如取50个，可以通过取2，16，32来实现（当只有1组时可以实现取0~1，当有前2组时可以实现取0~3（0：都不选，1：选第1组，2：选第2组，3：选1，2组），当有前3组时可以实现取0~7，一次类推当最后一组为489时，可以实现489+256+128+...+1=1000，即取0~1000）。因此从0~s的任何一种选法都可以用这种分组的方式拼凑出来，枚举次数从s降低到log s。
因此原问题从n个物品中选择不超过s[i]件i物品，转化为对于n件物品的总分组数量cnt，对于每一块分组都有自己的体积和价值，就相当于从已知体积和价值的cnt个物品中，每件物品只选择一次，求最大价值，即01背包问题。
(2)代码实现思路：
转化物品个数：设置一个计数器cnt，统计新物品的总个数。设置每一块的原物品个数为k，每次k都以2倍增长。从1枚举n个物品，若对于当前物品的选择数量s，仍可以在分出k个为一组，则进入循环，循环中令cnt++,表示分组数量增加，再更改当前分组的属性，即将v[cnt]更改为v[i]*k,w[cnt]更改为w[i]*k（因为将k个i物品划为1组），再将s减去k，表示还有多少选择数量能够支持继续分组，最后将k翻倍。当循环结束后，若s大于0，则说明多出了C个i物品，则将其归为一组。最终会得到新的物品个数cnt。
利用01背包一维优化版得到最终答案。
(3)代码实现：
#include <iostream>
#include <algorithm>
using namespace std;
const int N =25000,M=2010;
int n,m;
int v[N],w[N],f[N];
int main()
{
cin>>n>>m;
int cnt=1;
for(int i=1;i<=n;i++)
{
int a,b,s;
cin>>a>>b>>s;
int k=1;
while(s>=k)
{
cnt++;
v[cnt]=k*a;
w[cnt]=k*b;
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]);
cout<<f[m];
return 0;
}4.分组背包(每一组最多选一个)(AcWing 9. 分组背包问题)
(1)算法思想：
与01背包思路一致，集合划分为不包含i组，包含i组第1个物品，包含i组第2个物品，...包含i组第k个物品（k表示第i组的物品数量），...，包含第i组最后一个物品。因此若不包含第i组，则f(i,j)=f(i-1,j),若包含第i组第k个物品，则计算方法类似01背包，先除去第i组的第k个物品再进行计算的取法不变，即f(i,j)=f(i-1,j-v[i][k])+w[i][k]
(2)代码实现思路：
同上
(3)代码实现：
#include <iostream>
#include <algorithm>
using namespace std;
const int N =110;
int v[N][N],w[N][N],s[N],f[N];
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>s[i];
for(int j=1;j<=s[i];j++)
cin>>v[i][j]>>w[i][j];
}
for(int i=1;i<=n;i++)
for(int j=m;j>=0;j--)
for(int k=1;k<=s[i];k++)
if(j>=v[i][k])
f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
cout<<f[m];
return 0;
}(二).线性DP
1.AcWing 898. 数字三角形
(1)算法思想：
状态表示依然可以用二维表示，即f(i,j)，i表示横坐标，j表示纵坐标（斜线），如下图。
f(i,j)表示到当前位置的路径最大数值，集合表示所有到该位置的路径，条件是只能沿着左下和右下走。集合划分根据当前（i,j）坐标的上一步是从左上还是右上来区分，若从左上来，则当前f(i,j)相当于上一位置的f(i-1,j-1)加上当前位置的权值，若从右上来，则当前位置的f(i,j)也同样为上一位置的f(i-1,j)加上当前位置的权值。
(2)代码实现思路：
首先将所有位置初始化为负无穷，注意要将右上角的边界之外的数也初始化。更新完所有位置的f后，即行i从1枚举到n，列j从1枚举到i，f[i][j]=max(f(i-1,j-1)+a[i][j],f(i-1,j)++a[i][j])。更新完后取最后一行的最大值。
(3)代码实现：
#include <iostream>
#include <algorithm>
using namespace std;
const int N=510,INF=1e9;
int n;
int f[N][N],a[N][N];
int main() {
cin>>n;
for(int i=0;i<=n;i++)
for(int j=0;j<=i+1;j++)
a[i][j]=-INF;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
cin>>a[i][j];
f[1][1]=a[1][1];
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
f[i][j]=max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j]);
int res=-INF;
for(int i=1;i<=n;i++)
res=max(res,f[n][i]);
cout<<res;
return 0;
}
2.AcWing 895. 最长上升子序列
(1)算法思想：
该题状态表示可以采用一维，即f[i]表示前i个数的最大上升子序列，集合为以第i个数为结尾的上升子序列，集合可以根据i前面的所有位置来划分，若前面的某j位置的权值小于第i 个位置，则当前第i位置的f[i]=f[j]+1，若j位置的权值大于该位置，则说明j不属于i的上升子序列，因此不用计算，枚举所有权值小于i位置前面的位置，取最大的f[j]+1即为f[i]。最后枚举所有位置的f，取最大值。
(2)代码实现思路：
同上。
(3)代码实现：
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1010;
int f[N],a[N];
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++)
{
f[i]=1;//初始化
for(int j=1;j<i;j++)
if(a[j]<a[i])
f[i]=max(f[i],f[j]+1);
}
int res=0;
for(int i=1;i<=n;i++)
res=max(res,f[i]);
cout<<res;
return 0;
}3.AcWing 896. 最长上升子序列 II(二分优化)
(1)算法思想：
就上题解法而言，对于3 1 2而言，当长度为1的子序列为3或1时，每当后面有一个大于3的数时，它也一定大于1，因此对于3而言，记录他的子序列就产生冗余，所以考虑在长度相同的子序列时，只记录最后一个数字最小的子序列，通过简单的推导，可以发现，子序列最后一个数字随序列长度的增加而增加，因此对于一个新的数字，可以采用二分来查找应该接在哪个子序列所在的最后一个数字的后面，寻找最后一个数字最小的子序列（且该数字小于这个比这个子序列长度多1 的子序列的最后一个数字），将该数字接到该子序列的最后，并替代比他长度多1 的子序列
(2)代码实现思路：
设置一个len表示最长的子序列长度，q[]表示每一个长度的序列的最后一个数字，然后用i枚举每一个数，初始化第一个子序列的最后一个数为负无穷，然后用二分查找小于该数的最大的数字，也就是最后一个小于该数的数字（二分模板一），将二分左端点设为0，二分右端点设为该距离len，然后查找该区间内小于该数的最后一个数.然后再更新此时该长度+1的序列的最后一个数字，最终查找的r就是可以接在该长度的后面，即q[r+1]=a[i],最后更新长度,即len=max(len,r+1)
(3)代码实现：
#include <iostream>
#include <algorithm>
using namespace std;
const int N=100010;
int n;
int a[N],q[N];
int main()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
int len=0;
for(int i=0;i<n;i++)
{
q[0]=-2e9;
int l=0,r=len;
while(l<r)
{
int mid=(l+r+1)>>1;
if(q[mid]<=a[i]) l=mid;
else r=mid-1;
}
len=max(len,r+1);
q[r+1]=a[i];
}
cout<<len;
return 0;
}
3.AcWing 897.最长公共子序列
(1)算法思想：
采用二维表示状态，f(i,j)，其中i表示第一个序列的前i个字母，j表示第二个序列前j个字母，集合为所有在第一序列前i个字母且在第二序列前j字母中都出现的子序列，以a[i],b[j]是否出现在子序列当中作为划分依据，若都不在，则f(i,j)=f(i-1,j-1),若都在，则f(i,j)=f(i-1,j-1)+1,若只有a[i]在，则可以用一个包含该情况的状态表示，即f(i,j-1)，由于求最大值，且该状态包含该划分的集合，因此可以采取该状态表示，同理若只有b[j]在，则f(i,j)=f(i-1,j)，又由于取最大值并且f(i-1,j-1)状态包含在f(i,j-1)和f(i-1,j)两状态的并集之中。
(2)代码实现思路：
当a[i],b[i]都出现在子序列当中时，a[i]一定等于b[i]，因此可以加上一个条件判断
(3)代码实现：
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1010;
int n,m;
char a[N],b[N];
int f[N][N];
int main()
{
cin>>n>>m;
scanf("%s%s",a+1,b+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]);
if(a[i]==b[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1);
}
cout<<f[n][m];
return 0;
}
4.编辑距离
AcWing 902.最短编辑距离
(1)算法思想：
状态表示可以用二维f(i,j)表示，集合为所有将第一个字符串前i个字符变为第二个字符串前j个字符的方式的操作数量，f(i,j)表示这些方式的操作方式最少的一个。集合可以根据第一个字符串的第i个位置要进行什么操作才可以与第二个字符串的前j个字符相等分为删去第i个字符，即前i-1个字符已经与第二个字符串的前j个字符相同，因此只需要在上一个状态加上删去操作即可，即f(i,j)=f(i-1,j)+1；增加第i个字符才能与第二个字符串的前j个字符相等，即前i-1个字符已经与第二个字符串的前j-1个字符相同，因此只需要在上一个状态加上增加第i个字符操作即可，即f(i,j)=f(i-1,j-1)+1；修改第i个字符，即前i-1个字符已经与第二个字符串的前j-1个字符相同，再比较第i个字符是否与第j个字符相同，若相同就不用操作，若不同则需要增加一次修改操作,即f(i,j)=f(i-1,j-1)+0 or 1。最终f(i,j)取三者最小值
(2)代码实现思路：
首先初始化，当第一个字符长度为0，第二个字符长度为i时，需要i次添加操作，当第一个字母长度为i，第二个字符串长度为0时，需要i次删除操作。然后再进行状态计算。
(3)代码实现：
#include <iostream>
using namespace std;
const int N=1010;
char a[N],b[N];
int f[N][N];
int n,m;
int main()
{
scanf("%d%s",&n,a+1);
scanf("%d%s",&m,b+1);
for(int i=0;i<=n;i++) f[i][0]=i;
for(int i=0;i<=m;i++) f[0][i]=i;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);
if(a[i]==b[j]) f[i][j]=min(f[i][j],f[i-1][j-1]);
else f[i][j]=min(f[i][j],f[i-1][j-1]+1);
}
cout<<f[n][m];
return 0;
}
AcWing 899.编辑距离
(1)算法思想：
与上题思路一致，不过在读入时有所区别，该题需要读入n个字符串，m次问询，因此读入n个第一个字符串，然后在每次问询中读入第二个字符串，计算n个第一个字符串要变化到第二个字符串的次数，统计在规定次数内的第一个字符串有几个。
(2)代码实现思路：
同上
(3)代码实现：
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
const int N = 15, M = 1010;
int n, m;
int f[N][N];
char str[M][N];
int edit_distance(char a[], char b[])
{
int la=strlen(a+1),lb=strlen(b+1);
for (int i=0;i<=lb;i++) f[0][i] = i;
for (int i=0;i<=la;i++) f[i][0] = i;
for (int i=1;i<=la;i++)
for (int j=1;j<=lb;j++)
{
f[i][j] = min(f[i-1][j]+1,f[i][j-1]+1);
f[i][j] = min(f[i][j], f[i-1][j-1]+(a[i]!=b[j]));
}
return f[la][lb];
}
int main()
{
scanf("%d%d", &n,&m);
for (int i=0;i<n;i++) scanf("%s",str[i]+1);
while (m--)
{
char s[N];
int limit;
scanf("%s%d",s+1,&limit);
int res=0;
for (int i=0;i<n;i++)
if (edit_distance(str[i],s) <= limit)
res ++ ;
printf("%d\n", res);
}
return 0;
}