HDOJ 1159 Common Subsequence：最長公共子序列 (LCS) 經典動態規劃

題目大意

給定兩個字符串 X、Y，求其最長公共子序列（LCS）的長度。子序列不要求連續，只需保持相對順序。多組測試數據，直到 EOF。

動態規劃解法

狀態定義

dp[i][j]：X 的前 i 個字符與 Y 的前 j 個字符的 LCS 長度。

轉移方程

• 若 X[i-1] == Y[j-1]：dp[i][j] = dp[i-1][j-1] + 1
• 否則：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

初始化與邊界

dp[0][*] = dp[*][0] = 0。雙重循環填表，最終答案 dp[len1][len2]。

完整代碼

#include <stdio.h>
#include <string.h>
#define max(a,b) (a>b?a:b)
int dp[1010][1010], len1, len2;
char s1[1010], s2[1010];

void LCS() {
    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (s1[i-1] == s2[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
}

int main() {
    while (scanf("%s%s", s1, s2) != EOF) {
        len1 = strlen(s1);
        len2 = strlen(s2);
        LCS();
        printf("%d\n", dp[len1][len2]);
    }
    return 0;
}

複雜度分析

• 時間：O(len1 × len2)，最大 1000×1000 = 10^6，極快。
• 空間：O(len1 × len2) 整型數組，約 4MB，符合限制。

優化方向

空間可優化至 O(min(len1, len2))，只保留前一行；若需輸出具體 LCS，需回溯或存儲方向。

經典應用

LCS 是字符串匹配、版本控制、生物信息學序列比對的核心算法，必須熟練掌握。