线性DP

正推反推、分解子问题->状态表示->分类讨论->转移方程->优化

分解子问题，状态表示：
$F[i][j]$：$a_i$和$b_j$最长公共子序列

分类讨论

if(a[i]==b[j]) 
    f[i][j]=1+f[i-1][j-1];
else 
    f[i][j]=max(f[i-1][j],f[i][j-1]);

C++ 代码

#include<iostream>

using namespace std;
const int N=1010;

int f[N][N];
char a[N],b[N];

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=m;i++){
        cin>>b[i];
    }
    int res=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i]==b[j]) f[i][j]=1+f[i-1][j-1];
            else f[i][j]=max(f[i-1][j],f[i][j-1]);
            res=max(res,f[i][j]);
        }
    }
    cout<<res;

    return 0;
}