C语言代码：动态规划法求最长公共子序列问题

在C语言中，动态规划通常用于解决最长公共子序列（Longest Common Subsequence，LCS）问题。这是一个典型的优化问题，可以采用二维数组来存储中间结果并回溯找到最长子序列。

以下是C语言中使用动态规划求解LCS的基本思路和伪代码：

#include <stdio.h>

int lcs(char* str1, char* str2, int m, int n) {
    // 创建一个m+1 x n+1 的二维数组dp
    int dp[m+1][n+1];

    // 初始化所有元素为0，表示两个空字符串的LCS长度为0
    for (int i = 0; i <= m; i++) {
        dp[i][0] = 0;
    }
    for (int j = 0; j <= n; j++) {
        dp[0][j] = 0;
    }

    // 填充dp表
    for (int i = 1; i <= m; i++) { // 遍历str1
        for (int j = 1; j <= n; j++) { // 遍历str2
            if (str1[i-1] == str2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1; // 如果字符匹配，则长度加1
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]); // 否则取最长的前缀
            }
        }
    }

    return dp[m][n]; // 最终返回的值就是LCS的长度
}

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

在这个例子中，`lcs`函数计算了两个输入字符串`str1`和`str2`的最长公共子序列长度。关键步骤是在填充二维数组`dp`的过程中，通过比较当前字符是否相等来决定是否增加长度或选择之前的最长路径。