#include<iostream>#include<cstdio>#include<cstring>using namespace std;int dp[1000+5];char s1[1000+5],s2[1000+5];int main(){	int N,n,i,j,olddp,t;	cin>>N;	while(N--)	{		memset(dp,0,sizeof(dp));		scanf("%s",s1);		scanf("%s",s2);		for(i = 0;s2[i] != '/0';i++)		{			olddp=0;			for(j = 0;s1[j] != '/0';j++)			{				t=dp[j];				if(s1[j]==s2[i])	dp[j]=olddp+1;				else if(dp[j]<dp[j-1])	dp[j]=dp[j-1];				olddp=t;			}		}		cout<<dp[j-1]<<endl;	}	return 0;}這里j = x序列的長(zhǎng)度，故dp[j-1]的值即為x序列與y序列的LCS的長(zhǎng)度。可能dp[j-3] = dp[j-2] = dp[j-1]，但是dp數(shù)組的最后一個(gè)值一定為最大值。