用动态规划法求解公共子序列问题c语言

公共子序列问题是指给定两个序列S1和S2，找到它们的最长公共子序列。以下是使用动态规划法求解公共子序列问题的C语言代码：

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

// 定义最大字符串长度
#define MAX_LEN 100

// 动态规划求解最长公共子序列
int lcs(char *s1, char *s2, int m, int n)
{
    int dp[MAX_LEN][MAX_LEN];
    int i, j;

    // 初始化dp数组
    for (i = 0; i <= m; i++)
        dp[i][0] = 0;
    for (j = 0; j <= n; j++)
        dp[0][j] = 0;

    // 动态规划求解
    for (i = 1; i <= m; i++) {
        for (j = 1; j <= n; j++) {
            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[m][n];
}

int main()
{
    char s1[MAX_LEN], s2[MAX_LEN];
    int m, n;

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

    m = strlen(s1);
    n = strlen(s2);

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

    return 0;
}

在上述代码中，我们定义了一个MAX_LEN常量表示最大字符串长度，用于定义dp数组的大小。函数lcs用于计算最长公共子序列的长度，其中dp数组表示长度为i和j的两个子序列的最长公共子序列长度。在函数lcs中，我们使用两个循环遍历序列s1和s2，如果当前字符相同，则在dp[i-1][j-1]的基础上加1；否则，取dp[i-1][j]和dp[i][j-1]中的较大值。最后，返回dp[m][n]即可得到最长公共子序列的长度。