動態規劃經典：最長公共子序列 (LCS) 長度與路徑重建

問題定義

給定兩個序列 X[1..m]、Y[1..n]，尋找最長子序列（不要求連續）使其同時為 X 和 Y 的子序列。例如 X="abcde"、Y="afffbcde"，LCS 為 "bcde"，長度 4。

動態規劃遞推關係

定義 dp[i][j] 為 X[1..i] 與 Y[1..j] 的 LCS 長度。逆向思考（從尾部向前）：

• 若 X[i] == Y[j]：此字符必在 LCS 中 → dp[i][j] = 1 + dp[i-1][j-1]。
• 若 X[i] != Y[j]：至少一方不在 LCS → dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
• 邊界：i==0 || j==0 → dp=0。

遞歸備忘錄實現（自頂向下）

#include <stdio.h>
#include <string.h>
#define MAX 100

int dp[MAX+2][MAX+2];  // 0 表示未計算
char X[MAX] = "abcde";
char Y[MAX] = "afffbcde";

int LCS(int i, int j) {
    if (i <= 0 || j <= 0) return 0;
    if (dp[i][j] != 0) return dp[i][j];

    if (X[i-1] == Y[j-1])
        return dp[i][j] = LCS(i-1, j-1) + 1;
    else {
        int a = LCS(i-1, j);
        int b = LCS(i, j-1);
        return dp[i][j] = (a > b ? a : b);
    }
}

int main() {
    int m = strlen(X), n = strlen(Y);
    printf("LCS Length: %d\n", LCS(m, n));  // 輸出 4
    return 0;
}

迭代填表實現（自底向上，效能更優）

void LCS_Iterative(int m, int n) {
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (X[i-1] == Y[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = (dp[i-1][j] > dp[i][j-1]) ? dp[i-1][j] : dp[i][j-1];
        }
    }
}

重建 LCS 具體序列

填表完成後，從 dp[m][n] 逆向回溯：

void PrintLCS(int i, int j) {
    if (i == 0 || j == 0) return;

    if (X[i-1] == Y[j-1]) {
        PrintLCS(i-1, j-1);
        putchar(X[i-1]);  // 正序輸出
    }
    else if (dp[i-1][j] >= dp[i][j-1])
        PrintLCS(i-1, j);
    else
        PrintLCS(i, j-1);
}

呼叫 PrintLCS(m, n) 即可輸出 bcde。

空間優化：滾動陣列

遞推只依賴前一行，可壓縮為兩行 O(min(m,n)) 空間：

int *prev = calloc(n+1, sizeof(int));
int *curr = calloc(n+1, sizeof(int));
for (int i = 1; i <= m; ++i) {
    for (int j = 1; j <= n; ++j) {
        if (X[i-1] == Y[j-1]) curr[j] = prev[j-1] + 1;
        else curr[j] = (prev[j] > curr[j-1]) ? prev[j] : curr[j-1];
    }
    swap(prev, curr);
}
// 答案在 prev[n]

注意：空間優化後無法直接回溯重建序列，需保留完整表或採用 Hirschberg 算法（分治 + 線性空間）。

複雜度分析

擴展應用

• 最長公共子串：要求連續，遞推改為 X[i]==Y[j] ? dp[i-1][j-1]+1 : 0，須記錄最大值位置。
• 編輯距離：允許增刪改操作，LCS 是編輯距離的特例（僅允許刪除）。
• 版本控制 Diff：Git/Myers 算法基於 LCS 變體實現最小編輯腳本。
• 生物資訊學：DNA/蛋白質序列比對，尋找保守區域。

總結

LCS 是動態規劃的教科書級範例，展示了「最優子結構」與「重疊子問題」兩大核心特徵。掌握從遞推定義、填表順序、路徑回溯到空間優化的完整鏈路，能舉一反三解決字串、序列、樹等結構上的相似度計算問題。