[動态規劃] 最長公共子序列

  算法專題導航頁面

【題目描述】

    給定兩個字元串str1和str2，輸出連個字元串的最長公共子序列。如過最長公共子序列為空，則輸出-1。

【輸入描述】

    輸出包括兩行，第一行代表字元串str1，第二行代表str2。(1≤length(str1),length(str2)≤5000)

【輸出描述】

    輸出一行，代表他們最長公共子序列。如果公共子序列的長度為空，則輸出-1。

【示例1】

    輸入

        1A2C3D4B56

        B1D23CA45B6A

    輸出

        123456

【說明】

    "123456"和“12C4B6”都是最長公共子序列，任意輸出一個。

【備注】

    時間複雜度O(n∗m)，空間複雜度O(n∗m)。(n,m分别表示兩個字元串長度)

【代碼實作 - CPP版 - 經典動态規劃】

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int get_max_length(const string& x, const string& y, vector<vector<int>>& dp) {
    int xlen = x.size();
    int ylen = y.size();
    
    dp[0][0] = x[0] == y[0] ? 1 : 0;
    
    for(int i=1; i<xlen; i++) {
        // 目前位置取值隻可能是其上方的值或者目前位置的值
        dp[i][0] = max(dp[i-1][0], x[i] == y[0] ? 1 : 0);
        //dp[i][0] = dp[i-1][0] == 1 ? 1 : （x[i] == y[0] ？ 1 ： 0）；
    }
    
    for(int j=1; j<ylen; j++) {
        dp[0][j] = max(dp[0][j-1], (x[0] == y[j] ? 1 : 0));
    }
    
    for(int i=1; i<xlen; i++) {
        for(int j=1; j<ylen; j++) {
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1);
        }
    }
    
    return dp[xlen-1][ylen-1];
}

void max_len_str(const string& x, const string& y, string& z, vector<vector<int>>& dp) {
    int xlen = x.size() - 1;
    int ylen = y.size() - 1;
    int index = get_max_length(x, y, dp) - 1;
    while(index) {
        if(ylen>0 && dp[xlen][ylen] == dp[xlen][ylen-1]) {
            ylen--;
        } else if(xlen>0 && dp[xlen][ylen] == dp[xlen-1][ylen]) {
            xlen--;
        } else {
            // 從目前位置，向左上方周遊
            z.push_back(x[xlen]); // 逆序存儲最長公共子序列
            index--;
            xlen--;
            ylen--;
        }
    }
}

int main() {
    string str_a;
    string str_b;
    cin >> str_a;
    cin >> str_b;
    
    int alen = str_a.size();
    int blen = str_b.size();
    vector<vector<int>> dp(alen, vector<int>(blen, 0));
    
    string result_str;
    max_len_str(str_a, str_b, result_str, dp);
    
    if(0 == result_str.size()) {
        return -1;
    } else {
        reverse(result_str.begin(), result_str.end());
        cout << result_str <<endl;
    }
    
    return 0;
}