下载文档原格式
公共子序列问题徐康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 ），而查找所有的公共子序列的时间复杂度取决于所遍历的路径，而路径是由算法递归的方向决定的。
分治法1、二分搜索算法是利用（分治策略）实现的算法。
9. 实现循环赛日程表利用的算法是（分治策略）27、Strassen矩阵乘法是利用（分治策略）实现的算法。
34．实现合并排序利用的算法是（分治策略）。
实现大整数的乘法是利用的算法（分治策略）。
17．实现棋盘覆盖算法利用的算法是（分治法）。
29、使用分治法求解不需要满足的条件是（子问题必须是一样的）。
不可以使用分治法求解的是（0/1背包问题）。
动态规划下列不是动态规划算法基本步骤的是（构造最优解）下列是动态规划算法基本要素的是（子问题重叠性质）。
下列算法中通常以自底向上的方式求解最优解的是（动态规划法）备忘录方法是那种算法的变形。
（动态规划法）最长公共子序列算法利用的算法是（动态规划法）。
矩阵连乘问题的算法可由（动态规划算法B）设计实现。
实现最大子段和利用的算法是（动态规划法）。
贪心算法能解决的问题：单源最短路径问题，最小花费生成树问题，背包问题，活动安排问题，不能解决的问题：N皇后问题，0/1背包问题是贪心算法的基本要素的是（贪心选择性质和最优子结构性质）。
回溯法回溯法解旅行售货员问题时的解空间树是（排列树）。
剪枝函数是回溯法中为避免无效搜索采取的策略回溯法的效率不依赖于下列哪些因素（确定解空间的时间）分支限界法最大效益优先是（分支界限法）的一搜索方式。
分支限界法解最大团问题时，活结点表的组织形式是（最大堆）。
分支限界法解旅行售货员问题时，活结点表的组织形式是（最小堆）优先队列式分支限界法选取扩展结点的原则是（结点的优先级）在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( 分支限界法).从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( 栈式分支限界法)之外都是最常见的方式.（1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。
（2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。
动态规划经典——最长公共⼦序列问题（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)。
最长⼦串（动态规划）题⽬：如果字符串⼀的所有字符按其在字符串中的顺序出现在另外⼀个字符串⼆中，则字符串⼀称之为字符串⼆的⼦串。
注意，并不要求⼦串（字符串⼀）的字符必须连续出现在字符串⼆中。
请编写⼀个函数，输⼊两个字符串，求它们的最长公共⼦串，并打印出最长公共⼦串。
例如：输⼊两个字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它们的最长公共⼦串，则输出它们的长度4，并打印任意⼀个⼦串。
分析：求最长公共⼦串（Longest CommonSubsequence, LCS）是⼀道⾮常经典的动态规划题。
以下分析参见另外的⼀篇博⽂。
步骤⼀、描述⼀个最长公共⼦序列先介绍LCS问题的性质：记Xm={x0, x1,…xm-1}和Yn={y0,y1,…,yn-1}为两个字符串，并设Zk={z0,z1,…zk-1}是X和Y的任意⼀个LCS，则可得出3条性质：1. 如果xm-1=yn-1，那么zk-1=xm-1=yn-1，并且Zk-1是Xm-1和Yn-1的⼀个LCS；2. 如果xm-1≠yn-1，那么当zk-1≠xm-1时，Z是Xm-1和Y的LCS；3. 如果xm-1≠yn-1，那么当zk-1≠yn-1时，Z是X和Yn-1的LCS；下⾯简单证明⼀下由上述相应条件得出的这些性质：1. 如果zk-1≠xm-1，那么我们可以把xm-1（yn-1）加到Z中得到Z’，这样就得到X和Y的⼀个长度为k+1的公共⼦串Z’。
这就与长度为k的Z是X和Y的LCS相⽭盾了。
因此⼀定有zk-1=xm-1=yn-1。
既然zk-1=xm-1=yn-1，那如果我们删除zk-1（xm-1、yn-1）得到的Zk-1，Xm-1和Yn-1，显然Zk-1是Xm-1和Yn-1的⼀个公共⼦串，现在我们证明Zk-1是Xm-1和Yn-1的LCS。
⽤反证法不难证明。
假设有Xm-1和Yn-1有⼀个长度超过k-1的公共⼦串W，那么我们把加到W中得到W’，那W’就是X和Y的公共⼦串，并且长度超过k，这就和已知条件相⽭盾了。
动态规划问题常见解法
动态规划是一种高效解决优化问题的方法。
它通常用于涉及最
优化问题和最短路径的计算中。
下面是一些常见的动态规划问题解法：
1. 背包问题
背包问题是动态规划中的经典问题之一。
其目标是在给定的背
包容量下，选择一些物品放入背包中，使得物品总价值最大。
解决
这个问题的常见方法是使用动态规划的思想，定义一个二维数组来
记录每个物品放入背包时的最大价值，然后逐步计算出最终的结果。
2. 最长公共子序列问题
最长公共子序列问题是寻找两个字符串中最长的公共子序列的
问题。
解决这个问题的常见方法是使用动态规划的思想，定义一个
二维数组来记录两个字符串中每个位置的最长公共子序列的长度。
然后通过递推关系来计算出最终的结果。
3. 矩阵链乘法问题
矩阵链乘法问题是计算一系列矩阵相乘的最佳顺序的问题。
解
决这个问题的常见方法是使用动态规划的思想，定义一个二维数组
来记录每个矩阵相乘时的最小乘法次数，然后逐步计算出最终的结果。
4. 最长递增子序列问题
最长递增子序列问题是寻找一个序列中最长的递增子序列的问题。
解决这个问题的常见方法是使用动态规划的思想，定义一个一
维数组来记录每个位置处的最长递增子序列的长度，然后通过递推
关系来计算出最终的结果。
以上是一些常见的动态规划问题解法。
通过灵活运用这些方法，我们可以更高效地解决优化问题和最短路径计算等相关任务。
最长公共子上升序列
最长公共子上升序列（LCS）是指在一组有序数列中，两个或多个序列具有最长公共子序列（LCS）的问题，其中子序列必须保持原始序列中数字的相对顺序，而且所有的数字都是递增的，即公共子序列是一个上升的序列。
它的解决方案是基于动态规划（DP）算法的，可以利用递归算法和顺序搜索技术以有效的方式求解最长公共子上升序列问题。
假设有两个有序序列X和Y，其中X={x1，x2，x3，...，xm}和
Y={y1，y2，y3，...，yn}，LCS问题的解决方法是首先判断输入序列X 和Y有没有相同的元素，如果有，则称为基本情况。
如果没有，则假设xm=ym，比较xm-1与ym-1的大小，当xm-1 < ym-1时，得到xm-1的最长公共子上升序列的问题的解是xm-1的最长公共子上升序列，当xm-1 > ym-1时，得到ym-1的最长公共子上升序列的问题的解是ym-1的最长公共子上升序列，如果xm-1 = ym-1，则得到最长公共子上升序列的问题的解是xm-1和ym-1的最长公共子上升序列加上xm或ym。
算法55----最长⼦序列【动态规划】⼀、题⽬：最长公共⼦序列：给定两个字符串，求解这两个字符串的最长公共⼦序列（Longest Common Sequence）。
⽐如字符串L：BDCABA；字符串S：ABCBDAB 则这两个字符串的最长公共⼦序列长度为4，最长公共⼦序列是：BCBA思路：动态规划：时间O(n * m)，空间O(n * m)创建 DP数组C[i][j]：表⽰⼦字符串L【：i】和⼦字符串S【：j】的最长公共⼦序列个数。
状态⽅程：个数代码：def LCS(L,S):if not L or not S:return""dp = [[0] * (len(L)+1) for i in range(len(S)+1)]for i in range(len(S)+1):for j in range(len(L)+1):if i == 0 or j == 0:dp[i][j] = 0else:if L[j-1] == S[i-1]:dp[i][j] = dp[i-1][j-1] + 1else:dp[i][j] = max(dp[i-1][j],dp[i][j-1])return dp[-1][-1]L = 'BDCABA'S = 'ABCBDAB'LCS(L,S)最长⼦序列代码：设置⼀个标志def LCS(L,S):if not L or not S:return""res = ''dp = [[0] * (len(L)+1) for i in range(len(S)+1)]flag = [['left'] * (len(L)+1) for i in range(len(S)+1)]if i == 0 or j == 0:dp[i][j] = 0flag [i][j] = '0'else:if L[j-1] == S[i-1]:dp[i][j] = dp[i-1][j-1] + 1flag[i][j] = 'ok'else:dp[i][j] = max(dp[i-1][j],dp[i][j-1])flag[i][j] = 'up'if dp[i][j] == dp[i-1][j] else'left' return dp[-1][-1],flagdef printres(flag,L,S):m = len(flag)n = len(flag[0])res = ''i , j = m-1 , n-1while i > 0 and j > 0:if flag[i][j] == 'ok':res += L[j-1]i -= 1j -= 1elif flag[i][j] == 'left':j -= 1elif flag[i][j] == 'up':i -= 1return res[::-1]L = 'BDCABA'S = 'ABCBDAB'num,flag = LCS(L,S)res = printres(flag,L,S)⼆、题⽬：最长递增⼦序列8}，则其最长的单调递增⼦序列为{5，6，7，8}，长度为4.解法⼀：最长公共⼦序列：O（N^2）这个问题可以转换为最长公共⼦序列问题。
动态规划解最长公共子序列问题动态规划主要针对最优化问题,它的决策是全面考虑不同的情况分别进行决策,,最后通过多阶段决策逐步找出问题的最终解.当各个阶段采取决策后,会不断决策出新的数据,直到找到最优解.每次决策依赖于当前状态,又随机引起状态的转移.一个决策序列就是在变化的状态中产生出来的,故有”动态”的含义.所以,这种多阶段最优化决策解决问题的过程称为动态规划.一问题的描述与分析字符序列的子序列是指从给定字符序列中随意地(不一定连续)去掉若干字符(可能一个也不去掉)后形成的字符序列..令给定的字符序列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）（生物信息学中常用算法）子序列的概念：设X=< x1, x2,┅, x m>，若有1≤i1< i2< ┅<i k≤m，使得Z=< z1, z2,┅, z k> = < x i1, x i2,┅, x ik>，则称Z是X的子序列，记为Z<X。
e.g. X=<A,B,C,B,D,A,B>, Z=<B,C,B,A>, 则有Z<X。
公共子序列的概念：设X，Y是两个序列，且有Z<X和Z<Y，则称Z是X和Y 的公共子序列。
最长公共子序列的概念：若Z<X，Z<Y，且不存在比Z更长的X和Y 的公共子序列，则称Z是X和Y 的最长公共子序列，记为Z∈LCS(X , Y)。
最长公共子序列往往不止一个。
e.g. X=<A,B,C,B,D,A,B>, Y=<B,D,C,A,B,A>, 则Z=<B,C,B,A>, Z’=<B,C,A,B>, Z’’=<B,D,A,B>均属于LCS(X , Y) ，即X,Y有3个LCS。
如何找出X和Y的一个最长公共子序列？Brute-force法：列出X的所有长度不超过n（即∣Y∣）的子序列，从长到短逐一进行检查，看其是否为Y的子序列，直到找到第一个最长公共子序列。
由于X共有2m个子序列，故此方法对较大的m没有实用价值。
是否能使用动态规划法？如何用？分析：记X i=﹤x1，…，x i﹥即X序列的前i个字符(1≤i≤m)（前缀）Y j=﹤y1，…，y j﹥即Y序列的前j个字符(1≤j≤n)（前缀）假定Z=﹤z1，…，z k﹥∈LCS(X , Y)。
若x m=y n（最后一个字符相同），则不难用反证法证明：该字符必是X与Y的任一最长公共子序列Z（设长度为k）的最后一个字符，即有z k = x m = y n且显然有Z k-1∈LCS(X m-1 , Y n-1) 即Z的前缀Z k-1是X m-1与Y n-1的最长公共子序列。
