最长公共子序列问题c语言

最长公共子序列问题是一种经典的动态规划问题，可以使用动态规划算法求解。下面是一份使用C语言实现的代码示例：

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

#define MAX_LEN 100

int lcs(char *s1, char *s2, int len1, int len2)
{
    int dp[MAX_LEN][MAX_LEN];
    int i, j;

    for (i = 0; i <= len1; i++) {
        for (j = 0; j <= len2; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            } else if (s1[i-1] == s2[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];
            }
        }
    }

    return dp[len1][len2];
}

int main()
{
    char s1[MAX_LEN], s2[MAX_LEN];
    int len1, len2, result;

    printf("请输入字符串1：");
    scanf("%s", s1);
    printf("请输入字符串2：");
    scanf("%s", s2);

    len1 = strlen(s1);
    len2 = strlen(s2);

    result = lcs(s1, s2, len1, len2);

    printf("最长公共子序列的长度为：%d\n", result);

    return 0;
}

该代码使用二维数组`dp`来记录最长公共子序列的长度。其中`dp[i][j]`表示`s1`的前`i`个字符和`s2`的前`j`个字符的最长公共子序列的长度。如果`s1[i-1]`等于`s2[j-1]`，则`dp[i][j]`等于`dp[i-1][j-1]`加1；否则，`dp[i][j]`等于`dp[i-1][j]`和`dp[i][j-1]`中的较大值。最终，`dp[len1][len2]`即为最长公共子序列的长度。