最近練習動態(tài)規(guī)劃，很經(jīng)典的一個問題，也很基礎。
以下是我的代碼：
#include<stdio.h>
#include<string.h>
#define maxn 1007
#define max(a,b) (a>b?a:b)
char a[maxn],b[maxn];
long lena,lenb,d[maxn][maxn];
int main()
{
while(gets(a)&&gets(b))
{
lena=strlen(a);
lenb=strlen(b);
memset(d,0,sizeof(d));
for(long i=1;i<=lena;i++)
for(long j=1;j<=lenb;j++)
{
d[i][j]=max(d[i-1][j],d[i][j-1]);
if(a[i-1]==b[j-1])
d[i][j]=max(d[i][j],d[i-1][j-1]+1);
}
printf("%ld\n",d[lena][lenb]);
}
return 0;
}
posted on 2010-03-01 19:12
lee1r 閱讀(642)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：動態(tài)規(guī)劃