最长公共子序列动态规划算法c语言

最长公共子序列（Longest Common Subsequence，LCS）问题是指：给定两个序列 X 和 Y，找出它们最长的公共子序列。例如：

X: A B C B D A B
Y: B D C A B A

其中，最长的公共子序列是 BCBA，长度为4。

以下是最长公共子序列的动态规划算法代码：

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

#define MAX_LENGTH 100

int LCS(char *X, char *Y, int m, int n, int c[][MAX_LENGTH])
{
    int i, j;

    // 初始化第一行和第一列
    for (i = 0; i <= m; i++)
        c[i][0] = 0;
    for (j = 0; j <= n; j++)
        c[0][j] = 0;

    // 动态规划求解
    for (i = 1; i <= m; i++) {
        for (j = 1; j <= n; j++) {
            if (X[i-1] == Y[j-1]) // 当前字符相同
                c[i][j] = c[i-1][j-1] + 1;
            else // 当前字符不同
                c[i][j] = (c[i-1][j] > c[i][j-1]) ? c[i-1][j] : c[i][j-1];
        }
    }

    // 返回最长公共子序列的长度
    return c[m][n];
}

int main()
{
    char X[MAX_LENGTH] = "ABCBDAB";
    char Y[MAX_LENGTH] = "BDCABA";
    int m = strlen(X);
    int n = strlen(Y);
    int c[MAX_LENGTH][MAX_LENGTH];
    int len;

    len = LCS(X, Y, m, n, c);

    printf("LCS length: %d\n", len);

    return 0;
}

其中，c数组用于记录X和Y的最长公共子序列长度。在动态规划的过程中，c[i][j]表示X的前i个字符和Y的前j个字符的最长公共子序列长度。

该算法的时间复杂度为O(m*n)，其中m和n分别为X和Y的长度。