1、公共子序列問題
網上有很多關于公共子序列問題，說的大同小異，看了很多不明白，很多都是晦澀難懂，這裡分享一個連接配接，個人覺得講述的比較明白，易懂。
<a href="http://blog.csdn.net/v_july_v/article/details/6695482" target="_blank">http://blog.csdn.net/v_july_v/article/details/6695482</a>
我這裡也簡單的把自己的了解說一下，求公共子序列問題是一個非常常見的問題，最差的方法就是暴力比對，暴力比對算法第一步求去短字元串的所有序列組合，然後從長到短一個一個的去比對時候有公共序列相同，即使使用了這樣的剪枝，該算法效率任然很低。
比較受人青睐的算法當然莫過于動态規劃了，動态規劃的核心是找到轉移方程。把複雜的問題通過轉移方程轉移到子問題。
動态規劃算法
事實上，最長公共子序列問題也有最優子結構性質。
記:
Xi=﹤x1，⋯，xi﹥即X序列的前i個字元 (1≤i≤m)（字首） Yj=﹤y1，⋯，yj﹥即Y序列的前j個字元 (1≤j≤n)（字首）
假定Z=﹤z1，⋯，zk﹥∈LCS(X , Y)。
若xm=yn（最後一個字元相同），則不難用反證法證明：該字元必是X與Y的任一最長公共子序列Z（設長度為k）的最後一個字元，即有zk = xm = yn 且顯然有Zk-1∈LCS(Xm-1 , Yn-1)即Z的字首Zk-1是Xm-1與Yn-1的最長公共子序列。此時，問題化歸成求Xm-1與Yn-1的LCS（LCS(X , Y)的長度等于LCS(Xm-1 , Yn-1)的長度加1）。
若xm≠yn，則亦不難用反證法證明：要麼Z∈LCS(Xm-1, Y)，要麼Z∈LCS(X , Yn-1)。由于zk≠xm與zk≠yn其中至少有一個必成立，若zk≠xm則有Z∈LCS(Xm-1 , Y)，類似的，若zk≠yn 則有Z∈LCS(X , Yn-1)。此時，問題化歸成求Xm-1與Y的LCS及X與Yn-1的LCS。LCS(X , Y)的長度為：max{LCS(Xm-1 , Y)的長度, LCS(X , Yn-1)的長度}。
由于上述當xm≠yn的情況中，求LCS(Xm-1 , Y)的長度與LCS(X , Yn-1)的長度，這兩個問題不是互相獨立的：兩者都需要求LCS(Xm-1，Yn-1)的長度。另外兩個序列的LCS中包含了兩個序列的字首的LCS，故問題具有最優子結構性質考慮用動态規劃法。
也就是說，解決這個LCS問題，你要求三個方面的東西：1、LCS（Xm-1，Yn-1）+1；2、LCS（Xm-1，Y），LCS（X，Yn-1）；3、max{LCS（Xm-1，Y），LCS（X，Yn-1）}。
是以解決這個問題的動态轉移方程即：
if xm==yn LCS(Xm,Yn)= LCS（Xm-1，Yn-1）+1;
if xm!=yn LCS(Xm,Yn)= max{LCS（Xm-1，Yn),LCS（Xm，Yn-1)};
代碼如下：
<a></a>
運作結果
2、最大公共子串
首先區分下公共字串和公共子序列的差別，公共子序列是在整個字元串中隻要按照順序可以不用連續的，但是公共子串是指必須連續的字元串，舉個例子
公共子序列是 BCBA
公共字串是 AB
求公共字串比公共子序列稍微簡單了一些，如果上邊所述，公共子串也可以用暴力比對方法，求出較短的字元串的所有子串，然後可以從長到短利用kmp字元串比對算法求出公共子串，同時還添加了剪枝，但是字樣的暴力比對效率始終是比較差的，最好的方法還是使用動态規劃。
根據上邊公共子序列動态規劃的方法分析，其實我們可以發現公共子串和公共子序列非常類似
隻是在狀态轉移方程是稍有不同，
事實上，最長公共子串問題也有最優子結構性質。
若xm=yn（最後一個字元相同），則不難用反證法證明：該字元必是X與Y的任一最長公共子串Z（設長度為k）的最後一個字元，即有zk = xm = yn 且顯然有Zk-1∈LCS(Xm-1 , Yn-1)即Z的字首Zk-1是Xm-1與Yn-1的最長公共子串。此時，問題化歸成求Xm-1與Yn-1的LCS（LCS(X , Y)的長度等于LCS(Xm-1 , Yn-1)的長度加1）。
重要的是這裡的不同：
若xm≠yn，由于zk≠xm與zk≠yn 那麼說明之前相同的字元串也不能連接配接起來，此時的LCS(X,Y) 的長度回歸到0重新找最長的公共子串。
是以：關于最長公共子串的動态轉移方程為：
if xm!=yn LCS(Xm,Yn)= 0;
結果：
本文轉自NewPanderKing51CTO部落格，原文連結：http://www.cnblogs.com/newpanderking/p/3946159.html ，如需轉載請自行聯系原作者