動態規劃求解最長公共子序列（LCS）完整教程：原理、遞推、代碼與複雜度分析

編輯：關於C語言

問題定義

給定兩個序列 X = {x₁, x₂, ..., xₘ} 和 Y = {y₁, y₂, ..., yₙ}，找出它們的**最長公共子序列**（Longest Common Subsequence, LCS）。子序列不要求連續，只要求相對順序一致。區別於「最長公共子串」（需連續）。

例：X = {A, B, C, B, D, A, B}，Y = {B, D, C, A, B, A}
LCS 長度為 4，一組解為 {B, C, B, A}。

核心理論：最優子結構性質

設 Z = LCS(X, Y)。則：

若 xₘ = yₙ，則 zₖ = xₘ = yₙ，且 Zₖ₋₁ = LCS(Xₘ₋₁, Yₙ₋₁)；
若 xₘ ≠ yₙ 且 zₖ ≠ xₘ，則 Z = LCS(Xₘ₋₁, Y)；
若 xₘ ≠ yₙ 且 zₖ ≠ yₙ，則 Z = LCS(X, Yₙ₋₁)。

動態規劃遞推關係

定義 `c[i][j]` 為 Xᵢ 與 Yⱼ 的 LCS 長度（Xᵢ = 前 i 個字符，Yⱼ = 前 j 個字符）。

邊界：`c[0][j] = c[i][0] = 0`。
遞推：

if (X[i-1] == Y[j-1]) c[i][j] = c[i-1][j-1] + 1;
else c[i][j] = max(c[i-1][j], c[i][j-1]);

同時維護方向矩陣 `b[i][j]` 記錄決策來源（↖、↑、←），用於回溯構造具體 LCS。

時間/空間複雜度

時間：O(m·n) —— 雙層循環填表；
空間：O(m·n) —— 存儲 `c` 與 `b` 矩陣。可優化至 O(min(m,n)) 僅求長度，但無法回溯序列。

完整 C++ 實現

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
using namespace std;

enum Dir { LEFT_UP, UP, LEFT };

void PrintLCS(const string& X, int i, int j, const vector<vector<int>>& b) {
    if (i == 0 || j == 0) return;
    if (b[i][j] == LEFT_UP) {
        PrintLCS(X, i-1, j-1, b);
        cout << X[i-1] << ' ';
    } else if (b[i][j] == UP) {
        PrintLCS(X, i-1, j, b);
    } else {
        PrintLCS(X, i, j-1, b);
    }
}

void LCS_Length(const string& X, const string& Y) {
    int m = X.size(), n = Y.size();
    vector<vector<int>> c(m+1, vector<int>(n+1, 0));
    vector<vector<int>> b(m+1, vector<int>(n+1, 0));

    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            if (X[i-1] == Y[j-1]) {
                c[i][j] = c[i-1][j-1] + 1;
                b[i][j] = LEFT_UP;
            } 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;
            }

    cout << "LCS 長度: " << c[m][n] << "\n序列: ";
    PrintLCS(X, m, n, b);
    cout << endl;
}

int main() {
    string X = "ABCBDAB", Y = "BDCABAB";
    LCS_Length(X, Y);
    return 0;
}

輸出：
`LCS 長度: 4`
`序列: B C B A`