HDU 1159 最大公共子序列 (LCS)：经典 DP 详解

题目大意

给定两字符串，求最长公共子序列（LCS）长度。多测试用例，至 EOF。

DP 状态与转移

dp[i][j]：s1[0..i-1] 与 s2[0..j-1] 的 LCS 长度。
转移：

• s1[i-1] == s2[j-1]：dp[i][j] = dp[i-1][j-1] + 1
• 否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

图解

C 语言实现

#include 
#include 
#define MAX(a,b) ((a)>(b)?(a):(b))

char s[520], t[520];
int dp[520][520];

int lcs(int n, int m) {
    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j)
            if (s[i-1]==t[j-1]) dp[i][j]=dp[i-1][j-1]+1;
            else dp[i][j]=MAX(dp[i-1][j], dp[i][j-1]);
    return dp[n][m];
}

int main() {
    while (scanf("%s%s", s, t) != EOF) {
        int n=strlen(s), m=strlen(t);
        memset(dp, 0, sizeof(dp));
        printf("%d\n", lcs(n, m));
    }
    return 0;
}

复杂度

• 时间：O(n·m) ≤ 500² = 250,000
• 空间：O(n·m)，可优化为 O(min(n,m)) 滚动数组

扩展：输出 LCS 序列

void printLCS(int i, int j) {
    if (i==0 || j==0) return;
    if (s[i-1]==t[j-1]) { printLCS(i-1,j-1); putchar(s[i-1]); }
    else if (dp[i-1][j] > dp[i][j-1]) printLCS(i-1,j);
    else printLCS(i,j-1);
}