經典算法研究：動態規劃求解最長公共子序列（LCS）完整推導與代碼

編輯：關於C語言

動態規劃（DP）是解決最優化問題的利器，核心在於最優子結構與重疊子問題。本文以微軟面試經典第56題——最長公共子序列（LCS）為例，完整演示DP四步法：描述最優解結構、遞歸定義、自底向上計算、構造最優解。

一、問題定義

給定兩字符串X = x₁x₂...xₘ、Y = y₁y₂...yₙ。若序列Z同時是X與Y的子序列（不要求連續），稱Z為公共子序列。求長度最大的Z及其長度。
例：X=BDCABA、Y=ABCBDAB，LCS長度為4，如BCBA或BDAB。

二、 LCS 的最優子結構性質證明

設Z = z₁z₂...zₖ為X與Y的一個LCS。三條性質：

若xₘ = yₙ，則zₖ = xₘ = yₙ，且Zₖ₋₁是Xₘ₋₁與Yₙ₋₁的LCS。
若xₘ ≠ yₙ且zₖ ≠ xₘ，則Z是Xₘ₋₁與Y的LCS。
若xₘ ≠ yₙ且zₖ ≠ yₙ，則Z是X與Yₙ₋₁的LCS。

均可用反證法證明：假設不成立，則能構造更長的公共子序列，與LCS定義矛盾。

三、遞歸公式與自底向上DP

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


c[i][j] = 0                              if i=0 or j=0
c[i][j] = c[i-1][j-1] + 1                if i,j>0 and xᵢ = yⱼ
c[i][j] = max(c[i-1][j], c[i][j-1])      if i,j>0 and xᵢ ≠ yⱼ

為構造具體LCS，需記錄決策方向b[i][j]：

↖：來自c[i-1][j-1]（字符匹配，該字符屬於LCS）。
↑：來自c[i-1][j]。
←：來自c[i][j-1]。

LCS-LENGTH 偽代碼


LCS-LENGTH(X, Y)
m ← length[X], n ← length[Y]
for i ← 1 to m: c[i][0] ← 0
for j ← 0 to n: c[0][j] ← 0
for i ← 1 to m:
    for j ← 1 to n:
        if xᵢ = yⱼ:
            c[i][j] ← c[i-1][j-1] + 1
            b[i][j] ← "↖"
        else if c[i-1][j] ≥ c[i][j-1]:
            c[i][j] ← c[i-1][j]
            b[i][j] ← "↑"
        else:
            c[i][j] ← c[i][j-1]
            b[i][j] ← "←"
return c, b

時間O(mn)，空間O(mn)（可優化至O(min(m,n))）。

四、構造 LCS：回溯輸出


PRINT-LCS(b, X, i, j)
if i = 0 or j = 0: return
if b[i][j] = "↖":
    PRINT-LCS(b, X, i-1, j-1)
    print xᵢ
else if b[i][j] = "↑":
    PRINT-LCS(b, X, i-1, j)
else:
    PRINT-LCS(b, X, i, j-1)

從b[m][n]遞歸回溯至邊界，遇↖輸出字符，即得一個LCS（可能不唯一）。

五、 C 語言完整實現


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

char X[MAX], Y[MAX];
int c[MAX][MAX];
char b[MAX][MAX];

void LCS_LENGTH() {
    int m = strlen(X), n = strlen(Y);
    for (int i = 0; i <= m; i++) c[i][0] = 0;
    for (int j = 0; j <= n; j++) c[0][j] = 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] = '\\';  // ↖
            } else if (c[i-1][j] >= c[i][j-1]) {
                c[i][j] = c[i-1][j];
                b[i][j] = '|';   // ↑
            } else {
                c[i][j] = c[i][j-1];
                b[i][j] = '-';   // ←
            }
        }
    }
    printf("LCS長度: %d\n", c[m][n]);
}

void PRINT_LCS(int i, int j) {
    if (i == 0 || j == 0) return;
    if (b[i][j] == '\\') {
        PRINT_LCS(i-1, j-1);
        putchar(X[i-1]);
    } else if (b[i][j] == '|') {
        PRINT_LCS(i-1, j);
    } else {
        PRINT_LCS(i, j-1);
    }
}

int main() {
    strcpy(X, "BDCABA");
    strcpy(Y, "ABCBDAB");
    LCS_LENGTH();
    printf("一個LCS: ");
    PRINT_LCS(strlen(X), strlen(Y));
    putchar('\n');
    return 0;
}