介绍
最长公共子序列（Longest Common Subsequence LCS）是从给定的两个序列X和Y中取出尽可能多的一部分字符，按照它们在原序列排列的先后次序排列得到。LCS问题的算法用途广泛，如在软件不同版本的管理中，用LCS算法找到新旧版本的异同处;在软件测试中，用LCS算法对录制和回放的序列进行比较，在基因工程领域，用LCS算法检查患者DNA连与键康DNA链的异同;在防抄袭系统中，用LCS算法检查论文的抄袭率。LCS算法也可以用于程序代码相似度度量，人体运行的序列检索，视频段匹配等方面，所以对LCS算法进行研究具有很高的应用价值。
基本概念
子序列(subsequence)： 一个特定序列的子序列就是将给定序列中零个或多个元素去掉后得到的结果(不改变元素间相对次序)。例如序列<A,B,C,B,D,A,B>的子序列有：<A,B>、<B,C,A>、<A,B,C,D,A>等。
公共子序列(common subsequence)： 给定序列X和Y，序列Z是X的子序列，也是Y的子序列，则Z是X和Y的公共子序列。例如X=[A,B,C,B,D,A,B]，Y=[B,D,C,A,B,A[，那么序列Z=[B,C,A]为X和Y的公共子序列，其长度为3。但Z不是X和Y的最长公共子序列，而序列[B,C,B,A]和[B,D,A,B]也均为X和Y的最长公共子序列，长度为4，而X和Y不存在长度大于等于5的公共子序列。对于序列[A,B,C]和序列[E,F,G]的公共子序列只有空序列[]。
最长公共子序列：给定序列X和Y，从它们的所有公共子序列中选出长度最长的那一个或几个。
子串： 将一个序列从最前或最后或同时删掉零个或几个字符构成的新系列。区别与子序列，子序列是可以从中间抠掉字符的。cnblogs这个字符串中子序列有多少个呢？很显然有27个，比如其中的cb,cgs等等都是其子序列
给一个图再解释一下：
我们可以看出子序列不见得一定是连续的，连续的是子串。
问题分析
我们还是从一个矩阵开始分析,自己推导出状态迁移方程。
首先，我们把问题转换成前端够为熟悉的概念，不要序列序列地叫了，可以认为是数组或字符串。一切从简，我们就估且认定是两个字符串做比较吧。
我们重点留意”子序列“的概念，它可以删掉多个或零个，也可以全部干掉。这时我们的第一个子序列为 空字符串 （如果我们的序列不是字符串，我们还可以 ）！这个真是千万要注意到！许多人就是看不懂《算法导论》的那个图表，还有许多博客的作者不懂装懂。我们总是从左到右比较，当然了第一个字符串，由于作为矩阵的高，就垂直放置了。