最长公共子序列_动态规划

公共子序列问题徐康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 ），而查找所有的公共子序列的时间复杂度取决于所遍历的路径，而路径是由算法递归的方向决定的。

最长公共子序列GE GROUP system office room 【GEIHUA16H-GEIHUA GEIHUA8Q8-动态规划一、问题描述用动态规划法求两个字符串A=‘xzyzzyx’和B=‘zxyyzxz’的最长公共子序列二、算法分析(1)、若xm=yn,则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共自序列；(2)、若xm≠yn,且zk≠xm，则Zk是Xm-1和Yn的最长公共自序列；(3)、若xm≠yn,且zk≠yn，则Zk是Xm和Yn-1的最长公共自序列；设L(m,n)表示序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列的长度L表示已经决策的长度S表示每个决策的状态L(0,0)=L(0,j)=0 1≤i≤m, 1≤j≤nL(i-1,j-1)+1 xi=yi,i≥1,j≥1 L(i,j)=max{L(i,j-1),(L(i-1,j)} xi≠yi,i≥1,j≥1 1 xi=yiS(i,j)= 2 xi≠yi 且L(i,j-1)≥L(i-1,j)3 xi≠yi 且L(i,j-1)< L(i-1,j)长度矩阵L三、源代码#include <iostream>#include <string>using namespace std;int main(){string str1 = "xzyzzyx";string str2 = "zxyyzxz";int x_len = str1.length();int y_len = str2.length();int arr[50][50] ={{0,0}};int i = 0;int j = 0;for(i = 1; i <= x_len; i++){for(j = 1; j <= y_len; j++){if(str1[i - 1] == str2[j - 1]){arr[i][j] = arr[i - 1][j - 1] + 1;}else if(arr[i][j - 1] >= arr[i - 1][j]) arr[i][j] = arr[i][j - 1];elsearr[i][j] = arr[i -1][j];}}for(i = 0 ; i <= x_len; i++){for( j = 0; j <= y_len; j++){cout << arr[i][j] << " ";}cout << endl;}for(i = x_len, j = y_len; i >= 1 && j >= 1;) {if(str1[i - 1] == str2[j - 1]){cout << str1[i - 1] << " ";i--;j--;}else if(arr[i][j -1] > arr[i - 1][j]) j--;elsei--;}cout << endl;return 0;}。

动态规划（最长公共⼦序列）有⼀个经典问题：长度为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;}}。

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

确切地说，若给定序列X= { x1, x2,…, x m}，则另一序列Z= {z1, z2,…, z k}是X的子序列是指存在一个严格递增的下标序列{i1, i2,…, i k}，使得对于所有j=1,2,…,k有X ij=Z j。

例如，序列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的公共子序列。

给定两个序列X= {x1, x2, …, x m}和Y= {y1, y2, … , y n}，要求找出X和Y的一个最长公共子序列。

问题解析：设X= { A, B, C, B, D, A, B},Y= {B, D, C, A, B, A}。

求X，Y的最长公共子序列最容易想到的方法是穷举法。

对X的多有子序列，检查它是否也是Y的子序列，从而确定它是否为X和Y的公共子序列。

由集合的性质知，元素为m的集合共有2^m个不同子序列，因此，穷举法需要指数级别的运算时间。

进一步分解问题特性，最长公共子序列问题实际上具有最优子结构性质。

设序列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的最长公共子序列。

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

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

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

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

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

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 引言动态规划算法是一种有效的解决问题的算法。

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

公共解的三种解法
#### 1. 动态规划
使用动态规划的方法，可以把求解最大公共子序列问题转换为求解最长公共子序列问题。

动态规划的思路是：令dp[i][j]表示字符串A[0..i]和字符串B[0..j]的最长公共子序列的长度，则有状态转移方程：
```
dp[i][j] =
0 (i == 0 || j == 0)
dp[i-1][j-1] + 1 (A[i] == B[j])
max(dp[i-1][j], dp[i][j-1]) (A[i] != B[j])
```
最终结果为dp[n][m]，其中n为字符串A的长度，m为字符串B的长度。

#### 2. 递归
递归的思路是：令lcs(i, j)表示字符串A[0..i]和字符串B[0..j]的最长公共子序列的长度，则
有状态转移方程：
```
lcs(i, j) =
0 (i == 0 || j == 0)
lcs(i-1, j-1) + 1 (A[i] == B[j])
max(lcs(i-1, j), lcs(i, j-1)) (A[i] != B[j])
```
最终结果为lcs(n, m)，其中n为字符串A的长度，m为字符串B的长度。

#### 3. 滑动窗口
滑动窗口的思路是：定义两个指针i和j，分别指向字符串A和字符串B的开头，比较A[i]
和B[j]的值，如果相等，则将i和j同时向后移动，否则只有一个指针向后移动，直到两个
指针都到达字符串末尾。

最终结果为i和j指针移动的次数，即为最长公共子序列的长度。

动态规划经典——最长公共⼦序列问题（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)。

多个字符串的最长公共子序列（Longest Common Subsequence，LCS）是指这些字符串中最长的共同子序列。

与最长公共子串（Longest Common Substring）不同，最长公共子序列不要求连续性。

解决多个字符串的最长公共子序列问题可以采用动态规划的方法。

对于两个字符串的情况，可以构建一个二维矩阵，其中矩阵的每个元素表示两个字符串的相应字符是否相等。

然后，通过遍历矩阵并比较字符，可以找到两个字符串的最长公共子序列。

对于多个字符串的情况，可以将其视为两两之间求解最长公共子序列的问题。

首先，选取两个字符串，求出它们的最长公共子序列。

然后，将得到的最长公共子序列与下一个字符串进行比较，继续寻找最长公共子序列。

重复这个过程，直到所有字符串都比较完毕。

需要注意的是，多个字符串的最长公共子序列可能不唯一，但它们的长度一定相同。

实验二最长公共子序列（动态规划算法）班级：08计算机科学与技术（1）班学号：E08620113 姓名：戴斌江机器号：实验二最长公共子序列问题一、实验目的：1、理解动态规划算法的概念；2、掌握动态规划算法的基本要素；3、掌握设计动态规划算法的步骤；4、通过应用范例学习动态规划算法的设计技巧与策略；二、实验内容及要求：1、使用动态规划算法解决最长公共子序列问题：给定两个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。

2、通过上机实验进行算法实现。

3、保存和打印出程序的运行结果，并结合程序进行分析，上交实验报告。

三、实验原理：动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程（decision process)最优化的数学方法。

20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。

1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。

算法总体思想：1)动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题,先求解子问题，然后从这些子问题的解得到原问题的解。

2)与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是独立的。

子问题中存在大量的公共子问题，在分治求解过程中被多次重复计算，保存计算结果，为后面的计算直接引用，减少重复计算次数这就是动态规划的基本思想。

3)用动态规划算法求解问题，可依据其递归式以自底向上的方式进行计算。

在计算过程中，保存已解决的子问题的答案。

每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量重复计算，最终得到多项式时间算法。