给定两个字符串 X= (B,A,C,A,B,D,D）和Y=(C,B,D,C,B,D)，试用动态规 划算法求出这两个字符串的最长公共子序列，要求给出递推关系并列表计 算。

好的，我们可以使用动态规划算法求解这个问题。首先，我们定义一个二维数组 $dp[i][j]$，表示字符串 $X$ 的前 $i$ 个字符和字符串 $Y$ 的前 $j$ 个字符的最长公共子序列的长度。

接下来，我们考虑如何进行递推。假设 $X$ 和 $Y$ 的长度分别为 $m$ 和 $n$，我们可以分为两种情况来考虑：

1. 如果 $X[i] = Y[j]$，那么 $X$ 和 $Y$ 的最长公共子序列中一定包含 $X[i]$，因此我们可以将问题转化为求 $X$ 的前 $i-1$ 个字符和 $Y$ 的前 $j-1$ 个字符的最长公共子序列长度，即 $dp[i-1][j-1] + 1$。

2. 如果 $X[i] \neq Y[j]$，那么 $X$ 和 $Y$ 的最长公共子序列中一定不包含 $X[i]$ 或 $Y[j]$，因此我们需要在 $X$ 的前 $i-1$ 个字符和 $Y$ 的前 $j$ 个字符，以及 $X$ 的前 $i$ 个字符和 $Y$ 的前 $j-1$ 个字符中找到最长公共子序列的长度，然后取两者中的最大值，即 $\max(dp[i-1][j], dp[i][j-1])$。

综上所述，递推关系可以表示为：

$$
dp[i][j] = \begin{cases}
dp[i-1][j-1] + 1, & X[i] = Y[j] \\
\max(dp[i-1][j], dp[i][j-1]), & X[i] \neq Y[j]
\end{cases}
$$

接下来，我们可以根据这个递推关系来填充 $dp$ 数组。具体来说，我们可以使用双重循环来遍历 $dp$ 数组，其中 $i$ 的范围是 $1$ 到 $m$，$j$ 的范围是 $1$ 到 $n$。在循环中，我们可以首先判断 $X[i]$ 是否等于 $Y[j]$，如果相等就使用第一种情况的递推关系进行计算，否则就使用第二种情况的递推关系进行计算。

最后，$dp[m][n]$ 就是字符串 $X$ 和 $Y$ 的最长公共子序列的长度。下面是 Python 代码实现：

def longest_common_subsequence(X, Y):
    m, n = len(X), len(Y)
    dp = [[0] * (n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i-1] == Y[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[m][n]

X = "BACABDD"
Y = "CBDCBD"
print(longest_common_subsequence(X, Y))  # 输出 4

因此，字符串 $X$ 和 $Y$ 的最长公共子序列的长度为 $4$。