使用闫氏dp分析法真的好用啊，y总yyds！！

纪念一下第一次独自分析并代码实现了线性dp的字符串问题！！！（注释详细）

最长公共子序列

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1010;
int f[N][N];  //表示从a[1~i]中和b[1~j]中的公共子序列的长度最大值的集合
char a[N],b[N];
int n,m;
int main()
{
    scanf("%d%d",&n,&m);
    scanf("%s%s",a+1,b+1);  //从下标为1读入更好处理
    //a一个字符不选，b选任意长度的字符，其公共子序列长度的最大值都为0
    for (int j=0;j<=m;j++) f[0][j]=0;  
    //同理，b一个字符都不选，a选任意长度的字符，其公共子序列长度的最大值为0
    for (int i=0;i<=n;i++) f[i][0]=0;

    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
        {
            //这是选a[i]不选b[j]和选b[j]不选a[i]的两种选择情况取max
            f[i][j]=max(f[i][j-1],f[i-1][j]);
            //当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);
            else f[i][j]=max(f[i][j],f[i-1][j-1]); //否则只能都不选了
        }
    printf("%d\n",f[n][m]);
    return 0;
}