dp

#include<bits/stdc++.h>
using namespace std;
int dp[1010][1010];
//定义二位dp数组,存储每个小解的答案以及最后的答案
string a,b;
int main(){
    cin>>a>>b;
    int n=a.size(),m=b.size();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i-1]==b[j-1]){
                dp[i][j]=dp[i-1][j-1]+1;
                //比较两个字符串的最后一个字符,检查是否匹配成功;
                //若不：进行下面两种情况的枚举
            }else{
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
            //dp[i-1][j]指b与a的前面试图匹配;
            //另一个反之,指a与b的前面试图匹配,取一个较大值则是因为若匹配成功会+1
        }
    }cout<<dp[n][m];
    return 0;
}