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。

                  下面的圖說明了這兩種情況：

                  
由此我們可以得到如下的狀態轉移方程：



下面就是題目代碼啦，很簡單，沒什么好說的。