C语言求解最长公共子序列问题，尝试找到不同的最优解代码分析

最长公共子序列问题是指给定两个字符串，求它们的最长公共子序列。算法中主要使用动态规划的思想，具体实现有多种方法。下面分别介绍两种常见的 C 语言求解最长公共子序列问题的方法。

方法一：直接使用动态规划求解

动态规划的思路是：将问题分解成若干个子问题，先求解子问题，再通过子问题的解得到原问题的解。对于最长公共子序列问题，我们可以将两个字符串分别看作一个矩阵，然后通过填表法求解最长公共子序列。

以下是使用动态规划求解最长公共子序列的 C 语言代码：

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

#define MAXLEN 100

int max(int a, int b)
{
    return a > b ? a : b;
}

int lcs(char *str1, char *str2, int m, int n, int dp[MAXLEN + 1][MAXLEN + 1])
{
    int i, j;

    for (i = 0; i <= m; i++) {
        for (j = 0; j <= n; 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] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[m][n];
}

int main()
{
    char str1[MAXLEN + 1] = "ABCBDAB";
    char str2[MAXLEN + 1] = "BDCABA";
    int m = strlen(str1);
    int n = strlen(str2);
    int dp[MAXLEN + 1][MAXLEN + 1];
    int len;

    len = lcs(str1, str2, m, n, dp);

    printf("The length of the longest common subsequence is: %d\n", len);

    return 0;
}

在上面的代码中，我们定义了一个 `lcs` 函数用于求解最长公共子序列。其中，`dp` 数组用于存储子问题的解，`m` 和 `n` 分别表示两个字符串的长度。在函数中，我们使用两个嵌套循环遍历整个矩阵，并根据当前位置的字符是否相同，来决定如何填表。最终，返回 `dp[m][n]` 即为最长公共子序列的长度。

方法二：使用递归优化动态规划

上面的代码中，我们使用了二维数组来存储子问题的解，在空间上需要开辟额外的存储空间。为了优化空间复杂度，我们可以使用递归来实现动态规划。具体实现方法是：在递归过程中，每次只需要计算当前状态的解，不需要存储之前的状态，从而达到优化空间的目的。

以下是使用递归优化动态规划求解最长公共子序列的 C 语言代码：

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

int max(int a, int b)
{
    return a > b ? a : b;
}

int lcs(char *str1, char *str2, int m, int n)
{
    if (m == 0 || n == 0) {
        return 0;
    } else if (str1[m - 1] == str2[n - 1]) {
        return lcs(str1, str2, m - 1, n - 1) + 1;
    } else {
        return max(lcs(str1, str2, m - 1, n), lcs(str1, str2, m, n - 1));
    }
}

int main()
{
    char str1[] = "ABCBDAB";
    char str2[] = "BDCABA";
    int m = strlen(str1);
    int n = strlen(str2);
    int len;

    len = lcs(str1, str2, m, n);

    printf("The length of the longest common subsequence is: %d\n", len);

    return 0;
}

在上面的代码中，我们定义了一个 `lcs` 函数用于求解最长公共子序列。在函数中，我们通过递归的方式计算当前状态的解。由于每次只计算当前状态的解，因此不需要开辟额外的存储空间。最终，返回的结果即为最长公共子序列的长度。

总结

以上是两种常见的 C 语言求解最长公共子序列问题的方法。方法一使用动态规划，时间复杂度为 O(mn)，空间复杂度为 O(mn)；方法二使用递归优化动态规划，时间复杂度为 O(2^n)，空间复杂度为 O(1)。在实际应用中，我们需要根据具体情况选择合适的算法。