证明：Theorem 15.1: (Optimal substructure of an LCS)

Let X = 《x1, x2, ..., xm》 and Y = 《y1, y2, ..., yn》 be sequences, and let Z = 《z1, z2, ..., zk》 be any LCS of X and Y.

1. If xm = yn, then zk = xm = yn and Zk-1 is an LCS of Xm-1 and Yn-1.
2. If xm ≠ yn, then zk ≠ xm implies that Z is an LCS of Xm-1 and Y.
3. If xm ≠ yn, then zk ≠ yn implies that Z is an LCS of X and Yn-1.

1.如果zk ≠ xm ，则zk ≠ yn 。令z k+1 = xm = yn，则《Z, zk+1》是CS，但是长度大于Z。同时，若存在比Zk-1长的CS，则的长度大于Zk。得证。
2.xm ≠ yn & zk ≠ xm，若zk = yn，Z不是LCS of Xm-1 and Y，则Y中不存在一个yl，使得l大于n，有zk+1 = yl
若zk ≠ yn，Z不是LCS of Xm-1 and Y，则存在zk+1 = yl = xo，使《Z, z+1》是CS of Xm-1 and Y。进一步，是CS of Xm and Yn 。矛盾
3 同2。