最长公共子序列（LCS DP）

状态：d[i][j]，i，j表示下标，A[1~i]和B[1~j]的最长LCS 

状态转移：d[i][j]-->  1)A[i]==B[j] d[i][j]=d[i-1][j-1]+1;

                                    2)A[i]!=B[j] d[i][j]=max(d[i-1][j],d[i][j-1]);

const int maxn=1000+5;  
int A[maxn],B[maxn],n1,n2,d[maxn][maxn]={0},path[maxn];         
int main()
{scanf("%d",&n1);for(int i=1;i<=n1;i++) cin>>A[i];scanf("%d",&n2);for(int j=1;j<=n2;j++) cin>>B[j];int p=0,ans=0;for(int i=1;i<=n1;i++)for(int j=1;j<=n2;j++){if(A[i]==B[j]) d[i][j]=d[i-1][j-1]+1,path[p++]=A[i];else d[i][j]=max(d[i-1][j],d[i][j-1]);ans=max(ans,d[i][j]);}//	for(int i=1;i<=n1;i++)
//	{
//		for(int j=1;j<=n2;j++)
//		cout<<d[i][j];
//		cout<<endl;
//	}cout<<ans<<endl;
//	for(int i=0;i<p;i++) cout<<path[i]<<' ';
//	cout<<endl;
}