算法學習 - 最長公共子序列（LCS）C++實現

最長公共子序列

最長公共子序列的問題很簡單，就是在兩個字符串中找到最長的子序列，這裡明確兩個含義：

子串：表示連續的一串字符 。 子序列：表示不連續的一串字符。

所以這裡要查找的是不連續的最長子序列，

動態規劃

這裡為什麼要使用動態規劃可以說一下，簡單來說動態規劃是為了降低時間復雜度的一種算法，申請一個額外空間，來保存每一個步驟的結果，最後從這些結果中找到最優的解。

這裡有個問題就是：一般來說，當前的最優解，只與當前時刻和上一時刻有關系，和其他時刻沒有關系，這樣才能讓動態規劃發生作用，降低復雜度。

分析LCS

其實LCS看起來很麻煩，找不到思路，如果暴力破解可能要O(n^4)了，而這個題目使用動態規劃的思想也非常簡單，為何相比之前的問題不好找思路呢？

是因為之前的動態規劃問題例如：背包問題，生產線問題，都是一維數組空間內的結果，規劃到一個線性時間內，而這個題目需要O(m*n)的時間復雜度和空間復雜度。

所以其實就是進行m*n次對比，每次保存當前的最優解，就可以了。

代碼實現分析

這裡有個問題，就是我們需要的結果僅僅是長度？ 還是包括這個序列串一起輸出。

看下面圖：

這裡可以看到，我們構造的一個i*j的矩陣，這個矩陣裡的內容不但包括數值（當前結果的最優解），還包括一個方向箭頭，這個代表了我們回溯的時候，需要行走的方向。<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwPsv50tTO0sPH1eLA77GjtObBvbj21rWjrL/J0tTKudPDwb249rb+zqy+2NXzo6zSsr/J0tTKudPD0ru49r3hubnM5b7Y1fOhozwvcD4NCjxoMSBpZD0="解法分析">解法分析

其實這個題目在動態規劃來理解，也非常簡單。一個狀態轉移函數。

這個非常好理解，其中一個字符串為0的時候，那麼肯定是0了。

當兩個字符相等的時候，這個時候很好理解，舉例來說：

abcd 和 adcd,在遍歷c的時候，發現前面只有a相等了，也就是1.
那麼c相等，也就是abc和adc在匹配的時候，一定比ab和ad的長度大1，這個1就是c相等麼。也就是相等的時候，是比c[i-1][j-1]大1的。

下一個更好理解了，如果不相等，肯定就是找到上一個時刻對比最大的麼。

代碼

這個代碼只輸出了LCS的長度，而結果數組的方向我已經存儲好了，想要遍歷的，直接從後向前遍歷數組就好了。

//
//  main.cpp
//  LCS
//
//  最長公共子序列(LCS)
//
//  Created by Alps on 15/8/23.
//  Copyright (c) 2015年 chen. All rights reserved.
//

#include 

using namespace std;

/*
* 這裡可以不定義長度，輸入的字符串用string存儲，然後利用string.c_str()來對字符串進行數組轉化。 我這裡為了方便沒有這樣做。
*/
#ifndef MAX_LENGTH
#define MAX_LENGTH 15 //定義字符串最大長度
#endif

int MaxNum(int firstNum, int secondNum){
    return firstNum > secondNum ? firstNum : secondNum;
}

//定義數組結構體
struct matrix{
    int num;
    int direct;
};

typedef matrix Matrix;

int LCS(char *strA, char *strB, int lengthA, int lengthB, Matrix *resultMatrix[]){
    if (lengthA == 0 || lengthB == 0) {
        return 0;
    }
    for (int i = 0; i < lengthA; i++) {
        for (int j = 0; j < lengthB; j++) {
            resultMatrix[i][j].num = 0; //設置所有默認的最長為0
            resultMatrix[i][j].direct = 1; //所有默認方向變成上 0斜上，1上，-1左
        }
    }

    for (int i = 0; i < lengthA; i++) {
        for (int j = 0; j < lengthB; j++) {
            if (strA[i] == strB[j]) {
                resultMatrix[i+1][j+1].num = resultMatrix[i][j].num + 1;
                resultMatrix[i+1][j+1].direct = 0;
            }else{
                resultMatrix[i+1][j+1].num = MaxNum(resultMatrix[i+1][j].num, resultMatrix[i][j+1].num);
                resultMatrix[i+1][j+1].direct = resultMatrix[i+1][j].num > resultMatrix[i][j+1].num ? 1 : -1;
            }
        }
    }
    return resultMatrix[lengthA][lengthB].num;
}

int main(int argc, const char * argv[]) {
    char *strA = (char*)malloc(sizeof(char) * MAX_LENGTH);
    char *strB = (char*)malloc(sizeof(char) * MAX_LENGTH);
    scanf(%s,strA);
    scanf(%s,strB);
    int lengthA = (int)strlen(strA);
    int lengthB = (int)strlen(strB);
    Matrix *resultMatrix[lengthA+1];
    for (int i = 0; i <= lengthA; i++) {
        resultMatrix[i] = (Matrix*)malloc(sizeof(struct matrix)* (lengthB+1));
    }

    int max = LCS(strA, strB, lengthA, lengthB, resultMatrix);
    printf(%d
,max);
    std::cout << Hello, World!
;
    return 0;
}

以上。©Alps1992