0011算法笔记——【动态规划】最长公共子序列问题(LCS)

最长公共子序列（LCS）问题（非连续子序列）的两种解法最长公共子序列也称作最长公共子串，英文缩写是LCS（Longest Common Subsequence）。

其定义是：一个序列S，如果分别是两个或多个已知序列的子序列，且是符合此条件的子序列中最长的，则称S为已知序列的最长公共子序列。

关于子序列的定义通常有两种方式，一种是对子序列没有连续的要求，其子序列的定义就是原序列中删除若干元素后得到的序列。

另一种是对子序列有连续的要求，其子序列的定义是原序列中连续出现的若干个元素组成的序列。

求解子序列是非连续的最长公共子序列问题是一个十分实用的问题，它可以描述两段文字之间的“相似度”，即它们的雷同程度，从而能够用来辨别抄袭。

本文将介绍对子序列没有连续性要求的情况下如何用计算机解决最长公共子序列问题，对子序列有连续性要求的情况下如何用计算机解决最长公共子序列问题将在后续的文章中介绍。

一、动态规划法（Dynamic Programming）最长公共子序列问题应该是属于多阶段决策问题中求最优解一类的问题，凡此类问题在编制计算机程序时应优先考虑动态规划法，如果不能用动态规划法，而且也找不到其它解决方法，还可以考虑穷举法。

对于这个问题，只要能找到描述最长公共子序列的最优子结构和最优解的堆叠方式，并且保证最优子结构中的每一次最优决策都满足“无后效性”，就可以考虑用动态规划法。

使用动态规划法的关键是对问题进行分解，按照一定的规律分解成子问题（分解后的子问题还可以再分解，这是个递归的过程），通过对子问题的定义找出最优子结构中最优决策序列（对于子问题就是最有决策序列的子序列）以及最优决策序列子序列的递推关系（当然还包括递推关系的边界值）。

如果一个给定序列的子序列是在该序列中删去若干元素后得到的序列，也就意味着子序列在原序列中的位置索引（下标）保持严格递增的顺序。

例如,序列S = <B,C,D,B>是序列K = <A，B，C，B，D，A，B>的一个子序列（非连续），序列S的元素在在K中的位置索引I = [2,3,5,7]，I是一个严格递增序列。

公共子序列问题徐康123183一．算法设计假设有两个序列X和Y，假设X和Y分别有m和n个元素，则建立一个二维数组C[(m+1)*(n+1)]，记录X i与Y j的LCS的长度。

将C[i,j]分为三种情况：若i =0 或j =0时，C[i,j]=0；若i,j>0且X[i]=Y[j]，C[i,j]=C[i-1,j-1]+1；若i,j>0且X[i] Y[j],C[i,j]=max{C[i-1,j],C[i,j-1]}。

再使用一个m*n的二维数组b，b[i,j]记录C[i,j]的来向:若X[i]=Y[j]，则B[i,j]中记入“↖”，记此时b[i,j] = 1；若X[i] Y[j]且C[i-1,j] > C[i,j-1]，则b[i,j]中记入“↑”，记此时B[i,j] = 2；若X[i] Y[j]且C[i-1,j] < C[i,j-1]，则b[i,j]中记入“←”，记此时B[i,j] = 3；若X[i]Y[j]且C[i-1,j] = C[i,j-1]，则b[i,j]中记入“↑”或“←”，记此时B[i,j] = 4；得到了两个数组C[]和B[]，设计递归输出LCS(X,Y)的算法：LCS_Output(Direction[][], X[], i, j, len,LCS[]){If i=0 or j=0 将LCS[]保存至集合LCS_SET中then return;If b[i,j]=1 then /*X[i]=Y[j]*/{LCS_Output(b,X,i-1,j-1)；将X[i]保存至LCS[len-i]；}else if b[i,j]=2 then /*X[i]Y[j]且C[i-1,j]>C[i,j-1]*/LCS_Output(b,X,i-1,j)else if b[i,j]=3 then /*X[i]Y[j]且C[i-1,j]<C[i,j-1]*/ LCS_Output(b,X,i,j-1)else if b[i,j]=4 then /*X[i]Y[j]且C[i-1,j]=C[i,j-1]*/LCS_Output(b,X,i-1,j)LCS_Output(b,X,i,j-1)}二．算法时间复杂度分析由上述对算法的分析得知，求辅助数组C 和B 所消耗的时间复杂度为O （mn ），而查找所有的公共子序列的时间复杂度取决于所遍历的路径，而路径是由算法递归的方向决定的。

最长公共子序列算法最长公共子序列算法概述最长公共子序列（Longest Common Subsequence，LCS）是一种常见的字符串匹配问题。

给定两个字符串S和T，求它们的最长公共子序列，即在S和T中都出现的最长的子序列。

该问题可以用动态规划算法解决。

算法原理动态规划算法是一种将复杂问题分解成更小的子问题来解决的方法。

在LCS算法中，我们将两个字符串S和T分别看作X和Y，并定义一个二维数组c[i][j]表示X[1..i]和Y[1..j]的LCS长度。

则有以下递推公式：c[i][j] = 0, if i=0 or j=0c[i][j] = c[i-1][j-1]+1, if X[i]=Y[j]c[i][j] = max(c[i-1][j], c[i][j-1]), if X[i]!=Y[j]其中第一行和第一列均初始化为0，因为空字符串与任何字符串的LCS长度均为0。

当X[i]=Y[j]时，说明当前字符相同，那么当前字符可以加入到LCS中，所以LCS长度加1；否则当前字符不能加入到LCS中，则需要从上一个状态继承得到当前状态。

最终结果即为c[m][n]，其中m和n分别表示X和Y的长度。

算法实现以下是LCS算法的Python实现：def lcs(X, Y):m = len(X)n = len(Y)c = [[0] * (n+1) for i in range(m+1)]for i in range(1, m+1):for j in range(1, n+1):if X[i-1] == Y[j-1]:c[i][j] = c[i-1][j-1] + 1else:c[i][j] = max(c[i-1][j], c[i][j-1])return c[m][n]其中X和Y分别为两个字符串。

算法优化以上算法的时间复杂度为O(mn)，其中m和n分别表示X和Y的长度。

如果X和Y较长，算法会很慢。

但是我们可以通过一些优化来降低时间复杂度。

[DataStructure]LCSs——最长公共⼦序列和最长公共⼦串1. 什么是 LCSs？ 什么是 LCSs? 好多博友看到这⼏个字母可能⽐较困惑，因为这是我⾃⼰对两个常见问题的统称，它们分别为最长公共⼦序列问题（Longest-Common-Subsequence）和最长公共⼦串（Longest-Common-Substring）问题。

这两个问题⾮常的相似，所以对不熟悉的同学来说，有时候很容易被混淆。

下⾯让我们去好好地理解⼀下两者的区别吧。

1.1 ⼦序列 vs ⼦串 ⼦序列是有序的，但不⼀定是连续，作⽤对象是序列。

例如：序列 X = <B, C, D, B> 是序列 Y = <A, B, C, B, D, A, B> 的⼦序列，对应的下标序列为 <2, 3, 5, 7>。

⼦串是有序且连续的，左右对象是字符串。

例如 a = abcd 是 c = aaabcdddd 的⼀个⼦串；但是 b = acdddd 就不是 c 的⼦串。

1.2 最长公共⼦序列 vs 最长公共⼦串 最长公共⼦序列和最长公共⼦串是常见的两种问题，虽然两者问题很相似，也均可以根据动态规划进⾏求解，但是两者的本质是不同的。

最长公共⼦序列问题是针对给出的两个序列，求两个序列最长的公共⼦序列。

最长公共⼦串问题是针对给出的两个字符串，求两个字符串最长的公共⼦串（有关字符串匹配相关算法可以转⾄博客《》）。

2. 动态规划⽅法求解LCSs 前⾯提到，动态规划⽅法均可以⽤到最长公共⼦序列和最长公共⼦串问题当中，在这⾥我们就不⼀⼀进⾏求解了。

我们以最长公共⼦序列为例，介绍⼀下如何利⽤动态规划的思想来解决 LCSs。

给定两个序列，找出在两个序列中同时出现的最长⼦序列的长度。

对于每⼀个序列⽽⾔，其均具有a m中⼦序列，因此采⽤暴⼒算法的时间复杂度是指数级的，这显然不是⼀种好的解决⽅案。

下⾯我们看⼀下，如何使⽤动态规划的思想来解决最⼤公共⼦序列问题。

最长公共子序列lcs算法最长公共子序列（Longest Common Subsequence，简称LCS）算法是一种常用的字符串匹配算法，用于在两个字符串中找到最长的公共子序列。

在计算机科学领域，字符串匹配是一项基础性的任务，常用于文本比较、版本控制、DNA序列比对等领域。

LCS算法的基本思想是通过动态规划的方式，从头开始比较两个字符串的每个字符，逐步构建一个二维数组来保存公共子序列的长度。

具体步骤如下：1. 创建一个二维数组dp，大小为两个字符串长度加1。

dp[i][j]表示字符串1的前i个字符和字符串2的前j个字符的最长公共子序列的长度。

2. 初始化dp数组的第一行和第一列，即dp[0][j]和dp[i][0]都为0，表示一个空字符串与任何字符串的最长公共子序列长度都为0。

3. 从字符串的第一个字符开始，逐行逐列地比较两个字符串的字符。

如果两个字符相等，则说明这个字符属于最长公共子序列，将dp[i][j]的值设置为dp[i-1][j-1]+1。

如果两个字符不相等，则说明这个字符不属于最长公共子序列，取dp[i-1][j]和dp[i][j-1]中的较大值来更新dp[i][j]的值。

4. 最后，dp[m][n]即为两个字符串的最长公共子序列的长度，其中m和n分别为两个字符串的长度。

接下来，我们通过一个例子来演示LCS算法的具体过程。

假设有两个字符串str1="ABCDAB"和str2="BDCABA"，我们要找出这两个字符串的最长公共子序列。

创建一个二维数组dp，大小为(str1.length()+1)×(str2.length()+1)。

初始化dp数组的第一行和第一列为0。

```B DC A B AA 0 0 0 0 0 0B 0C 0D 0A 0B 0```从第一个字符开始比较，我们发现str1[1]和str2[1]都是B，因此dp[1][1]=dp[0][0]+1=1。

2.3最长公共子序列问题和前面讲的有所区别，这个问题的不涉及走向。

很经典的动态规划问题。

例题16最长公共子序列(lcs.pas/c/cpp)【问题描述】一个给定序列的子序列是在该序列中删去若干元素后得到的序列。

确切地说，若给定序列X= < x1, x2,…, xm>，则另一序列Z= < z1, z2,…, zk>是X的子序列是指存在一个严格递增的下标序列< i1, i2,…, ik>，使得对于所有j=1,2,…,k有Xij=Zj例如，序列Z=是序列X=的子序列，相应的递增下标序列为<2,3,5,7>。

给定两个序列X 和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。

例如，若X= < A, B, C, B, D, A, B>和Y= < B, D, C, A, B, A>，则序列是X和Y的一个公共子序列，序列也是X和Y的一个公共子序列。

而且，后者是X和Y的一个最长公共子序列，因为X和Y没有长度大于4的公共子序列。

给定两个序列X= < x1, x2, …, xm>和Y= < y1, y2, … , yn>，要求找出X和Y的一个最长公共子序列。

【输入文件】输入文件共有两行，每行为一个由大写字母构成的长度不超过200的字符串，表示序列X和Y。

【输出文件】输出文件第一行为一个非负整数，表示所求得的最长公共子序列的长度，若不存在公共子序列，则输出文件仅有一行输出一个整数0，否则在输出文件的第二行输出所求得的最长公共子序列(也用一个大写字母组成的字符串表示。

【输入样例】ABCBDABBDCBA【输出样例】4BCBA【问题分析】这个问题也是相当经典的。

这个题目的阶段很不明显，所以初看这个题目没什么头绪，不像前面讲的有很明显的上一步，上一层之类的东西，只是两个字符串而且互相没什么关联。

但仔细分析发现还是有入手点的：既然说是动态规划，那我们首先要考虑的就是怎么划分子问题，一般对于前面讲到的街道问题和数塔问题涉及走向的，考虑子问题时当然是想上一步是什么？但这个问题没有涉及走向，也没有所谓的上一步，该怎么办呢？既然是求公共子序列，也就有第一个序列的第i个字符和第二个序列的第j个字符相等的情况。

最长公共子序列问题LCS问题描述一个给定序列的子序列是在该序列中删去若干元素后得到的序列。

确切地说，若给定序列X=<x1, x2,…, x m>，则另一序列Z=<z1, z2,…, z k>是X的子序列是指存在一个严格递增的下标序列<i1, i2,…, i k>，使得对于所有j=1,2,…,k有例如，序列Z=<B,C,D,B>是序列X=<A,B,C,B,D,A,B>的子序列，相应的递增下标序列为<2,3,5,7>。

给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。

例如，若X=<A, B, C, B, D, A, B>和Y=<B, D, C, A, B, A>，则序列<B, C, A>是X和Y的一个公共子序列，序列<B, C, B, A>也是X和Y的一个公共子序列。

而且，后者是X和Y的一个最长公共子序列，因为X和Y没有长度大于4的公共子序列。

最长公共子序列(LCS)问题：给定两个序列X=<x1, x2, …, x m>和Y=<y1, y2, … , y n>，要求找出X和Y的一个最长公共子序列。

参考解答动态规划算法可有效地解此问题。

下面我们按照动态规划算法设计的各个步骤来设计一个解此问题的有效算法。

1.最长公共子序列的结构解最长公共子序列问题时最容易想到的算法是穷举搜索法，即对X的每一个子序列，检查它是否也是Y的子序列，从而确定它是否为X和Y的公共子序列，并且在检查过程中选出最长的公共子序列。

X的所有子序列都检查过后即可求出X和Y的最长公共子序列。

X 的一个子序列相应于下标序列{1, 2, …, m}的一个子序列，因此，X共有2m个不同子序列，从而穷举搜索法需要指数时间。

事实上，最长公共子序列问题也有最优子结构性质，因为我们有如下定理：定理: LCS的最优子结构性质设序列X=<x1, x2, …, x m>和Y=<y1, y2, …, y n>的一个最长公共子序列Z=<z1, z2, …,z k>，则：1.若x m=y n，则z k=x m=y n且Z k-1是X m-1和Y n-1的最长公共子序列；2.若x m≠y n且z k≠x m ，则Z是X m-1和Y的最长公共子序列；3.若x m≠y n且z k≠y n，则Z是X和Y n-1的最长公共子序列。

最长公共子序列（LCS）是一种经典的字符串算法，用于找到两个字符串中最长的共同子序列。

在实际应用中，LCS算法被广泛用于文本相似度比较、版本控制系统、生物信息学等领域。

在本文中，我们将探讨LCS算法的空间复杂度优化，通过深入分析和讨论，帮助你更好地理解这一优化策略。

1. LCS算法概述LCS算法是一种动态规划算法，通过填表格的方式，将两个字符串的比对过程可视化，最终找到它们的最长公共子序列。

在最简单的情况下，LCS算法的时间复杂度为O(n*m)，其中n和m分别为两个字符串的长度。

但是，在实际应用中，我们通常不仅关注算法的时间复杂度，还需要考虑空间复杂度的优化。

2. 实现原理在传统的LCS算法中，我们通常使用一个二维数组来保存中间状态，以便回溯最长公共子序列。

然而，这种做法在空间上会占用较多的内存，尤其是当输入字符串较长时。

为了优化空间复杂度，我们可以采用一维数组来存储中间状态，从而减少内存的占用。

3. 空间复杂度优化具体来说，我们可以利用滚动数组的思想，只使用两个一维数组来交替保存当前行和上一行的状态。

这样做的好处是，我们可以不断地更新这两个数组，而不需要保存整个二维表格，从而减少了空间的占用。

通过这种优化策略，我们可以将空间复杂度降低到O(min(n, m))，显著减少了内存的使用。

4. 示例分析让我们通过一个简单的示例来说明空间复杂度优化的过程。

假设有两个字符串"ABCD"和"BACDB"，我们希望找到它们的最长公共子序列。

在传统的LCS算法中，我们需要使用一个二维数组来保存中间状态，而在空间复杂度优化后，我们只需要使用两个一维数组来交替保存状态。

通过这种优化，我们可以用较少的内存来解决相同的问题。

5. 个人观点空间复杂度优化是算法设计中非常重要的一环，尤其在处理大规模数据时尤为重要。

通过优化空间复杂度，我们可以节省内存的使用，提高算法的效率，同时也更好地适应了现代计算机的内存限制。

动态规划（最长公共⼦序列）有⼀个经典问题：长度为n的序列，插⼊若⼲数字后，让其形成回⽂串。

求插⼊的数字最少的个数pp=n-最长公共⼦序列最长公共⼦序列可以利⽤动态规划的思想，具体可以⽤下⾯这个图来表⽰：//求最长公共⼦序列for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(s[i]==s[n-j+1])//正串和逆序串dp[i][j]=dp[i-1][j-1]+1;elsedp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}将序列打印出来#include<iostream>#include<cstdio>#include<string>using namespace std;int dp[100][100];int main(){//防⽌数组越界，添加⼀下前导符string s="0BDCABA";string t="1ABCBDAB";int len1=s.length();int len2=t.length();for(int i=1;i<len1;i++){for(int j=1;j<len2;j++){if(s[i]==t[j])dp[i][j]=dp[i-1][j-1]+1;elsedp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}cout<<dp[len1-1][len2-1]<<endl;int p=len1-1,q=len2-1;while(p>=1&&q>=1){if(s[p]==t[q]){cout<<s[p]<<"";p-=1;q-=1;}else if(dp[p-1][q]>=dp[p][q-1]){p-=1;}elseq-=1;}}。

利用动态规划算法解决最长公共子序列问题摘要：算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。

或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。

其中动态规划是一种有效的解决问题的算法。

此论文将围绕如何利用动态规划算法解决最长公共子序列问题展开。

关键词：算法，动态规划，最长公共子序列。

Abstract: Algorithm can be understood as a basic computing and the provisions of the order of operations that form a complete solving steps. Or as according to the request and design of the exact calculation of good limited sequence, and the steps and can solve problem of sequence. Among them the dynamic planning is a kind of effective problem solving algorithm. This paper will focus on how to use dynamic programming algorithm is presented to solve the longest public son on sequence. Keywords:algorithm, the dynamic programming, the longest public son sequence.1 引言动态规划算法是一种有效的解决问题的算法。

通常将待求解问题分解成若干个子问题，利用这一特性，可以解决很多能够以大化小的问题，如：矩阵连成问题、求最长公共子序列、求凸多边形最优三角剖分、图像压缩、电路布线、流水作业调度等。

最长公共子序列问题；最长公共子序列（Longest Common Subsequence, LCS）问题是指找到多个字符串中最长的公共子序列。

公共子序列是指这些字符串在所有字符串中都以相同的顺序出现，但不要求连续。

例如，对于字符串"ABCD"和"ACDF"，其最长公共子序列为"ACD"。

最长公共子序列问题可以通过动态规划来解决。

基本思路是使用一个二维数组dp，其中dp[i][j]表示字符串A的前i个字符和字符串B的前j个字符的最长公共子序列的长度。

首先，初始化dp[0][j]和dp[i][0]为0，表示空字符串与任何字符串的最长公共子序列长度为0。

然后，对于每个字符A[i]和B[j]，如果A[i]等于B[j]，则dp[i][j] = dp[i-1][j-1] + 1，表示在之前的最长公共子序列长度的基础上加1。

否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])，表示要么在字符串A的前i-1个字符和字符串B的前j个字符的最长公共子序列的基础上取得，要么在字符串A的前i个字符和字符串B的前j-1个字符的最长公共子序列的基础上取得。

最终，dp[m][n]即为所求，其中m和n分别为字符串A和字符串B的长度。

可以通过追踪dp数组来还原出最长公共子序列，具体方法是从dp[m][n]开始，如果A[i]等于B[j]，则该字符是公共字符，将其加入结果序列，然后向左上方移动，即dp[i-1][j-1]。

如果dp[i][j]等于dp[i-1][j]，则说明最长公共子序列在A中取得，向上移动，即dp[i-1][j]；如果dp[i][j]等于dp[i][j-1]，则说明最长公共子序列在B中取得，向左移动，即dp[i][j-1]。

重复上述过程，直到dp[i][j]为0。

LCS（最长公共⼦序列）动规算法正确性证明今天在看代码源⽂件求diff的原理的时候看到了LCS算法。

这个算法应该不陌⽣，动规的经典算法。

具体算法做啥了我就不说了，不知道的可以直接看《算法导论》动态规划那⼀章。

既然看到了就想回忆下，当想到算法正确性的时候，发现这个算法的正确性证明并不好做。

于是想了⼀段时间，⾥⾯有⼏个细节很trick，容易陷进去。

想了⼏轮，现在把证明贴出来，有异议的可以留⾔⼀起交流。

先把⼀些符号和约定说明下：假设有两个数组，A和B。

A[i]为A的第i个元素，A(i)为由A的第⼀个元素到第i个元素所组成的前缀。

m(i, j)为A(i)和B(j)的最长公共⼦序列长度。

由于算法本⾝的递推性质，其实只要证明，对于某个i和j：m(i, j) = m(i-1, j-1) + 1 （当A[i] = B[j]时）m(i, j) = max( m(i-1, j), m(i, j-1) ) （当A[i] != B[j]时）第⼀个式⼦很好证明，即当A[i] = B[j]时。

可以⽤反证，假设m(i, j) > m(i-1, j-1) + 1 （m(i, j)不可能⼩于m(i-1, j-1) + 1，原因很明显），那么可以推出m(i-1, j-1)不是最长的这⼀⽭盾结果。

第⼆个有些trick。

当A[i] != B[j]时，还是反证，假设m(i, j) > max( m(i-1, j), m(i, j-1) )。

由反证假设，可得m(i, j) > m(i-1, j)。

这个可以推出A[i]⼀定在m(i, j)对应的LCS序列中（反证可得）。

⽽由于A[i] != B[j]，故B[j]⼀定不在m(i, j)对应的LCS序列中。

所以可推出m(i, j) = m(i, j-1)。

这就推出了与反正假设⽭盾的结果。

得证。

动态规划经典——最长公共⼦序列问题（LCS）和最长公共⼦串问题⼀.最长公共⼦序列问题(LCS问题)给定两个字符串A和B，长度分别为m和n，要求找出它们最长的公共⼦序列，并返回其长度。

例如： A = "Hel lo W o rld" B = "loo p"则A与B的最长公共⼦序列为 "loo",返回的长度为3。

此处只给出动态规划的解法：定义⼦问题dp[i][j]为字符串A的第⼀个字符到第 i 个字符串和字符串B 的第⼀个字符到第 j 个字符的最长公共⼦序列，如A为“app”,B为“apple”，dp[2][3]表⽰ “ap” 和 “app” 的最长公共字串。

注意到代码中 dp 的⼤⼩为 (n + 1) x (m + 1) ，这多出来的⼀⾏和⼀列是第 0 ⾏和第 0 列，初始化为 0，表⽰空字符串和另⼀字符串的⼦串的最长公共⼦序列，例如dp[0][3]表⽰ "" 和“app” 的最长公共⼦串。

当我们要求dp[i][j]，我们要先判断A的第i个元素B的第j个元素是否相同即判断A[i - 1]和 B[j -1]是否相同，如果相同它就是dp[i-1][j-1]+ 1，相当于在两个字符串都去掉⼀个字符时的最长公共⼦序列再加 1；否则最长公共⼦序列取dp[i][j - 1] 和dp[i - 1][j]中⼤者。

所以整个问题的初始状态为：dp[i][0]=0,dp[0][j]=0相应的状态转移⽅程为：dp[i][j]=max{dp[i−1][j],dp[i][j−1]},A[i−1]!=B[j−1] dp[i−1][j−1]+1,A[i−1]==B[j−1]代码的实现如下：class LCS{public:int findLCS(string A, int n, string B, int m){if(n == 0 || m == 0)//特殊输⼊return 0;int dp[n + 1][m + 1];//定义状态数组for(int i = 0 ; i <= n; i++)//初始状态dp[i][0] = 0;for(int i = 0; i <= m; i++)dp[0][i] = 0;for(int i = 1; i <= n; i++)for(int j = 1; j<= m; j++){if(A[i - 1] == B[j - 1])//判断A的第i个字符和B的第j个字符是否相同dp[i][j] = dp[i -1][j - 1] + 1;elsedp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);}return dp[n][m];//最终的返回结果就是dp[n][m]}};该算法的时间复杂度为O(n*m)，空间复杂度为O(n*m)。

求解所有最长公共子序列一、问题分析该部分思路同课件二、算法设计思路根据问题分析的结果，具体的算法设计思路如下：1)申明两个数组，用于保存比较的两个字符串；由于事先不知字符串大小，故动态的实现，这里用C++的容器。

2)申明全局变量，二维数组B和数组C。

数组C用于保存计算Xi和Yi的LCS值；数组B保存当前的C是从哪个子问题得来的。

为此，定义一个枚举类型，用于标识不同的方向，分别为对角线、向上、向左和向左向上四个方向。

3)根据动态规划，实现一个函数LCS_LENGTH，完成的功能是计算数组B和C。

具体过程是：先是动态申请二维数组B和C，他们的行列长度都增加1，目的就是方便计算。

将C的第0行和第0列都赋上0，即初始化。

开始计算C[i][j]，以行为主，一次计算C的每一个元素，即将两个数组逐一比较。

比较时就有两种情况，分别是若相等时，就将C[i][j]设置成C[i-1][j-1]，同时将B[i][j]设置成DIAGONAL。

若不相等时，比较C[i-1][j] 和C[i][j-1]的值，又有三种情况：一是C[i-1][j] 与C[i][j-1]相等，就随便把某一个赋给C[i][j]，比如C[i-1][j]，B[i][j]设置为UP_LEFT；二是若C[i-1][j] 大于C[i][j-1]，则将C[i-1][j]赋给C[i][j]，并且将B[i][j]设置成UP；最后是若C[i-1][j] 小于C[i][j-1]，则将C[i][j-1]赋给C[i][j]，并且将B[i][j]设置成LEFT。

4)根据第3）步骤的结果，就可以找出所有LCS了。

这里会用到回溯方法，具体实现可以用栈，也可以用递归。

本人使用的是递归，代码简单、易懂。

具体实现方法是：申请一个数组用于保存一个LCS，这个数组会反复使用，因此，一旦找到一个就会立即将它输出。

再设置一个变量curpos标识当前的数组下标，一个变量len 保存当前LCS数组的元素个数。

动态规划解最长公共子序列问题动态规划主要针对最优化问题,它的决策是全面考虑不同的情况分别进行决策,,最后通过多阶段决策逐步找出问题的最终解.当各个阶段采取决策后,会不断决策出新的数据,直到找到最优解.每次决策依赖于当前状态,又随机引起状态的转移.一个决策序列就是在变化的状态中产生出来的,故有”动态”的含义.所以,这种多阶段最优化决策解决问题的过程称为动态规划.一问题的描述与分析字符序列的子序列是指从给定字符序列中随意地(不一定连续)去掉若干字符(可能一个也不去掉)后形成的字符序列..令给定的字符序列X=”x0,x1,x2,…xm-1”,序列Y=”y0,y1,…yk-1”是X的子序列，存在X的一个严格递增下标序列i=i0,i1,i2,…ik-1,使得对所有的j=0,1,2,…k-1,有xi=yi。

例如X=“ABCBDAB”,Y=“BCDB”是X的一个子序列。

给定两个序列A和B,称序列Z是A和B公共子序列，是指Z同是A和B的子序列。

求最长公共子序列。

若A的长度为m,B的长度为n,则A的子序列有2*m-1个，B的子序列有2*n-1个。

采用枚举法分别对A和B的所以子序列一一检查，最终求出最长公共子序列。

如此比较次数（2*2n）接近指数阶，当n较大时，算法太耗时，不可取。

所以要全面考虑不同的情况分别进行决策,,最后通过多阶段决策逐步找出问题的最终解.当各个阶段采取决策后,会不断决策出新的数据,直到找到最优解。

二、算法设计（或算法步骤）A=”a0,a1,a2,……am-1”,B=”b0,b1,b2,……bn-1”,且Z=”z0,z1,z2……zk-1”,为她们的最长公共子序列。

不难证明有一下结论：（1）如果am-1=bn-1,则zk-1=am-1=bn-1,且“z0,z1,z2,……zk-2”是“a0,a1,a2,……am-2”和“b0,b1,b2,……bn-2”的一个最长公共子序列；（2）如果am-1!=bn-1,则若zk-1!=am-1,则“z0,z1,z2,……zk-1”是“a0,a1,a2,……am-2”和”b0,b1,b2,……bn-1”的一个最长公共子序列。

程序员编程艺术第十一章：最长公共子序列(LCS)问题0、前言程序员编程艺术系列重新开始创作了（前十章，请参考程序员编程艺术第一~十章集锦与总结）。

回顾之前的前十章，有些代码是值得商榷的，因当时的代码只顾阐述算法的原理或思想，所以，很多的与代码规范相关的问题都未能做到完美。

日后，会着力修缮之。

搜遍网上，讲解这个LCS问题的文章不计其数，但大多给读者一种并不友好的感觉，稍感晦涩，且代码也不够清晰。

本文力图避免此些情况。

力保通俗，阐述详尽。

同时，经典算法研究系列的第三章（三、dynamic programming）也论述了此LCS问题。

有任何问题，欢迎不吝赐教。

第一节、问题描述什么是最长公共子序列呢好比一个数列S，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则S称为已知序列的最长公共子序列。

举个例子，如：有两条随机序列，如 1 3 4 5 5 ，and 2 4 5 5 7 6，则它们的最长公共子序列便是：4 5 5。

注意最长公共子串（Longest CommonSubstring）和最长公共子序列（LongestCommon Subsequence, LCS）的区别：子串（Substring）是串的一个连续的部分，子序列（Subsequence）则是从不改变序列的顺序，而从序列中去掉任意的元素而获得的新序列；更简略地说，前者（子串）的字符的位置必须连续，后者（子序列LCS）则不必。

比如字符串acdfg同akdfc 的最长公共子串为df，而他们的最长公共子序列是adf。

LCS可以使用动态规划法解决。

下文具体描述。

第二节、LCS问题的解决思路穷举法解最长公共子序列问题时最容易想到的算法是穷举搜索法，即对X的每一个子序列，检查它是否也是Y的子序列，从而确定它是否为X和Y的公共子序列，并且在检查过程中选出最长的公共子序列。

X和Y的所有子序列都检查过后即可求出X和Y的最长公共子序列。

X的一个子序列相应于下标序列{1, 2, …, m}的一个子序列，因此，X共有2m个不同子序列（Y亦如此，如为2^n），从而穷举搜索法需要指数时间（2^m * 2^n）。

的一个严格递增下标序列<i0，i1，…，ik-1>，使得对所有的j=0，1，…，k-1，有xij=yj。

例如，X=“ABCBDAB”，Y=“BCDB”是X的一个子序列。

考虑最长公共子序列问题如何分解成子问题，设A=“a0，a1，…，am-1”，B=“b0，b1，…，bm-1”，并Z=“z0，z1，…，zk-1”为它们的最长公共子序列。

不难证明有以下性质：（1）如果am-1=bn-1，则zk-1=am-1=bn-1，且“z0，z1，…，zk-2”是“a0，a1，…，am-2”和“b0，b1，…，bn-2”的一个最长公共子序列；（2）如果am-1!=bn-1，则若zk-1!=am-1，蕴涵“z0，z1，…，zk-1”是“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一个最长公共子序列；（3）如果am-1!=bn-1，则若zk-1!=bn-1，蕴涵“z0，z1，…，zk-1”是“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一个最长公共子序列。

这样，在找A和B的公共子序列时，如有am-1=bn-1，则进一步解决一个子问题，找“a0，a1，…，am-2”和“b0，b1，…，bm-2”的一个最长公共子序列；如果am-1!=bn-1，则要解决两个子问题，找出“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一个最长公共子序列和找出“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一个最长公共子序列，再取两者中较长者作为A和B的最长公共子序列。

求解：引进一个二维数组c[][]，用c[i][j]记录X[i]与Y[j] 的LCS 的长度，b[i][j]记录c[i][j]是通过哪一个子问题的值求得的，以决定搜索的方向。

我们是自底向上进行递推计算，那么在计算c[i,j]之前，c[i-1][j-1]，c[i-1][j]与c[i][j-1]均已计算出来。

此时我们根据X[i] = Y[j]还是X[i] != Y[j]，就可以计算出c[i][j]。

算法设计与分析动态规划——最长公共⼦序列LCS及模板摘⾃这位⼤佬写的对理解DP也很有帮助，我就直接摘抄过来了，代码部分来⾃我做过的题⼀，问题描述给定两个字符串，求解这两个字符串的最长公共⼦序列（Longest Common Sequence）。

⽐如字符串1：BDCABA；字符串2：ABCBDAB则这两个字符串的最长公共⼦序列长度为4，最长公共⼦序列是：BCBA⼆，算法求解这是⼀个动态规划的题⽬。

对于可⽤动态规划求解的问题，⼀般有两个特征：①最优⼦结构；②重叠⼦问题①最优⼦结构设 X=(x1,x2,.....xn) 和 Y={y1,y2,.....ym} 是两个序列，将 X 和 Y 的最长公共⼦序列记为LCS(X,Y)找出LCS(X,Y)就是⼀个最优化问题。

因为，我们需要找到X 和 Y中最长的那个公共⼦序列。

⽽要找X 和 Y的LCS，⾸先考虑X的最后⼀个元素和Y的最后⼀个元素。

1）如果 xn=ym，即X的最后⼀个元素与Y的最后⼀个元素相同，这说明该元素⼀定位于公共⼦序列中。

因此，现在只需要找：LCS(X n-，Y m-1)1LCS(X n-1，Y m-1)就是原问题的⼀个⼦问题。

为什么叫⼦问题？因为它的规模⽐原问题⼩。

（⼩⼀个元素也是⼩嘛....）为什么是最优的⼦问题？因为我们要找的是X n-1 和 Y m-1的最长公共⼦序列啊。

最长的换句话说，就是最优的那个。

（这⾥的最优就是最长的意思）2）如果xn != ym，这下要⿇烦⼀点，因为它产⽣了两个⼦问题：LCS(X n-1，Y m) 和 LCS(X n，Y m-1)因为序列X 和 序列Y 的最后⼀个元素不相等嘛，那说明最后⼀个元素不可能是最长公共⼦序列中的元素嘛。

（都不相等了，怎么公共嘛）。

LCS(X n-1，Y m)表⽰：最长公共序列可以在(x1,x2,....x(n-1)) 和 (y1,y2,...yn)中找。

LCS(X n，Y m-1)表⽰：最长公共序列可以在(x1,x2,....xn) 和 (y1,y2,...y(n-1))中找。

算法系列之六：最长公共子序列（LCS）问题（连续子序列）的三种解法最长公共子序列（LCS）问题有两种方式定义子序列，一种是子序列不要求不连续，一种是子序列必须连续。

上一章介绍了用两种算法解决子序列不要求连续的最终公共子序列问题，本章将介绍要求子序列必须是连续的情况下如何用算法解决最长公共子序列问题。

仍以上一章的两个字符串“abcdea”和“aebcda”为例，如果子序列不要求连续，其最长公共子序列为“abcda”，如果子序列要求是连续，则其最长公共子序列应为“bcd”。

在这种情况下，有可能两个字符串出现多个长度相同的公共子串，比如“askdfiryetd”和“trkdffirey”两个字符串就存在两个长度为3的公共子串，分别是“kdf”和“fir”，因此问题的性质发生了变化，需要找出两个字符串所有可能存在公共子串的情况，然后取最长的一个，如果有多个最长的公共子串，只取其中一个即可。

字符串“abcdea”和“aebcda”如果都以最左端的a字符对齐，则能够匹配的最长公共子串就是“a”。

但是如果用第二个字符串的e字符对齐第一个字符串的a 字符，则能够匹配的最长公共子串就是“bcd”。

可见，从两个字符串的不同位置开始对齐匹配，可以得到不同的结果，因此，本文采用的算法就是穷举两个字符串所有可能的对齐方式，对每种对齐方式进行字符的逐个匹配，找出最长的匹配子串。

一、递归方法首先看看递归方法。

递归的方法比较简单，就是比较两个字符串的首字符是否相等，如果相等则将其添加到已知的公共子串结尾，然后对两个字符串去掉首字符后剩下的子串继续递归匹配。

如果两个字符串的首字符不相等，则用三种对齐策略分别计算可能的最长公共子串，然后取最长的一个与当前已知的最长公共子串比较，如果比当前已知的最长公共子串长就用计算出的最长公共子串代替当前已知的最长公共子串。

第一种策略是将第一个字符串的首字符删除，将剩下的子串与第二个字符串继续匹配；第二种策略是将第二个字符串的首字符删除，将剩下的子串与第一个字符串继续匹配；第三种策略是将两个字符串的首字符都删除，然后继续匹配两个字符串剩下的子串。