動态規劃執行個體（二）：最長公共子序列（LCS）

    本文參考http://www.cnblogs.com/hapjin/p/5572483.html

    給定兩個字元串，求解這兩個字元串的最長公共子序列（Longest Common Sequence）。比如字元串1：BDCABA；字元串2：ABCBDAB，則這兩個字元串的最長公共子序列長度為4，最長公共子序列是：BCBA

二，算法求解

    這是一個動态規劃的題目。對于可用動态規劃求解的問題，一般有兩個特征：①最優子結構；②重疊子問題

    ①最優子結構

    設 X=(x1,x2,.....xn) 和 Y={y1,y2,.....ym} 是兩個序列，将 X 和 Y 的最長公共子序列記為LCS(X,Y)，找出LCS(X,Y)就是一個最優化問題。因為，我們需要找到X 和 Y中最長的那個公共子序列。而要找X 和 Y的LCS，首先考慮X的最後一個元素和Y的最後一個元素。

    1）如果 xn=ym，即X的最後一個元素與Y的最後一個元素相同，這說明該元素一定位于公共子序列中。是以，現在隻需要找：LCS(Xn-1，Ym-1)，LCS(Xn-1，Ym-1)就是原問題的一個子問題。為什麼叫子問題？因為它的規模比原問題小。（小一個元素也是小嘛....）為什麼是最優的子問題？因為我們要找的是Xn-1 和 Ym-1 的最長公共子序列啊。。。最長的！！！換句話說，就是最優的那個。（這裡的最優就是最長的意思）

    2）如果xn != ym，這下要麻煩一點，因為它産生了兩個子問題：LCS(Xn-1，Ym) 和 LCS(Xn，Ym-1)因為序列X 和 序列Y 的最後一個元素不相等嘛，那說明最後一個元素不可能是最長公共子序列中的元素嘛。（都不相等了，怎麼公共嘛）。

        LCS(Xn-1，Ym)表示：最長公共序列可以在(x1,x2,....x(n-1)) 和 (y1,y2,...yn)中找。

        LCS(Xn，Ym-1)表示：最長公共序列可以在(x1,x2,....xn) 和 (y1,y2,...y(n-1))中找。

    求解上面兩個子問題，得到的公共子序列誰最長，那誰就是 LCS（X,Y）。用數學表示就是：

        LCS=max{LCS(Xn-1，Ym)，LCS(Xn，Ym-1)}

    由于條件 1)  和  2)  考慮到了所有可能的情況。是以，我們成功地把原問題 轉化 成了 三個規模更小的子問題。

   ②重疊子問題

    重疊子問題是啥？就是說原問題 轉化 成子問題後，  子問題中有相同的問題。咦？我怎麼沒有發現上面的三個子問題中有相同的啊？？？？

    OK，來看看，原問題是：LCS(X,Y)。子問題有 ❶LCS(Xn-1，Ym-1)    ❷LCS(Xn-1，Ym)    ❸LCS(Xn，Ym-1)初一看，這三個子問題是不重疊的。可本質上它們是重疊的，因為它們隻重疊了一大部分。舉例：第二個子問題：LCS(Xn-1，Ym) 就包含了：問題❶LCS(Xn-1，Ym-1)，為什麼？

    因為，當Xn-1 和 Ym 的最後一個元素不相同時，我們又需要将LCS(Xn-1，Ym)進行分解：分解成：LCS(Xn-1，Ym-1) 和 LCS(Xn-2，Ym)。也就是說：在子問題的繼續分解中，有些問題是重疊的。

    由于像LCS這樣的問題，它具有重疊子問題的性質，是以：用遞歸來求解就太不劃算了。因為采用遞歸，它重複地求解了子問題啊。而且注意哦，所有子問題加起來的個數 可是指數級的哦。。。。

    這篇文章中就示範了一個遞歸求解重疊子問題的示例。

    那麼問題來了，你說用遞歸求解，有指數級個子問題，故時間複雜度是指數級。這指數級個子問題，難道用了動态規劃，就變成多項式時間了？？

    關鍵是采用動态規劃時，并不需要去一 一 計算那些重疊了的子問題。或者說：用了動态規劃之後，有些子問題 是通過 “查表“ 直接得到的，而不是重新又計算一遍得到的。廢話少說：舉個例子吧！比如求Fib數列。

    LCS具體執行個體及實作代碼如下所示：

/**
 * @Title: LCS.java
 * @Package dynamicprogramming
 * @Description: TODO
 * @author peidong
 * @date 2017-6-5 上午9:34:15
 * @version V1.0
 */
package dynamicprogramming;

import java.util.Stack;

/**
 * @ClassName: LCS
 * @Description: 最長公共子序列
 * @date 2017-6-5 上午9:34:15
 *
 */

public class LCS {
    /**
     *
     * @Title: lcs1
     * @Description: 遞歸的方式擷取最長公共子序列
     * @param x  字元串數組
     * @param y  字元串數組
     * @param m  數組長度
     * @param n  數組長度
     * @return
     * @return int
     * @throws
     */
    public static int lcs1(char[] x, char[] y, int m, int n){
        //邊界條件判斷
        if(m == 0 || n ==0)
            return 0;
        if(x[m-1] == y[n-1])
            return 1 + lcs1(x, y, m-1, n-1);
        else
            return max(lcs1(x, y, m-1, n), lcs1(x, y, m, n-1));
    }

    /**
     *
     * @Title: max
     * @Description: 傳回較大值
     * @param a
     * @param b
     * @return
     * @return int
     * @throws
     */
    public static int max(int a, int b){
        return (a > b) ? a : b;
    }

    /**
     *
     * @Title: lcs2
     * @Description: 動态規劃求解最長公共子串
     * @param x   字元串數組
     * @param y   字元串數組
     * @param m   數組長度
     * @param n   數組長度
     * @return int
     * @throws
     */
    public static int lcs2(char[] x, char[] y, int m, int n){
        //初始化數組
        int[][] L = new int[m+1][n+1];

        //求解過程
        for(int i = 0; i <= m; i++){
            for(int j = 0; j <= n; j++){
                if( i == 0 || j == 0){
                    L[i][j] = 0;
                }else if( x[i - 1] == y[j - 1]){
                    L[i][j] = L[i - 1][j - 1] + 1;
                }else{
                    L[i][j] = max(L[i][j - 1], L[i - 1][j]);
                }
            }
        }
        Stack<Character> stack = new Stack();
        int m1 = x.length - 1;
        int n1 = y.length - 1;
        while (n1 >= 0 && m1 >= 0) { // 周遊數組
            if (x[m1] == y[n1]) {
                stack.push(x[m1]);
                m1--;
                n1--;
            } else {// 字元不同時，根據列印出的二維矩陣（測試資料）查找上一個相同的字元
                if (L[m1 + 1][n1] > L[m1][n1 + 1]) {
                    n1--;
                } else {
                    m1--;
                }
            }
        }
        System.out.println("最長公共子序列為：");
        while (!stack.isEmpty()) {// 列印出最長的遞增子序列
            System.out.print(stack.pop() + ",");
        }
        return L[m][n];
    }

    /**
     * @Title: main
     * @Description: TODO
     * @param args
     * @return void
     * @throws
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub

        char[] x ={'A', 'G', 'G', 'T', 'A', 'B'};
        char[] y = {'G', 'X', 'T', 'X', 'A', 'Y', 'B'};
        int m = x.length;
        int n = y.length;

        int res1 = lcs1(x, y, m, n);
        int res2 = lcs2(x, y, m, n);
        System.out.println();
        System.out.println("使用遞歸擷取最長公共子序列長度為：" + res1);
        System.out.println("使用dp擷取最長公共子序列長度為：" + res2);
    }

}