基本概念

首先需要科普一下渔彰，最長公共子序列（longest common sequence）和最長公共子串（longest common substring）不是一回事兒捷泞。

什么是子序列呢海洼？

這里給出一個例子：有兩個母串
cnblogs
belong
比如序列bo, bg, lg在母串cnblogs與belong中都出現(xiàn)過并且出現(xiàn)順序與母串保持一致畔况，我們將其稱為公共子序列贞谓。最長公共子序列（Longest Common Subsequence,LCS）斤富，顧名思義，是指在所有的子序列中最長的那一個罐柳。

什么是子串呢掌腰？

子串是要求更嚴(yán)格的一種子序列，要求在母串中連續(xù)地出現(xiàn)张吉。
在上述例子的中齿梁，最長公共子序列為blog（cnblogs,belong），最長公共子串為lo（cnblogs, belong）。

給一個圖再解釋一下：

如上圖勺择，給定的字符序列： {a,b,c,d,e,f,g,h}创南，它的子序列示例： {a,c,e,f} 即元素b,d,g,h被去掉后，保持原有的元素序列所得到的結(jié)果就是子序列省核。同理稿辙，{a,h},{c,d,e}等都是它的子序列。
它的子串示例：{c,d,e,f} 即連續(xù)元素c,d,e,f組成的串是給定序列的子串气忠。同理邻储，{a,b,c,d},{g,h}等都是它的子串。

這個問題說明白后旧噪，最長公共子序列（以下都簡稱LCS）就很好理解了吨娜。
給定序列s1={1,3,4,5,6,7,7,8},s2={3,5,7,4,8,6,7,8,2}，s1和s2的相同子序列淘钟，且該子序列的長度最長萌壳，即是LCS。
s1和s2的其中一個最長公共子序列是 {3,4,6,7,8}

動態(tài)規(guī)劃

求解LCS問題日月，不能使用暴力搜索方法袱瓮。一個長度為n的序列擁有 2的n次方個子序列，它的時間復(fù)雜度是指數(shù)階爱咬，太恐怖了尺借。解決LCS問題，需要借助動態(tài)規(guī)劃的思想精拟。

動態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題燎斩。在這類問題中，可能會有許多可行解蜂绎。每一個解都對應(yīng)于一個值栅表，我們希望找到具有最優(yōu)值的解。動態(tài)規(guī)劃算法與分治法類似师枣，其基本思想也是將待求解問題分解成若干個子問題怪瓶，先求解子問題，然后從這些子問題的解得到原問題的解践美。與分治法不同的是洗贰，適合于用動態(tài)規(guī)劃求解的問題，經(jīng)分解得到子問題往往不是互相獨立的陨倡。若用分治法來解這類問題敛滋，則分解得到的子問題數(shù)目太多，有些子問題被重復(fù)計算了很多次兴革。為了避免大量的重復(fù)計算绎晃，節(jié)省時間蜜唾，我們引入一個數(shù)組，不管它們是否對最終解有用庶艾，把所有子問題的解存于該數(shù)組中灵妨，這就是動態(tài)規(guī)劃法所采用的基本方法。

特征分析

解決LCS問題落竹，需要把原問題分解成若干個子問題，所以需要刻畫LCS的特征货抄。

設(shè)A=“a0述召，a1，…蟹地，am”积暖，B=“b0，b1怪与，…夺刑，bn”，且Z=“z0分别，z1遍愿，…，zk”為它們的最長公共子序列耘斩。不難證明有以下性質(zhì)：
如果am=bn沼填，則zk=am=bn，且“z0括授，z1坞笙，…，z(k-1)”是“a0荚虚，a1薛夜，…，a(m-1)”和“b0版述，b1梯澜，…，b(n-1)”的一個最長公共子序列渴析；
如果am!=bn腊徙，則若zk!=am，蘊(yùn)涵“z0檬某，z1撬腾，…，zk”是“a0恢恼，a1民傻，…，a(m-1)”和“b0，b1漓踢，…牵署，bn”的一個最長公共子序列；
如果am!=bn喧半，則若zk!=bn奴迅，蘊(yùn)涵“z0，z1挺据，…取具，zk”是“a0，a1扁耐，…暇检，am”和“b0，b1婉称，…块仆，b(n-1)”的一個最長公共子序列。

有些同學(xué)王暗，一看性質(zhì)就容易暈菜悔据，所以我給出一個圖來讓這些同學(xué)理解一下：

以我在第1小節(jié)舉的例子（S1={1,3,4,5,6,7,7,8}和S2={3,5,7,4,8,6,7,8,2}），并結(jié)合上圖來說：

假如S1的最后一個元素 與 S2的最后一個元素相等俗壹，那么S1和S2的LCS就等于 {S1減去最后一個元素} 與 {S2減去最后一個元素} 的 LCS 再加上 S1和S2相等的最后一個元素蜜暑。

假如S1的最后一個元素 與 S2的最后一個元素不等（本例子就是屬于這種情況），那么S1和S2的LCS就等于 ： {S1減去最后一個元素} 與 S2 的LCS策肝， {S2減去最后一個元素} 與 S1 的LCS 中的最大的那個序列肛捍。

遞歸公式

假設(shè)Z=<z1,z2,?,zk>是X與Y的LCS， 我們觀察到
如果Xm=Yn之众，則Zk=Xm=Yn拙毫，有Zk?1是Xm?1與Yn?1的LCS；
如果Xm≠Yn棺禾，則Zk是Xm與Yn?1的LCS缀蹄，或者是Xm?1與Yn的LCS。

因此膘婶，求解LCS的問題則變成遞歸求解的兩個子問題缺前。但是，上述的遞歸求解的辦法中悬襟，重復(fù)的子問題多衅码，效率低下。改進(jìn)的辦法——用空間換時間脊岳，用數(shù)組保存中間狀態(tài)逝段，方便后面的計算垛玻。這就是動態(tài)規(guī)劃（DP)的核心思想了。
DP求解LCS
用二維數(shù)組c[i][j]記錄串x1x2?xi與y1y2?yj的LCS長度奶躯，則可得到狀態(tài)轉(zhuǎn)移方程

計算LCS的長度的圖解過程

以s1={1,3,4,5,6,7,7,8},s2={3,5,7,4,8,6,7,8,2}為例帚桩。我們借用《算法導(dǎo)論》中的推導(dǎo)圖：

圖中的空白格子需要填上相應(yīng)的數(shù)字（這個數(shù)字就是c[i,j]的定義，記錄的LCS的長度值）嘹黔。填的規(guī)則依據(jù)遞歸公式账嚎，簡單來說：如果橫豎（i,j）對應(yīng)的兩個元素相等，該格子的值 = c[i-1,j-1] + 1儡蔓。如果不等郭蕉，取c[i-1,j] 和 c[i,j-1]的最大值。首先初始化該表：

S1的元素3 與 S2的元素3 相等开呐，所以 c[2,1] = c[1,0] + 1

S1的元素3 與 S2的元素5 不等，c[2,2] =max(c[1,2],c[2,1])规求，圖中c[1,2] 和 c[2,1] 背景色為淺黃色筐付。

繼續(xù)填充：

至此阻肿，該表填完瓦戚。根據(jù)性質(zhì)，c[8,9] = S1 和 S2 的 LCS的長度丛塌，即為5较解。

構(gòu)造LCS

本文S1和S2的最LCS并不是只有1個，本文并不是著重講輸出兩個序列的所有LCS赴邻，只是介紹如何通過上表印衔，輸出其中一個LCS。

我們根據(jù)遞歸公式構(gòu)建了上表姥敛，我們將從最后一個元素c[8][9]倒推出S1和S2的LCS奸焙。

c[8][9] = 5，且S1[8] != S2[9]彤敛，所以倒推回去与帆，c[8][9]的值來源于c[8][8]的值(因為c[8][8] > c[7][9])。

c[8][8] = 5, 且S1[8] = S2[8], 所以倒推回去墨榄，c[8][8]的值來源于 c[7][7]玄糟。

以此類推，如果遇到S1[i] != S2[j] 袄秩，且c[i-1][j] = c[i][j-1] 這種存在分支的情況茶凳，這里請都選擇一個方向（之后遇到這樣的情況嫂拴，也選擇相同的方向）。

這就是倒推回去的路徑贮喧，棕色方格為相等元素筒狠，即LCS = {3,4,6,7,8}，這是其中一個結(jié)果箱沦。

如果如果遇到S1[i] != S2[j] 辩恼，且c[i-1][j] = c[i][j-1] 這種存在分支的情況，選擇另一個方向谓形，會得到另一個結(jié)果灶伊。

即LCS ={3,5,7,7,8}。

關(guān)于時間復(fù)雜度

構(gòu)建c[i][j]表需要Θ(mn)寒跳，輸出1個LCS的序列需要Θ(m+n)聘萨。

代碼實現(xiàn):

package com.smart.algorithm.str;

/**
 * Created by fc.w on 2018/05/09
 */
public class LCS {

    public static int lcs(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();
        int[][] c = new int[n+1][m+1];

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (i == 0 || j == 0) {
                    c[i][j] = 0;
                } else if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    c[i][j] = c[i - 1][j - 1] + 1;
                } else {
                    c[i][j] = Math.max(c[i - 1][j], c[i][j - 1]);
                }
            }
        }
        return c[n][m];
    }

    public static void main(String[] args) {
        String strOne = "abcdefg";
        String strTwo = "adefgwgeweg";
        System.out.println(lcs(strOne, strTwo));
    }

}

參考：
https://blog.csdn.net/hrn1216/article/details/51534607
https://blog.csdn.net/u012102306/article/details/53184446