小题解

这题用dp
转移方程在代码里了

#include<bits/stdc++.h>
using namespace std;
char X[1005],Y[1005];
int ans,dp[1005][1005];
// if(X[i]==Y[i]) dp[i][j]=dp[i-1][j-1]+1
// else dp[i][j]=max(dp[i-1][j],dp[i][j-1])
int main(){
	scanf("%s\n%s",X+1,Y+1);
	
	int lx=strlen(X+1),ly=strlen(Y+1); //长度 
	
	for(int i=1;i<=lx;i++){
		for(int j=1;j<=ly;j++){
			if(X[i]==Y[j]){
				dp[i][j]=dp[i-1][j-1]+1;//转移方程
			}
			else{
				dp[i][j]=max(dp[i-1][j],dp[i][j-1]);//转移方程
			}
		}
	}
	cout<<dp[lx][ly];
	return 0;
}