用c语言写一个算法分析与设计:动态规划(最长公共子序列)

动态规划是一种通过将大问题分解成小问题并存储解决方案来解决复杂问题的技术，常用于优化和求解最值问题。对于最长公共子序列 (Longest Common Subsequence, LCS) 的经典问题，我们可以使用二维数组来实现动态规划。以下是简单的C语言算法：

#include <stdio.h>

// 定义最大长度
#define MAX_LENGTH 100

// 动态规划函数
int lcs(char* X, char* Y, int m, int n) {
    // 初始化二维数组 dp[m+1][n+1]，所有元素默认为0
    int dp[MAX_LENGTH][MAX_LENGTH] = {0};

    // 遍历X和Y的字符
    for(int i=1; i<=m; i++) {
        for(int j=1; j<=n; j++) {
            // 如果X[i-1] 和 Y[j-1] 相同，则LCS长度加一
            if(X[i-1] == Y[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            // 否则，取之前两个子问题的最大LCS长度
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }

    // 最终结果就是dp[m][n]
    return dp[m][n];
}

// 辅助函数，返回两数中的较大者
int max(int a, int b) {
    return (a > b)? a : b;
}

int main() {
    char X[] = "ABCDGH";
    char Y[] = "AEDFHR";
    int m = strlen(X);
    int n = strlen(Y);

    printf("Length of LCS is %d\n", lcs(X, Y, m, n));

    return 0;
}

在这个程序中，`lcs` 函数计算两个字符串 `X` 和 `Y` 的最长公共子序列。`dp[i][j]` 存储了前 `i` 个 `X` 字符和前 `j` 个 `Y` 字符的最长公共子序列长度。