HDU 1159 最長公共子序列 (LCS) 動態規劃標準解法

問題描述

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

動態規劃模型

• 狀態定義：c[i][j] 表示 a[0..i-1] 與 b[0..j-1] 的 LCS 長度。
• 轉移方程：
  • a[i-1] == b[j-1]：c[i][j] = c[i-1][j-1] + 1
  • 否則：c[i][j] = max(c[i-1][j], c[i][j-1])
• 邊界：c[0][*] = c[*][0] = 0。
• 答案：c[m][n]（或矩陣中最大值，兩者等價）。

代碼實現

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

#define M 1000
#define N 1000
int c[M][N];

int lcs_len(char *a, char *b)
{
    int m = strlen(a), n = strlen(b), i, j;
    for (i = 0; i <= m; ++i)
        for (j = 0; j <= n; ++j)
            c[i][j] = 0;

    for (i = 1; i <= m; i++) {
        for (j = 1; j <= n; j++) {
            if (a[i-1] == b[j-1])
                c[i][j] = c[i-1][j-1] + 1;
            else if (c[i-1][j] > c[i][j-1])
                c[i][j] = c[i-1][j];
            else
                c[i][j] = c[i][j-1];
        }
    }
    return c[m][n];
}

int main()
{
    char a[M], b[M];
    while (cin >> a >> b)
        cout << lcs_len(a, b) << endl;
    return 0;
}

複雜度

• 時間 O(m×n) = 10⁶ 操作，極快。
• 空間 O(m×n) = 4 MB（int[1000][1000]），符合限制。可優化至 O(min(m,n)) 滾動數組。

常見變體

1. 輸出 LCS 序列本身：從 c[m][n] 回溯構造。
2. 最長公共子串：要求連續，轉移方程改為 a[i-1]==b[j-1] ? c[i-1][j-1]+1 : 0。
3. 編輯距離：允許增刪改，經典 Levenshtein 距離 DP。