最长公共子序列

Longest common subsequence问题：已知两序列，求这两个序列的最长公共子序列（不一定要连续）的长度。设二维数组dp[i][j]表示长度分别为i和j的序列 A和B的LCS的最大长度，有状态转移方程：A[i]=B[j]时，dp[i][j]=dp[i-1][j-1]+1；A[i]≠B[j]时，dp[i] [j]=max{dp[i-1][j],dp[i][j-1]}。
    通过观察发现，状态dp[i][j]只与当前行(dp[i][j-1])和上一行(dp[i-1][j]，dp[i-1][j-1])的状态有关。这样， 我们可以设置2个一维数组c1[],c2[]，其中c1[]保存上一行的状态信息，c2[]更新当前行的状态信息，更新完毕之后再将c2[]的状态信息复 制到c1[]中，循环结束后c1[length_B]就是所求LCS的最大长度，从而降低了空间需求。

#include
#include
int main()
{
        char s1[1000],s2[1000];         //输入两个字符串序列
        int  r[1000],s[1000];           //DP记录状态结果，采用滚动数组节省空间
        int  len1,len2,i,j;
        while(scanf("%s %s",s1,s2)!=EOF)
        {
                len1 = strlen(s1);
                len2 = strlen(s2);
                for(i=0;i                    r[i]=0;
                for(i=0;i                {
                        for(j=0;j                            if(s1[i]==s[j])     //如果序列对应字符相同
                                s[j+1]=r[j]+1;
                            else//如果序列对应字符不同，取长度较大的那一个
                                s[j+1]=r[j+1]>s[j]?r[j+1]:s[j];
                        for(j=1;j<=len2;++j)
                                r[j] = s[j];    //数组往后滚动
                }
                printf("%d\n",r[len2]);         //最大的字符串长度值是最后的元素值
        }
}