HDU 1503 最大公共子序列及路徑輸出

題目要求

給定兩個字符串，求其最長公共子序列（LCS）並輸出該子序列（若多解輸出任意一個）。字符串長度 ≤ 100。

DP 狀態與轉移

• dp[i][j]：str1 前 i 字符、str2 前 j 字符的 LCS 長度。
• mark[i][j]：記錄轉移來源，用於回溯輸出路徑。
  • 0：來自 dp[i-1][j-1]（匹配字符）
  • 1：來自 dp[i-1][j]（刪除 str1[i]）
  • 2：來自 dp[i][j-1]（刪除 str2[j]）

轉移方程

if (str1[i-1] == str2[j-1]) {
    dp[i][j] = dp[i-1][j-1] + 1;
    mark[i][j] = 0;
} else if (dp[i-1][j] >= dp[i][j-1]) {
    dp[i][j] = dp[i-1][j];
    mark[i][j] = 1;
} else {
    dp[i][j] = dp[i][j-1];
    mark[i][j] = 2;
}

路徑回溯輸出

遞歸函數 print(i, j)：

• 若 i==0 || j==0 返回。
• 根據 mark[i][j] 遞歸：0→print(i-1,j-1) 輸出 str1[i-1]；1→print(i-1,j)；2→print(i,j-1)。

完整代碼

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

const int MAXL = 110;
char s1[MAXL], s2[MAXL];
int dp[MAXL][MAXL];
int mark[MAXL][MAXL];

void printPath(int i, int j) {
    if (i == 0 || j == 0) return;
    if (mark[i][j] == 0) {
        printPath(i-1, j-1);
        putchar(s1[i-1]);
    } else if (mark[i][j] == 1) {
        printPath(i-1, j);
    } else {
        printPath(i, j-1);
    }
}

int main() {
    while (scanf("%s%s", s1, s2) == 2) {
        int n = strlen(s1), m = strlen(s2);
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i <= n; i++) mark[i][0] = 1;
        for (int j = 0; j <= m; j++) mark[0][j] = 2;
        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;
                    mark[i][j] = 0;
                } else if (dp[i-1][j] >= dp[i][j-1]) {
                    dp[i][j] = dp[i-1][j];
                    mark[i][j] = 1;
                } else {
                    dp[i][j] = dp[i][j-1];
                    mark[i][j] = 2;
                }
            }
        }
        printPath(n, m);
        putchar('\n');
    }
    return 0;
}

複雜度與注意點

• 時間 O(n*m)，空間 O(n*m)，n,m≤100 完全足夠。
• 輸入多組測試數據直到 EOF。
• 若需輸出長度可直接用 dp[n][m]。

總結

經典 LCS 問題，通過 mark 數組記錄決策路徑，遞歸回溯輸出具體子序列。代碼簡潔，是動態規劃路徑重構的標準模板。