设计最长公共子序列问题的动态规划算法C++

好的，针对你的问题，下面是最长公共子序列问题的动态规划算法C代码实现：

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

#define MAX_LEN 100

int LCS(char *s1, char *s2)
{
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int dp[MAX_LEN][MAX_LEN] = {0};
    int i, j;
    for (i = 1; i <= len1; i++)
    {
        for (j = 1; j <= len2; 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[len1][len2];
}

int main()
{
    char *s1 = "ABCD";
    char *s2 = "BD";
    int length = LCS(s1, s2);
    printf("%d\n", length);
    return 0;
}

在代码实现中，我们利用动态规划的思想求解最长公共子序列问题。具体地，我们将问题划分为若干个子问题，并将已经得到的子问题的结果保存下来，以供后续计算使用。

针对输入的两个字符串s1和s2，我们首先获取它们的长度len1和len2。然后我们定义一个动态规划数组dp，其中dp[i][j]表示s1的前i个字符和s2的前j个字符之间的最长公共子序列的长度。初始时，我们将dp[0][0]设为0，表示空字符串之间的最长公共子序列长度为0；而将dp[0][j]和dp[i][0]都设为0，表示一个非空字符串和一个空字符串之间的最长公共子序列长度也为0。

接下来，我们采用双重循环的方式，遍历s1和s2的每个字符。如果当前s1的第i个字符和s2的第j个字符相等，则说明当前这个字符是它们所共有的，那么它就可以成为它们的最长公共子序列的一部分。此时，我们将dp[i][j]设为dp[i-1][j-1]+1。否则，说明当前这个字符不是它们所共有的，那么我们将在s1的前i-1个字符和s2的前j个字符之间找到一个最长公共子序列，或者在s1的前i个字符和s2的前j-1个字符之间找到一个最长公共子序列，然后取这两个最长公共子序列中的较长者作为它们的最长公共子序列长度。此时，我们将dp[i][j]设为dp[i-1][j]和dp[i][j-1]中的较大值。

最后，我们返回dp[len1][len2]，即s1和s2的最长公共子序列长度。在本例中，我们以字符串"ABCD"和"BD"为例，求它们之间的最长公共子序列长度。运行以上代码，可以得到输出结果2，表明它们之间的最长公共子序列长度为2。