第2关：最长公共子序列问题：求最长公共子序列。 要求：采用动态规划算法求解以上问题。 1、请用伪码描述该算法。 2、请截图显示实现该算法的c语言代码。 3、请写出动态规划数组和决策数组的值（如果使用了决策数组）。

第2关：最长公共子序列（Longest Common Subsequence, LCS）问题可以使用动态规划解决。以下是使用伪代码描述的算法：

function lcs(X, Y):
    m = length of X
    n = length of Y

    dp = array of size (m+1) x (n+1) filled with zeros
    for i from 1 to m:
        for j from 1 to n:
            if X[i] == Y[j]:
                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]

对于C语言的实现，以下是基本版本的代码：

#include <stdio.h>

int lcs(char *X, char *Y, int m, int n) {
    int dp[m + 1][n + 1];

    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                dp[i][j] = 0;
            else if (X[i - 1] == Y[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = (dp[i - 1]) ? dp[i - 1][j] : dp[i][j - 1];
        }
    }

    return dp[m][n];
}

// 主函数用于测试
int main() {
    // 请替换实际字符串X和Y
    char X[] = "ABCBDAB";
    char Y[] = "BDCAB";

    int m = strlen(X);
    int n = strlen(Y);

    printf("Length of the Longest Common Subsequence: %d\n", lcs(X, Y, m, n));
    return 0;
}

在这个例子中，动态规划数组`dp[i][j]`存储了前`i`个字符的X与前`j`个字符的Y的最长公共子序列长度。决策过程就是基于当前字符是否相等来更新最长公共子序列的长度。