编程要求 求字符串序列“ABCDBAB”和“BDCABA”的最长公共子序列 解题思路： 递推关系分析： 设 A=“a0，a1，…，am−1”，B=“b0，b1，…，bn−1”，Z=“z0,z1,…,zk−1” 为它们的最长公共子序列。 有以下结论： 1）如果am−1=bn−1,则zk−1=am−1=bn−1,且“z0,z1,…,zk−2”是“a0,a1,…,am−2”和“b0,b1,…,bn−2”的一个最长公共子序列； 2）如果am−1​=bn−1，则若zk−1​=am−1，蕴涵“z0，z1，…，zk−1”是“a0,a1,…,am−2”和“b0,b1,…,bn−1”的一个最长公共子序列； 3）如果am−1​=bn−1，则若zk−1​=bn−1，蕴涵“z0，z1，…，zk−1”是“a0，a1，…，am−1”和“b0，b1，…，bn−2”的一个最长公共子序列。 定义c[i][j]为序列“a0,a1,…,ai−1”和“b0,b1,…,bj−1”的最长公共子序列的长度，计算c[i][j]可递归地表述如下： 1）c[i][j]=0 如果i=0或j=0； 2）c[i][j]=c[i−1][j−1]+1 如果i,j>0,且a[i−1]=b[j−1]； 3）c[i][j]=max(c[i][j−1],c[i−1][j]) 如果i,j>0,且a[i−1]​=b[j−1]。 由二维数组c的递归定义，c[i][j]的结果依赖于c[i−1][j−1]，c[i−1][j]和c[i][j−1]。可以从c[m][n]开始，跟踪c[i][j]结果的产生过程，从而逆向构造出最长公共子序列。 测试说明 平台会对你编写的代码进行测试： 测试输入： a=“ABCDBAB” b=“BDCABA” 输出示例： BCBA

以下是Python代码实现：

def lcs(a, b):
    m, n = len(a), len(b)
    c = [[0] * (n+1) for i in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if a[i-1] == b[j-1]:
                c[i][j] = c[i-1][j-1] + 1
            else:
                c[i][j] = max(c[i][j-1], c[i-1][j])
    res = ""
    i, j = m, n
    while i > 0 and j > 0:
        if a[i-1] == b[j-1]:
            res = a[i-1] + res
            i -= 1
            j -= 1
        elif c[i-1][j] > c[i][j-1]:
            i -= 1
        else:
            j -= 1
    return res

a = "ABCDBAB"
b = "BDCABA"
print(lcs(a, b)) # output: BCBA