2.1、最长公共子序列的结构有如下表示：设序列X=和Y=的一个最长公共子序列Z=，则：

  1. 若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列；

  2. 若xm≠yn且zk≠xm ，则Z是Xm-1和Y的最长公共子序列；

  3. 若xm≠yn且zk≠yn ，则Z是X和Yn-1的最长公共子序列。

其中Xm-1=，Yn-1=，Zk-1=。

2.2、子问题的递归结构由最长公共子序列问题的最优子结构性质可知，要找出X=和Y=的最长公共子序列，可按以下方式递归地进行：

当xm=yn时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一个最长公共子序列。

当xm≠yn时，必须解两个子问题，即找出Xm-1和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列。这两个公共子序列中较长者即为X和Y的一个最长公共子序列。

由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。在计算X和Y的最长公共子序列时，可能要计算出X和Yn-1及Xm-1和Y的最长公共子序列。而这两个子问题都包含一个公共子问题，即计算Xm-1和Yn-1的最长公共子序列。

那么，如何更好地理解这一问题呢？可以参考《最长公共子序列算法》中对相关算法的详细解释，或者阅读《数据结构与算法题解：最长公共子序列和最长公共子串》以获取更多实例和解答思路。

与矩阵连乘积最优计算次序问题类似，我们来建立子问题的最优值的递归关系。用c[i,j]记录序列Xi和Yj的最长公共子序列的长度。其中Xi=，Yj=。

当i=0或j=0时，空序列是Xi和Yj的最长公共子序列，故c[i,j]=0。其他情况下，由定理可建立递归关系如下：

更多详细算法及其实现，可以查看《最长公共子序列LCS算法》以及《算法导论：最长公共子序列》的相关内容。