最長公共子序列（LCS）動態規劃算法C語言實現詳解

最長公共子序列（LCS）動態規劃算法C語言實現詳解

給定兩字符串 X、Y，求最長公共子序列長度。子序列不要求連續，但順序保持。

動態規劃狀態定義

dp[i][j] 表示 X[0..i-1] 和 Y[0..j-1] 的 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])

完整代碼

#include <stdio.h>
#include <string.h>
#define N 2000
int dp[N][N];
char a[N], b[N];

int main() {
    while (scanf("%s%s", a, b) != EOF) {
        memset(dp, 0, sizeof(dp));
        int m = strlen(a), n = strlen(b);
        for (int i=1; i<=m; i++)
            for (int j=1; j<=n; j++)
                if (a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = dp[i-1][j] > dp[i][j-1] ? dp[i-1][j] : dp[i][j-1];
        printf("%d\n", dp[m][n]);
    }
    return 0;
}

示例追蹤

a=abcfbc, b=abfcab，DP 表最終 dp[6][6]=4，對應 LCS "abfb" 或 "abcb" 等。