f(i-1,j-1)+1 (a[i]==b[j])
f(i,j)= {
max(f(i-1,j),f(i,j-1)) (a[i]!=b[j])
#include#include int dp[1000][1000]; int max(int a,int b) { return a=a>b a:b; } int main() { char s1[1000],s2[1000]; while(scanf("%s%s",s1+1,s2+1)!=EOF) { memset(dp,0,sizeof(dp)); int i=0; int j=0; for(i=1;s1[i]!='\0';i++) { for(j=1;s2[j]!='\0';j++) { if(s1[i]==s2[j]) { dp[i][j]=dp[i-1][j-1]+1; } else { dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } } } printf("%d\n",dp[i-1][j-1]); } }