最长公共子序列问题C++代码

下面是最长公共子序列问题的动态规划实现C代码：

#include <stdio.h>
#include <string.h>
#define MAX_LENGTH 100

int lcs(char* str1, char* str2, int len1, int len2, int dp[MAX_LENGTH][MAX_LENGTH]) {
    int i, j;

    // 初始化第一行和第一列
    for (i = 0; i <= len1; i++) {
        dp[i][0] = 0;
    }
    for (j = 0; j <= len2; j++) {
        dp[0][j] = 0;
    }

    // 填充dp数组
    for (i = 1; i <= len1; i++) {
        for (j = 1; j <= len2; j++) {
            if (str1[i-1] == str2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = (dp[i][j-1] > dp[i-1][j]) ? dp[i][j-1] : dp[i-1][j];
            }
        }
    }

    // 返回最长公共子序列长度
    return dp[len1][len2];
}

int main() {
    char str1[MAX_LENGTH];
    char str2[MAX_LENGTH];
    int dp[MAX_LENGTH][MAX_LENGTH];
    int len1, len2, lcs_length;

    printf("请输入两个字符串：\n");
    scanf("%s %s", str1, str2);

    len1 = strlen(str1);
    len2 = strlen(str2);

    lcs_length = lcs(str1, str2, len1, len2, dp);

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

    return 0;
}

这个程序会让用户输入两个字符串，然后计算它们的最长公共子序列长度，并输出结果。