分析
很简单的一道动态规划,而且没有打印路径 我的思路也是来自《算法导论》,但是看了一个台湾朋友的博客才算是明白了一点点。 他是这么想的,将两个字符串各取最后一个的e1,e2,这样原字符串可以表示为sub1+e1,sub2+e2,
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
char X[1000];
char Y[1000];
int C[1000][1000];
int LCS(char* X,char* Y,int m,int n)
{
for(int i=1;i<=m;i++)
C[i][0]=0;
for(int i=0;i<=n;i++)
C[0][i]=0;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
if(X[i-1]==Y[j-1])
C[i][j]=C[i-1][j-1]+1;
else if(C[i-1][j]>=C[i][j-1])
C[i][j]=C[i-1][j];
else
C[i][j]=C[i][j-1];
}
return C[m][n];
}
int main()
{
freopen("in.txt","r",stdin);
while(cin>>X>>Y){
int m=strlen(X);
int n=strlen(Y);
int ans=LCS(X,Y,m,n);
printf("%d\n",ans);
memset(X,0,sizeof(X));
memset(Y,0,sizeof(Y));
memset(C,0,sizeof(C));
}
}
后来再补充!