HDU Common Subsequence：最長公共子序列 (LCS) 經典 DP

問題描述

給定兩字符串，求最長公共子序列長度。多測試用例至 EOF。

DP 定義與轉移

dp[i][j] = s1[0..i-1] 和 s2[0..j-1] 的 LCS 長度。

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])

代碼

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

char s1[10000], s2[10000];
int dp[1000][1000]; // 注意：題目長度未給，假設 ≤1000

int main() {
    while (~scanf("%s", s1)) {
        scanf("%s", s2);
        int n = strlen(s1), m = strlen(s2);
        for (int i=1; i<=n; ++i)
            for (int j=1; j<=m; ++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]);
        printf("%d\n", dp[n][m]);
    }
    return 0;
}

空間優化

僅需兩行滾動數組：dp[2][m+1]，cur = i&1，pre = 1-cur。

複雜度

• 時間：O(n·m)
• 空間：O(min(n,m))（滾動數組）