Common Subsequence LCS最长公共子序列

这题也算是动态规划里比较经典的题了，不会这道题的时候呢，我去看了麻省理工的公开课，就是讲LCS的，当然啦，是在网上看的。但是没怎么看懂，就前面一会儿还可以理解的后来就有些跟不上思路了。不知道是我太傻还是语言不通，难理解，虽然有字幕。这里有链接，感兴趣的朋友可以也点开看看--麻省理工公开课。纠结了一下下，还是先上题目吧。

A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = <x1, x2, ..., xm> another sequence Z = <z1, z2, ..., zk> is a subsequence of X if there exists a strictly increasing sequence <i1, i2, ..., ik> of indices of X such that for all j = 1,2,...,k, xij = zj. For example, Z = <a, b, f, c> is a subsequence of X = <a, b, c, f, b, c> with index sequence <1, 2, 4, 6>. Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y. 

The program input is from a text file. Each data set in the file contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct. For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line. 

Input

abcfbc abfcab
programming contest 
abcd mnp
           

Output

4
2
0
           

Sample Input

abcfbc abfcab
programming contest 
abcd mnp
           

Sample Output

4
2
0
           

题目都是英文，感觉也不是太清晰，反正我是觉得不清晰...英语菜还偏偏要做题/(ㄒoㄒ)/~~菜哭。首先呢，感谢一下这位大牛，看了他的博客我才恍然大悟的。我写的只是小小的阐述而已。

最长公共子序列（longest common sequence）和最长公共子串（longest common substring）不是一回事儿。什么是子序列呢？即一个给定的序列的子序列，就是将给定序列中零个或多个元素去掉之后得到的结果。什么是子串呢？给定串中任意个连续的字符组成的子序列称为该串的子串。

上面这句带下划线的字体呢，就是上面提到的大牛的一句原话，说白了意思就是子序列呢可以不是连续的，但是字串必须是连续的，这就是子序列和子串的区别了。

这题用枚举的方法的确是可以做，但是时间复杂度是O(n*2^m),很可怕，是指数阶的。所以就自然要用算法来进行优化。动态规划，在我眼里，就是状态的递加，意思就是某个状态是直接由上一个状态经过简单的处理形成的，当然了上一状态是需要固定不变的。这样，每次需要某个状态的时候，直接调用上一个状态在微处理就行了。我是这么理解的，如果有那个地方理解不对的，欢迎各位大佬提出。

                      ------Count[i-1,j-1]+1 ,;if ai==bi;

Count[i,j]-----                                                                             (lll￢ω￢)原谅我不会画大括号

                      ------Max(Count[i-1,j],count[I,j-1]);

上面的就是状态转移的方程，也把这一部分的代码贴过来好了

la=strlen(a);
        lb=strlen(b);
        for(int i=1;i<=la;i++){
            for(int j=1;j<=lb;j++){
                if(a[i-1]==b[j-1]) count[i][j]=count[i-1][j-1]+1;
                else {
                    count[i][j]=max(count[i-1][j],count[i][j-1]);
                }
            }
        }
           

注意了，下面的LCS都表示的是两串字符串的公共最长子序列的长度。

a0...i的意思是字符串a0,a1,a2,,,,,,,,,ai。

小小的解释一下，如果ai和bj是一样的，那么此时LCS的长度就是a0...i-1和b0...j-1之前的那一串的字符的LCS加上1。

如果不一样，此时的LCS就是①和②的最大值。。；

①：表示a0...i去掉ai(就是a0...i-1)和b0...i的LCS

②：表示a0...i和b0...i再去掉bi(即b0...i-1);

这些搞懂了的话，这题就ac了。最后附上完整代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
using  namespace std;
int count[2001][2001];
int la,lb;
char a[2001],b[2001];
int main()
{
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(count,0,sizeof(count));
    while(~scanf("%s%s",a,b)){
        la=strlen(a);
        lb=strlen(b);
        for(int i=1;i<=la;i++){
            for(int j=1;j<=lb;j++){
                if(a[i-1]==b[j-1]) count[i][j]=count[i-1][j-1]+1;
                else {
                    count[i][j]=max(count[i-1][j],count[i][j-1]);
                }
            }
        }
        printf("%d\n",count[la][lb]);
    }
    return 0;
}