最长公共子序列，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个数列 S ，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。

d[i][j]表示s1的第i位和s2的第j位之前的最长公共子序列长度.

转移方程:

d[i][j]=d[i-1][j-1]+1                  (s1[i-1]==s2[j-1])

d[i][j]=max(d[i-1][j],d[i][j-1])     (s1[i-1]<>s2[j-1])

#include <cstdio>  
#include <cstring>  
//using namespace std;  
#define maxn 1000
char s1[maxn],s2[maxn];
int len1,len2;
int d[maxn][maxn];

int inline max(int a,int b){return a>b?a:b;};

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int i,j;
    while(scanf("%s%s",s1,s2)!=EOF)
    {
        len1=strlen(s1);
        len2=strlen(s2);
        for(i=0;i<=len1;i++)
            for(j=0;j<=len2;j++)
            {
                if(i==0||j==0)
                    d[i][j]=0;
                else if(s1[i-1]==s2[j-1])
                    d[i][j]=d[i-1][j-1]+1;
                else
                    d[i][j]=max(d[i-1][j],d[i][j-1]);
            }
        printf("%d\n",d[len1][len2]);
    }
}

为什么是之前的?因为这样初始化方便吧.

若d[i][j]表示算上s1[i]和s2[j]的.则代码为:

#include <cstdio>  
#include <cstring>  
//using namespace std;  
#define maxn 1000
char s1[maxn],s2[maxn];
int len1,len2;
int d[maxn][maxn];
 
int inline max(int a,int b){return a>b?a:b;};
 
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    int i,j;
    while(scanf("%s%s",s1,s2)!=EOF)
    {
        len1=strlen(s1);
        len2=strlen(s2);
        d[0][0]=(s1[0]==s2[0])?1:0;
        for(i=1;i<len1;i++)
            if(s1[i]==s2[0])
                d[i][0]=1;
            else
                d[i][0]=max(0,d[i-1][0]);
        for(j=1;j<len2;j++)
            if(s1[0]==s2[j])
                d[0][j]=1;
            else
                d[0][j]=max(0,d[0][j-1]);
 
        for(i=1;i<len1;i++)
            for(j=1;j<len2;j++)
            {
                if(s1[i]==s2[j])
                    d[i][j]=d[i-1][j-1]+1;
                else
                    d[i][j]=max(d[i-1][j],d[i][j-1]);
            }
        printf("%d\n",d[len1-1][len2-1]);
    }
}