bon

这一篇讲我对最长公共子序列（LCS）的理解，之前只是强记了公式，现在有了较好的理解。

主要是要理解这个问题具有最优子结构性质。

设序列和的LCS是，则

(1) 若，则，且是与的LCS；

(2) 若，且，则是与的LCS；

(3) 若，且，则是与的LCS 。

证明：(1) 若，说明在的后面加上，可以得到一个长为k+1的新序列：，这与是与
                  的LCS矛盾。另外若不是与的LCS，那么我们只用与就可以得到一个长度至少为k的子序列，再这个子序列
                  后面再加上，就可以用与构造得到一个长为k+1的子序列，这也产生了矛盾。
         
            (2) 若与有比更长的LCS，则这个LCS同样是与的一个长于k的LCS，矛盾。(3)的证明类似。

思考：(2)中的结论"是与的LCS "能否改成"是与的LCS" 呢？因为可能是最后一个元素，那么与的LCS就不是
                  了，而是更小的一个序列。
               
                  其实(2)的条件暗示着可能就是，当然也有可能不是，但是不管怎么样， 肯定是与的LCS。

                  下面的图说明了这两种情况：

                  
由此我们可以得到如下的状态转移方程：



下面就是题目代码啦，很简单，没什么好说的。