c++算法写最长公共子序列

最长公共子序列问题是一个经典的动态规划问题。假设有两个序列 $A=a_1,a_2,...,a_m$ 和 $B=b_1,b_2,...,b_n$，求它们的最长公共子序列（LCS）。

定义 $c[i][j]$ 为序列 $A$ 的前 $i$ 个元素和序列 $B$ 的前 $j$ 个元素的 LCS 的长度。则有以下递推公式：

$c[i][j]=\begin{cases}
0, & i=0 \text{ or } j=0 \\
c[i-1][j-1]+1, & a_i=b_j \\
\max(c[i-1][j],c[i][j-1]), & a_i \neq b_j
\end{cases}$

其中 $c[i-1][j-1]+1$ 表示如果 $a_i=b_j$，那么 $a_i$ 和 $b_j$ 必然是 LCS 的一部分，所以 LCS 长度加 $1$；$\max(c[i-1][j],c[i][j-1])$ 表示如果 $a_i \neq b_j$，则 $a_i$ 和 $b_j$ 不可能同时出现在 LCS 中，所以 LCS 的长度就是序列 $A$ 的前 $i-1$ 个元素和序列 $B$ 的前 $j$ 个元素的 LCS 的长度，以及序列 $A$ 的前 $i$ 个元素和序列 $B$ 的前 $j-1$ 个元素的 LCS 的长度的最大值。

最终的 LCS 长度即为 $c[m][n]$。而要得到 LCS 的具体内容，可以倒着遍历 $c$ 数组，按照递推公式的规则向左上方移动，并记录下相同的字符即可。

下面是 C 语言代码实现：

#include <stdio.h>
#include <string.h>

#define MAXLEN 100

int max(int a, int b) {
    return a > b ? a : b;
}

void LCS(char* A, char* B, int m, int n, int c[][MAXLEN]) {
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (A[i - 1] == B[j - 1]) {
                c[i][j] = c[i - 1][j - 1] + 1;
            } else {
                c[i][j] = max(c[i - 1][j], c[i][j - 1]);
            }
        }
    }
}

void printLCS(char* A, int m, int n, int c[][MAXLEN]) {
    char lcs[MAXLEN];
    int len = 0;

    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (A[i - 1] == A[j - 1]) {
            lcs[len++] = A[i - 1];
            i--;
            j--;
        } else if (c[i - 1][j] > c[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }

    printf("LCS: ");
    for (int k = len - 1; k >= 0; k--) {
        printf("%c", lcs[k]);
    }
    printf("\n");
}

int main() {
    char A[] = "ABCBDAB";
    char B[] = "BDCABA";

    int m = strlen(A);
    int n = strlen(B);

    int c[MAXLEN][MAXLEN] = {0};
    LCS(A, B, m, n, c);

    printf("LCS length: %d\n", c[m][n]);
    printLCS(A, m, n, c);

    return 0;
}

输出结果为：

LCS length: 4
LCS: BCBA