著名问题(LCS，Longest Common Subsequence)
d[i][j]:=s1…si和t1…ti对应的LCS的长度
由此s1…s（i+1）和t1…t（i+1）对应的公共子列可能是
1.当s(i+1)=t(j+1)时，在s1.s(i)和t1.t(i)的公共子列末尾追加上s(i+1)
s1..si和t1…t（j+1）的公共子列
s1..s（i+1）和t1…tj的公共子列
三者中的某一个，所有就如下递推关系
dp[i+1][j+1]=
1.max(dp[i][j]+1,dp[i][j+1],dp[i+1][j]) (si+1=tj+1)
2.max(dp[i][j+1],dp[i+1][j])
AC:
#include<cstdio>#include<algorithm>#include<cstring>#define MAX 1000using namespace std;int m,n;char s[MAX],t[MAX];int dp[MAX + 1][MAX + 1];int main(){while(scanf("%s%s",s,t)!=EOF){memset(dp,0,sizeof(dp));m=strlen(s);n=strlen(t);for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(s[i]==t[j]) dp[i+1][j+1]=dp[i][j]+1;else dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);}}printf("%d\n",dp[m][n]);}return 0;}
版权声明：本文为博主原创文章，，未经博主允许不得转载。
人只要不失去方向，就不会失去自己
