問題介紹

??給定一個(gè)序列，另一個(gè)序列滿足如下條件時(shí)稱為X的子序列：存在一個(gè)嚴(yán)格遞增的X的下標(biāo)序列，對(duì)所有的滿足
??給定兩個(gè)序列和,如果同時(shí)是和的子序列，則稱是和的公共子序列。最長(zhǎng)公共子序列（LCS）問題指的是：求解兩個(gè)序列和的長(zhǎng)度最長(zhǎng)的公共子序列。例如，序列和的最長(zhǎng)公共子序列為，長(zhǎng)度為4。
??本文將具體闡釋如何用動(dòng)態(tài)規(guī)劃法（Dynamic Programming）來求解最長(zhǎng)公共子序列（LCS）問題。

算法分析

1. LCS的子結(jié)構(gòu)

??給定一個(gè)序列，對(duì)，定義的第i前綴為,其中為空序列。
??（LCS的子結(jié)構(gòu)）令和為兩個(gè)序列，為和的任意LCS，則：

1. 如果則且是和的一個(gè)LCS。
2. 如果則意味著是和的一個(gè)LCS。
3. 如果則且是和的一個(gè)LCS。

2. 構(gòu)造遞歸解

??在求和的一個(gè)LCS時(shí)，需要求解一個(gè)或兩個(gè)子問題：如果，應(yīng)求解和的一個(gè)LCS，再將追加到這個(gè)LCS的末尾，就得到和的一個(gè)LCS；如果，需求解和的一個(gè)LCS與和的一個(gè)LCS，兩個(gè)LCS較長(zhǎng)者即為和的一個(gè)LCS。當(dāng)然，可以看出，LCS問題容易出現(xiàn)重疊子問題，這時(shí)候，就需要用動(dòng)態(tài)規(guī)劃法來解決。
??定義表示和的LCS的長(zhǎng)度。如果或，則利用LCS的子結(jié)構(gòu)，可以得到如下公式：

3. 計(jì)算LCS的長(zhǎng)度

??計(jì)算LCS長(zhǎng)度的偽代碼為L(zhǎng)CS-LENGTH. 過程LCS-LENGTH接受兩個(gè)子序列和為輸入。它將的值保存在表中，同時(shí)，維護(hù)一個(gè)表，幫助構(gòu)造最優(yōu)解。過程LCS-LENGTH的偽代碼如下：

LCS-LENGTH(X, Y):
m = X.length
n = Y.length
let b[1...m, 1...n] and c[0...m, 0...n] be new table

for i = 1 to m
    c[i, 0] = 0
for j = 1 to n
    c[0, j] = 0

for i = 1 to m
    for j = 1 to n
        if x[i] == y[j]
           c[i,j] = c[i-1, j-1]+1
           b[i,j] = 'diag'
           
        elseif c[i-1, j] >= c[i, j-1]
            c[i,j] = c[i-1, j]
            b[i,j] = 'up'
            
        else
            c[i,j] = c[i, j-1]
            b[i,j] = 'left'
            
return c and b

4. 尋找LCS

??為了尋找和的一個(gè)LCS， 我們需要用到LCS-LENGTH過程中的表，只需要簡(jiǎn)單地從開始，并按箭頭方向追蹤下去即可。當(dāng)在表項(xiàng)中遇到一個(gè)'diag'時(shí)，意味著是LCS的一個(gè)元素。按照這種方法，我們可以按逆序依次構(gòu)造出LCS的所有元素。偽代碼PRINT-LCS如下：

PRINT-LCS(b, X, i, j):
    if i == 0 or j == 0
        return
    if b[i,j] == 'diag'
        PRINT-LCS(b, X, i-1, j-1)
        print x[i]
    elseif b[i,j] == 'up':
        PRINT-LCS(b, X, i-1, j)
    else
        PRINT-LCS(b, X, i, j-1)

程序?qū)崿F(xiàn)

??有了以上對(duì)LCS問題的算法分析，我們不難寫出具體的程序來實(shí)現(xiàn)它。下面將會(huì)給出Python代碼和Java代碼，供讀者參考。
??完整的Python代碼如下：

import numpy as np

# using dynamic programming to solve LCS problem
# parameters: X,Y -> list
def LCS_LENGTH(X, Y):
    m = len(X) # length of X
    n = len(Y) # length of Y

    # create two tables, b for directions, c for solution of sub-problem
    b = np.array([[None]*(n+1)]*(m+1))
    c = np.array([[0]*(n+1)]*(m+1))

    # use DP to sole LCS problem
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i-1] == Y[j-1]:
                c[i,j] = c[i-1,j-1]+1
                b[i,j] = 'diag'
            elif c[i-1,j] >= c[i, j-1]:
                c[i,j] = c[i-1,j]
                b[i,j] = 'up'
            else:
                c[i,j] = c[i,j-1]
                b[i,j] = 'left'
    #print(b)
    #print(c)
    return b,c

# print longest common subsequence of X and Y
def print_LCS(b, X, i, j):

    if i == 0 or j == 0:
        return None
    if b[i,j] == 'diag':
        print_LCS(b, X, i-1, j-1)
        print(X[i-1], end=' ')
    elif b[i,j] == 'up':
        print_LCS(b, X, i-1, j)
    else:
        print_LCS(b, X, i, j-1)

X = 'conservatives'
Y = 'breather'

b,c = LCS_LENGTH(X,Y)
print_LCS(b, X, len(X), len(Y))

輸出結(jié)果如下：

e a t e 

??完整的Java代碼如下：

package DP_example;

import java.util.Arrays;
import java.util.List;

public class LCS {
    // 主函數(shù)
    public static void main(String[] args) {
        // 兩個(gè)序列X和Y
        List<String> X = Arrays.asList("A","B","C","B","D","A","B");
        List<String> Y = Arrays.asList("B","D","C","A","B","A");

        int m = X.size(); //X的長(zhǎng)度
        int n = Y.size(); // Y的長(zhǎng)度
        String[][] b = LCS_length(X, Y); //獲取維護(hù)表b的值

        print_LCS(b, X, m, n); // 輸出LCS
    }

    /*
    函數(shù)LCS_length：獲取維護(hù)表b的值
    傳入?yún)?shù)： 兩個(gè)序列X和Y
    返回值： 維護(hù)表b
     */
    public static String[][] LCS_length(List X, List Y){
        int m = X.size(); //X的長(zhǎng)度
        int n = Y.size(); // Y的長(zhǎng)度
        int[][] c = new int[m+1][n+1];
        String[][] b = new String[m+1][n+1];

        // 對(duì)表b和表c進(jìn)行初始化
        for(int i=1; i<m+1; i++){
            for(int j=1; j<n+1; j++){
                c[i][j] = 0;
                b[i][j] = "";
            }
        }
        
        // 利用自底向上的動(dòng)態(tài)規(guī)劃法獲取b和c的值
        for(int i=1; i<m+1; i++){
            for(int j=1; j<n+1; j++){
                if(X.get(i-1) == Y.get(j-1)){
                    c[i][j] = c[i-1][j-1]+1;
                    b[i][j] = "diag";
                }
                else if(c[i-1][j] >= c[i][j-1]){
                    c[i][j] = c[i-1][j];
                    b[i][j] = "up";
                }
                else{
                    c[i][j] = c[i][j-1];
                    b[i][j] = "left";
                }
            }
        }

        return b;
    }

    // 輸出最長(zhǎng)公共子序列
    public static int print_LCS(String[][] b, List X, int i, int j){

        if(i == 0 || j == 0)
            return 0;

        if(b[i][j].equals("diag")){
            print_LCS(b, X, i-1, j-1);
            System.out.print(X.get(i-1)+" ");
        }
        else if(b[i][j].equals("up"))
            print_LCS(b, X, i-1, j);
        else
            print_LCS(b, X, i, j-1);

        return 1;
    }
}

輸出結(jié)果如下：

B C B A 

參考文獻(xiàn)

1. 算法導(dǎo)論（第三版） 機(jī)械工業(yè)出版社
2. https://www.geeksforgeeks.org/longest-common-subsequence/

注意：本人現(xiàn)已開通兩個(gè)微信公眾號(hào)： 因?yàn)镻ython（微信號(hào)為：python_math）以及輕松學(xué)會(huì)Python爬蟲（微信號(hào)為：easy_web_scrape）， 歡迎大家關(guān)注哦~~