若给定序列X={ x 1 x_1 x1, x 2 x_2 x2,…, x m x_m xm}，则另一序列Z={ z 1 z_1 z1, z 2 z_2 z2,…, z k z_k zk} 是X的子序列，是指存在一个严格递增下标序列{ i 1 i_1 i1, i 2 i_2 i2,…, i k i_k ik}使得对于所有j=1,2,…,k有： z j z_j zj = x i j x_{i_j} xij 。
例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}
给定2个序列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的公共子序列。
给定2个序列X={ x 1 x_1 x1, x 2 x_2 x2,…, x m x_m xm}和 Y={ y 1 y_1 y1, y 2 y_2 y2,…, y n y_n yn}，找出X和Y的最长公共子序列。
设序列X={ x 1 x_1 x1, x 2 x_2 x2,…, x m x_m xm}和Y={ y 1 y_1 y1, y 2 y_2 y2,…, y n y_n yn}的最长公共子序列为Z={ z 1 z_1 z1, z 2 z_2 z2,…, z k − 1 z_{k-1} zk−1, z k z_k zk} ，则：
2个序列的最长公共子序列包含了它们前缀的最长公共子序列。最长公共子序列问题具有最优子结构性质。 最优子结构性质：问题最优解，是否包含了子问题的最优解。子问题变为Xm-1 ={ x 1 x_1 x1, x 2 x_2 x2,…, x m − 1 x_{m-1} xm−1}和Yn-1 ={ y 1 y_1 y1, y 2 y_2 y2,…, y n − 1 y_{n-1} yn−1}的最长公共子序列。
为了验证整个问题最优解Z是否包含子问题Xm-1和Yn-1最优解，就要验证 Z k − 1 Z_{k-1} Zk−1={ z 1 z_1 z1, z 2 z_2 z2,…, z k − 1 z_{k-1} zk−1}是否是子问题Xm-1和Yn-1的最长公共子序列（即： 验证Zk-1是否是Xm-1和Yn-1长度为k-1的公共子序列）。
证明：若Xm-1和Yn-1有长度大于k-1的公共子序列W，则将xm加在W尾部产生X和Y的长度大于k的公共子序列，与题干中X和Y的最长公共子序列长度为k矛盾，故Zk-1是Xm-1和Yn-1的最长公共子序列
子问题变为Xm-1 ={ x 1 x_1 x1, x 2 x_2 x2,…, x m − 1 x_{m-1} xm−1}和Y ={ y 1 y_1 y1, y 2 y_2 y2,…, y n y_{n} yn}的最长公共子序列。
为了验证整个问题最优解Z是否包含子问题Xm-1和Y最优解，就要验证 Z k Z_{k} Zk={ z 1 z_1 z1, z 2 z_2 z2,…, z k z_{k} zk是否是子问题Xm-1和Y的最长公共子序列（即： 验证Z是否是Xm-1和Y长度为k的公共子序列）。
证明：若Xm-1和Y有长度大于k的公共子序列W，则W也是X和Y的长度大于k的公共子序列，这与Z是X和Y的最长公共子序列矛盾。
子问题变为X ={ x 1 x_1 x1, x 2 x_2 x2,…, x m x_{m} xm}和 Y n − 1 Y_{n-1} Yn−1 ={ y 1 y_1 y1, y 2 y_2 y2,…, y n − 1 y_{n-1} yn−1}的最长公共子序列。
就要验证 Z k Z_{k} Zk={ z 1 z_1 z1, z 2 z_2 z2,…, z k z_{k} zk是否是子问题X和Yn-1的最长公共子序列
证明过程与（2）相似。
2个序列的最长公共子序列包含了它们前缀的最长公共子序列 最长公共子序列问题具有最优子结构性质
找序列X={ x 1 x_1 x1, x 2 x_2 x2,…, x m x_m xm}和Y={ y 1 y_1 y1, y 2 y_2 y2,…, y n y_n yn}的最长公共子序列为Z={ z 1 z_1 z1, z 2 z_2 z2,…, z k − 1 z_{k-1} zk−1, z k z_k zk} ，递归执行如下：
a）和 b）这两个公共子序列中较长者即为X和Y的最长公共子序列。
由最优子结构性质建立子问题最优值的递归关系
用c[i][j]记录序列 X i X_i Xi和 Y j Y_j Yj的最长公共子序列的长度，其中， X i X_i Xi={ x 1 x_1 x1, x 2 x_2 x2,…, x i x_i xi}； Y j Y_j Yj={ y 1 y_1 y1, y 2 y_2 y2,…, y j yj yj}
当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故C[i][j]=0。
由最优子结构性质可建立递归关系如下：
最长公共子序列问题具有子问题重叠性质；
例如，若xm≠yn，找X和Y的最长公共子序列，要计算Xm-1和Y以及X和Yn-1的最长公共子序列，而这两个都包含一个公共子问题，即计算Xm-1和Yn-1的最长公共子序列。
三种情况下b[i][j]的取值
LCSLength只是计算出最优值，并未给出最优解，然而数组b可用于快速构造两个序列的最长公共子序列：
b[i][j]=1时表示Xi和Yj的最长公共子序列是由Xi-1和Yj-1的最长公共子序列加上xi所得到；b[i][j]=2时表示Xi和Yj的最长公共子序列与Xi-1和Yj的最长公共子序列相同；b[i][j]=3时表示Xi和Yj的最长公共子序列与Xi和Yj-1的最长公共子序列相同。根据b的内容打印出最长公共子序列
给定两个序列X={B,C,D,A}，Y={A,B,C,B}，请采用动态规划策略。求出其最长公共子序列，要求给出过程。
算法lcsLength和lcs中，可进一步将数组b省去。
事实上，数组元素c[i][j]的值仅由c[i-1][j-1]，c[i-1][j]和c[i][j-1]这3个数组元素的值所确定。对于给定的数组元素c[i][j]，可仅借助于c本身确定c[i][j]的值是由c[i-1][j-1]，c[i-1][j]和c[i][j-1]中哪一个值所确定的。给定两个序列X={B,C,D,A}，Y={A,B,C,B}，请采用动态规划策略求出其最长公共子序列，要求给出过程。
参照算法分析：
for (i = 1; i <= m; i++) for (j = 1; j <= n; j++) { if (x[i]==y[j]) { c[i][j]=c[i-1][j-1]+1; b[i][j]=1;} else if (c[i-1][j]>=c[i][j-1]) { c[i][j]=c[i-1][j]; b[i][j]=2;} else { c[i][j]=c[i][j-1]; b[i][j]=3;} } } [4,4]开始，此时为2。比较[4,3]和[3,4]，与[4,4]的值相同，说明没有新增公共字符。又[3,4]=[4,3]，从算法中可以看出此时下一步应该是[i-1,j],即[3,4][3,4]开始,此时为2。比较[3,3]和[2,4]，与[3,4]的值相同，说明没有新增公共字符。又[3,3]=[2,4]，从算法中可以看出此时下一步应该是[i-1,j],即[2,4][2,4]开始,此时为2。比较[2,3]和[1,4]，有一个与[2,4]相同，说明没有新增公共字符。又[2,3]>[1,4]，从算法中可以看出此时下一步应该是[i,j-1],即[2,3][2,3]开始,此时为2。比较[2,2]和[1,3]，都与[2,3]不同，说明此时新增了公共字符。从算法中可以看出此时下一步应该是[i-1,j-1],即[1,2][1,2]开始,此时为2。比较[1,1]和[0,2]，都与[1,2]不同，说明此时新增了公共字符。从算法中可以看出此时下一步应该是[i-1,j-1],即[0,1]此时x=0,算法结束.最长公共子序列：｛ＢＣ｝
如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。
事实上，在计算c[i][j]时，只用到数组c的第i行和第i-1行。用2行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至O(min(m,n))。输入 请输入第一个序列(字母中间不要空格)：BCDA 请输入第二个序列(字母中间不要空格)：ABCB
输出 BC
