使用动态规划算法实现最长公共子序列问题，c语言

下面是使用动态规划算法实现最长公共子序列问题的C语言代码：

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

#define MAXLEN 100

int LCS(char *str1, char *str2, int len1, int len2, int dp[MAXLEN][MAXLEN]) {
    for (int i = 0; i <= len1; i++) {
        for (int j = 0; j <= len2; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            } else if (str1[i - 1] == str2[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 str1[MAXLEN], str2[MAXLEN];
    int dp[MAXLEN][MAXLEN] = {0};
    printf("请输入第一个字符串：");
    scanf("%s", str1);
    printf("请输入第二个字符串：");
    scanf("%s", str2);
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    int lcs_len = LCS(str1, str2, len1, len2, dp);
    printf("最长公共子序列长度为：%d\n", lcs_len);
    return 0;
}

该代码通过一个二维数组`dp`来存储每个子问题的最长公共子序列长度，其中`dp[i][j]`表示`str1[0...i-1]`与`str2[0...j-1]`的最长公共子序列的长度。初始化时，当`i=0`或`j=0`时，最长公共子序列长度为0，即`dp[i][j]=0`。对于其他情况，若`str1[i-1]`与`str2[j-1]`相等，则`dp[i][j]=dp[i-1][j-1]+1`；否则，取`dp[i-1][j]`和`dp[i][j-1]`中的较大值。最后返回`dp[len1][len2]`即可得到最长公共子序列的长度。