算法作业：LCS 问 题作业要求 ：设计一个算法求出两个序列的所有LCS，分析最坏情况，用“会计方法”证明利用b[i][j] 求出所有 LCS 的算法在最坏情况下时间复杂度为)(mmnCO1、 算法思路：根据最长公共子序列问题的性质，即经过分解后的子问题具有高度重复性，并且具有最优子结构性质，采用动态规划法求解问题。设X={x 1, x 2, ⋯ , x n}, Y={y1, y2, ⋯ , y m}, 首先引入二维数组C[i][j]记录 X i 和 Y j 的 LCS 的长度，定义C[i][j] 如下：jijyi且x,i,j]][ jC[ ijyixjijiCjiCjiC00001110,]},1][[],][1[max{]][[或，且为了构造出LCS，还需要使用一个二维数组b[m][n] ，b[i][j] 记录 C[i][j] 是通过哪个子问题的值求得的，以决定搜索的方向，欲求出所有的LCS，定义数组b 如下：设 1-对角线方向 ;2-向上 ;3- 向左 ;4-向上或向左若 X[i]=Y[j],b[i][j] = 1, 若 C[i-1][j][i][j-1], 则 b[i][j] = 3, 若 C[i-1][j]=[i][j-1], 则 b[i][j] = 4, 根据以上辅助数组C 和 b 的定义，算法首先需要求出这两个数组，C[m][n] 中记录的最长公共子序列的长度， b 中记录了查找子序列元素的搜索方向。利用 C 和 b 的信息， Find_All_LCS可以采用回溯法求出所有的LCS。基本思路如下：使用一个辅助数组记录每次调用Find_All_LCS得到的 LCS 中的元素，每次递归调用一次Find_All_LCS ，进入一个新的执行层，首先要判断当前处理的两个子序列长度是否大于等于0 ，若不满足，则该层的递归结束，返回上一层；然后再判断当前得到的子序列是否等于数组C 中求出的最长公共子序列长度，若等于，则说明算法执行到此已经得到一个LCS ，按序输出；若不等于，此时根据数组b 中记录的搜索方向继续搜索，特别要说明的是，当b[i][j]=4时，即要向上或向左，需要对这两个方向分别调用Find_All_LCS ，保证沿着这两个方向上LCS 元素不被漏掉，都可以搜索到；若b[i][j]=1 ，即沿对角线方向搜索前进时，此时元素X[i] 为 LCS 中的元素，存放至辅助数组中去，同时将当前已经求得的LCS长度增 1，当递归调用Find_All_LCS从 b[i][j]=1处时，需要回溯一步，搜索其它路径上可能为LCS 中的元素。当所有的可能路径都已经搜索完，算法结束。对于某些情况会输出重复的LCS，这是因为算法在沿不同路径搜索时可能会出现相同的LCS 序列。2、 时间复杂度分析由上述对Find_A...
