C语言用动态规划找出最长公共子序列

动态规划（Dynamic Programming）是一种常用的求解最优化问题的算法，它通常用于求解具有重叠子问题和最优子结构性质的问题。其中求最长公共子序列（Longest Common Subsequence，简称LCS）是一个经典的动态规划问题，其求解过程如下：

假设有两个字符串s1和s2，其长度分别为n1和n2，我们需要找出它们的最长公共子序列。

1. 定义状态：定义dp[i][j]表示s1的前i个字符和s2的前j个字符的最长公共子序列的长度。

2. 状态转移方程：当s1[i-1]等于s2[j-1]时，dp[i][j] = dp[i-1][j-1] + 1；否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

3. 初始化状态：dp[0][j]和dp[i][0]均为0。

4. 求解目标：dp[n1][n2]即为s1和s2的最长公共子序列的长度。

下面是C语言实现代码：

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

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

int LCS(char s1[], char s2[], int n1, int n2) {
    int dp[n1+1][n2+1];
    memset(dp, 0, sizeof(dp)); // 初始化状态

    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; j++) {
            if (s1[i-1] == s2[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[n1][n2]; // 求解目标
}

int main() {
    char s1[] = "ABCBDAB";
    char s2[] = "BDCABA";
    int n1 = strlen(s1);
    int n2 = strlen(s2);
    int lcs = LCS(s1, s2, n1, n2);
    printf("LCS: %d\n", lcs);
    return 0;
}

输出：

LCS: 4

其中，输入的两个字符串s1和s2分别为"ABCBDAB"和"BDCABA"，它们的最长公共子序列为"BCBA"，长度为4。