最长公共子序列。给定两个序列, , 使用动态规划算法求X和Y的最长公共子序列。 要求： （1） 写出递归公式 （2） 分析采用哪种数据结构存储中间结果 （3） 分析求解顺序 （4） 写出算法伪码 （5） 分析算法复杂度 （6） 使用熟悉的编程语言实现算法 （7） 生成测试数据，测试算法的正确性和性能

1. 递归公式：设X和Y分别为两个序列，LCS(i,j)为X[1...i]和Y[1...j]的最长公共子序列长度，则有：

LCS(i,j) = 0 i=0或j=0
LCS(i,j) = LCS(i-1,j-1) + 1 X[i] = Y[j]
LCS(i,j) = max(LCS(i-1,j),LCS(i,j-1)) X[i] != Y[j]

2. 数据结构：可以使用二维数组存储中间结果

3. 求解顺序：从LCS(0,0)开始，按照行优先或列优先的顺序依次计算LCS(i,j)，直到LCS(m,n)

4. 算法伪码：

function LCSLength(X,Y)
m = length(X)
n = length(Y)
let c[0..m, 0..n] be a new array
for i = 0 to m
c[i,0] = 0
for j = 0 to n
c[0,j] = 0
for i = 1 to m
for j = 1 to n
if X[i] = Y[j]
c[i,j] = c[i-1,j-1] + 1
else
c[i,j] = max(c[i,j-1],c[i-1,j])
return c[m,n]

5. 复杂度：最坏情况下时间复杂度为O(mn)

6. 编程语言实现：

def LCSLength(X,Y):
    m = len(X)
    n = len(Y)
    c = [[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]:
                c[i][j] = c[i-1][j-1] + 1
            else:
                c[i][j] = max(c[i-1][j],c[i][j-1])
    return c[m][n]

7. 测试数据：

X = "ABCBDAB"
Y = "BDCABA"
LCSLength(X,Y)  # 输出4