#include<stdio.h>
#include<string.h>
#define N 1010
#define max(x,y) x>y?x:y
int dp();
char s1[N];
char s2[N];
int main(){
int n;
scanf("%d",&n);
while(n--){
scanf("%s",s1);
scanf("%s",s2);
printf("%d
",dp());
}
return 0;
}
int dp(){
int x,y,a,b;
a=strlen(s1);
b=strlen(s2);
int num[N][N]={0};
for(x=1;x<=a;x++){
for(y=1;y<=b;y++){
if(s1[x-1]==s2[y-1]){
num[x][y]=num[x-1][y-1]+1;
}
else{
num[x][y]=max(num[x-1][y],num[x][y-1]);
}
}
}
return num[a][b];
}虽然是经典的DP问题。。。表示还是有些压力，表示，调用strlen函数也是需要很多时间的，今天才发现，结果就是，TLE很多次才通过，，
最近要考试了，所以，，，还是减慢速度吧，，，从开始做题到现在已经有了2个月了，总算是对搜索和动规有些思路了，继续加油
版权声明：本文为博主原创文章，未经博主允许不得转载。