最长公共子序列算法C语言

最长公共子序列（Longest Common Subsequence，LCS）算法是一种用于找出两个序列中最长共同部分的动态规划算法。在C语言中，你可以通过以下几个步骤实现：

1. 定义一个二维数组dp，其大小为(m+1) x (n+1)，其中m和n分别是输入序列的长度。

2. 初始化dp数组的第一行和第一列为0，因为单独的一个字符的子序列总是包含它自身，所以最短长度为0。

3. 使用两层循环遍历输入序列a和b：
- 如果a[i]等于b[j]，则dp[i][j] = dp[i-1][j-1] + 1（相同的字符添加到公共子序列，长度加1）。
- 否则，dp[i][j]取dp[i-1][j]和dp[i][j-1]中的较大值，表示不包括当前字符的最长公共子序列长度。

4. 当完成所有计算后，dp[m][n]就是两个序列的最长公共子序列的长度。为了获取实际的子序列，可以回溯dp数组，从dp[m][n]开始，向左上方移动，遇到相等的字符就添加到结果串中。

5. 实现过程中注意存储每个节点的选择过程（即哪些字符被选入子序列），以便最后构造出完整的子序列。

下面是一个简单的C语言伪代码示例：

#include <stdio.h>
int lcs(char* a, char* b, int m, int n);

int main() {
    char a[] = "ABCDGH";
    char b[] = "AEDFHR";
    int len = lcs(a, b, strlen(a), strlen(b));
    printf("Length of LCS is %d\n", len);
    return 0;
}

// LCS function implementation
int lcs(char* a, char* b, int m, int n) {
    int dp[m+1][n+1];
    // ... fill dp matrix and backtrack to get LCS
    return dp[m][n];
}