注意：当dp要用到上一层的状态如f(i-1)时，下标最好从1开始，下标0直接初始化为0，避免越界。

A：数字三角形

入门题，稍作推导便知道第(i,j)个位置的最大值计算路径必然来自其上的 (i-1, j-1) 和 (i-1, j) 两点。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int N=510,INF=1e9;
  5. int n;
  6. int f[N][N],a[N][N];
  8. int main()
  9. {
  10.     cin>>n;
  11.     for(int i=1;i<=n;i++)
  12.         for(int j=1;j<=i;j++)
  13.             cin>>a[i][j];
  15.     for(int i=1;i<=n;i++)
  16.         for(int j=0;j<=i+1;j++) //因为计算涉及到(i-1,j-1)(i-1,j)，要考虑边界在数字三角形周围一圈
  17.             f[i][j]=-INF;
  19.     f[1][1]=a[1][1];    //不要忘记赋初值
  20.     for(int i=2;i<=n;i++)
  21.         for(int j=1;j<=i;j++)
  22.             f[i][j]=max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j]);
  24.     int ans=-INF;
  25.     for(int i=1;i<=n;i++)   //遍历最底下一层得到最大值
  26.         ans=max(ans,f[n][i]);
  28.     cout<<ans<<endl;
  29.     return 0;
  30. }

B：最长上升子序列I

模板题 O(n^2)

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int N=1010;
  5. int n,f[N],a[N];
  7. int main()
  8. {
  9.     cin>>n;
  10.     for(int i=1;i<=n;i++)
  11.         cin>>a[i];
  13.     for(int i=1;i<=n;i++)
  14.     {
  15.         f[i]=1;
  16.         for(int j=1;j<i;j++)
  17.             if(a[j]<a[i])
  18.                 f[i]=max(f[i],f[j]+1);
  19.     }
  21.     int ans=0;
  22.     for(int i=1;i<=n;i++)
  23.         ans=max(ans,f[i]);
  24.     cout<<ans<<endl;
  26.     return 0;
  27. }

如果要保存最长子序列：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int N=1010;
  5. int n,f[N],a[N];
  6. int g[N];    //存最长上升子序列
  8. int main()
  9. {
  10.     cin>>n;
  11.     for(int i=1;i<=n;i++)
  12.         cin>>a[i];
  14.     for(int i=1;i<=n;i++)
  15.     {
  16.         f[i]=1;    //表示只有本身一个数
  17.         g[i]=0;    
  18.         for(int j=1;j<i;j++)
  19.             if(a[j]<a[i])
  20.                 if(f[i]<f[j]+1)
  21.                 {
  22.                     f[i]=f[[j]+1;
  23.                     g[i]=j;    //保存f[k]从哪转移的（下标）
  24.                 }
  25.     }
  27.     int k=1;    //记下标
  28.     for(int i=1;i<=n;i++)
  29.         if(f[k]<f[i])
  30.             k=i;
  31.     cout<<f[k]<<endl;
  33.     for(int i=0,len=f[k];i<len;i++)    //这是倒序输出（降序）
  34.     {
  35.         cout<<a[k]<<endl;    //因为f[k]表示的是以a[k]结尾的最长上升子序列长度，所以输出a[k]
  36.         k=g[k];    //f[k]是从g[k]转移过来的
  37.     }
  39.     return 0;
  40. }

C：最长上升子序列II

这题把数据加到了n<=100000，显然要对上面的算法进行优化。
（显然我们直接记牢这个算法即可hhh）

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int N = 100010;
  5. int n,q[N],a[N];
  6. //q[k]：a序列从第1个元素至第k个元素，所有以a[k]为结尾的上升子序列中，最小的结尾元素值。注意，这里保证了以a[k]结尾的上升子序列的末尾元素一定是最小的！
  8. int main()
  9. {
  10.     cin>>n;
  11.     for(int i=0;i<n;i++)
  12.         cin>>a[i];
  14.     int len = 0;//长度为len的上升子序列
  15.     q[0]=-2e9;//初始化
  16.     for(int i=0;i<n;i++)
  17.     {
  18.         int l=0,r=len;
  19.         while(l<r)//二分查找
  20.         {
  21.             int mid=l+r+1>>1;
  22.             if(q[mid]<a[i]) l=mid;
  23.             else r=mid-1;
  24.         }
  25.         len=max(len,r+1);
  26.         q[r+1]=a[i];
  27.     }
  28.     cout<<len<<endl;
  29.     return 0;
  30. }

D：最长公共子序列

f 是dp数组，f(i, j) 是集合：所有在 a 序列前 i 个字母中出现，且在 b 序列的前 j 个字母中出现的公共子序列
那么 f(i, j) 由四种情况转移：
(1)不包含 a[i]、b[i] 👉 f[i-1][j-1]
(2)不包含 a[i]，包含b[i] 👉 f[i-1][j]（左边情况含于右式，在求最大值的问题中可以借助右式进行计算）
(3)包含 a[i]，不包含b[i] 👉 f[i][j-1]（同理）
(4)包含a[i]、b[i] 👉 f[i-1][j-1]+1（去掉第 a[i]、b[j]，在直接加上1，代表 a[i]、b[j] 已经必选）

注意：情况(1)显然含于情况(2、3)，所以可以省略。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int N=1010;
  5. int n,m;
  6. char a[N],b[N];
  7. int f[N][N];//这里的f是dp数组，f(i,j)是集合：所有在a序列前i个字母中出现，且在b序列的前j个字母中出现的公共子序列
  9. int main()
  10. {
  11.     cin>>n>>m;
  12.     cin>>a+1>>b+1;
  14.     for(int i=1;i<=n;i++)    //两层for进行状态枚举
  15.         for(int j=1;j<=m;j++)
  16.         {
  17.             f[i][j]=max(f[i-1][j],f[i][j-1]);
  18.             if(a[i]==b[j])
  19.                 f[i][j]=max(f[i][j],f[i-1][j-1]+1);
  20.         }
  22.     cout<<f[n][m]<<endl;
  24.     return 0;
  25. }

E：最短编辑距离

这题是公共子序列的应用。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int N=1010;
  5. char a[N],b[N];
  6. int n,m;
  7. int f[N][N];
  8. //f(i,j)表示a的前i个字母与b的前j个字母相匹配
  10. int main()
  11. {
  12.     cin>>n,cin>>a+1;
  13.     cin>>m,cin>>b+1;
  15.     //初始化f数组
  16.     for(int i=0;i<=n;i++)//a的前0～n个长度的串与b的长度为零(就是空的意思)相比，只能删，删i个
  17.         f[i][0]=i;
  18.     for(int i=0;i<=m;i++)//a的长度为0的串(就是空的意思)与b的前0～n个长度的串相比，只能添，添i个
  19.         f[0][i]=i;
  21.     for(int i=1;i<=n;i++)
  22.         for(int j=1;j<=m;j++)
  23.         {
  24.             f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);
  25.             f[i][j]=min(f[i][j],f[i-1][j-1]+(a[i]!=b[j]));
  26.         }
  27.     cout<<f[n][m]<<endl;
  29.     return 0;
  30. }

F：编辑距离

也是对公共子序列的应用，与上题差不多。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int N=15,M=1010;
  5. int n,m,f[N][N];
  6. char str[N][N];
  8. int edit_distance(cahr a[],char b[])
  9. {
  10.     int la=strlen(a+1),lb=strlen(b+1);//注意这里是从下标1开始
  12.     for(int i=0;i<=la;i++) f[i][0]=i;  //对dp数组进行初始化
  13.     for(int i=0;i<=lb;i++) f[0][i]=i;
  15.     for(int i=1;i<=la;i++)
  16.         for(int j=1;j<=lb;j++)
  17.         {
  18.             f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);//注意这里的写法
  19.             f[i][j]=min(f[i][j],f[i-1][j-1]+(a[i]!=b[j]);
  20.         }
  22.     return f[la][lb];
  23. }
  25. int main()
  26. {
  27.     cin>>n>>m;
  28.     for(int i=0;i<n;i++)
  29.         cin>>str[i]+1;
  31.     while(m--)
  32.     {
  33.         char s[N];
  34.         int limit;
  35.         cin>>s+1,cin>>limit;
  37.         int ans=0;
  38.         for(int i=0;i<n;i++)
  39.             if(edit_distance(str[i],s)<=limit)
  40.                 ans++;
  42.         cout<<ans<<endl;
  43.     }
  45.     return 0;
  46. }