C[i][j] = 2.Max(C[i+1][j],C[i][j+1]) (X[i]!=Y[j])

#include"stdio.h"
#include"stdlib.h"
#include"string.h"
#define N 10010
char X[N],Y[N];
int C[N][N];
void Solve(int m,int n)
{
      int i,j;
      for(i=0;i<=m;i++)
      {
            C[i][n]=0;
      }
      for(j=0;j<=n;j++)
      {
            C[m][j]=0;
      }
      for(i=m-1;i>=0;i--)
      {
            for(j=n-1;j>=0;j--)
            {
                  if(X[i]==Y[j])
                  {
                        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];
                        }
                  }
            }
      }
}
int main()
{
while(scanf("%s%s",X,Y)==2)
{
      int m=strlen(X);
      int n=strlen(Y);
      Solve(m,n);
      printf("%d\n",C[0][0]);
}
return 0;
}

--转自