算法作业：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 ，若不满足，则该层的递归结束，返回上一层；然后再判断当前得到的子序列是否等于
