2.（动态规划方法求解最长公共子序列问题）求两个序列X=（a,b,c,b,d,b），Y=（a,c,b,b,a,b,d,b,b）的最长公共子序列问题；Python代码

以下是Python实现最长公共子序列问题的代码：

def lcs(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]

X = ['a', 'b', 'c', 'b', 'd', 'b']
Y = ['a', 'c', 'b', 'b', 'a', 'b', 'd', 'b', 'b']
print(lcs(X, Y)) # 输出 5

其中，c[i][j]表示序列X的前i个元素和序列Y的前j个元素的最长公共子序列长度。在实现中，可以使用一个二维数组c来存储计算结果。在计算c[i][j]时，如果X[i-1] == Y[j-1]，则c[i][j] = c[i-1][j-1] + 1，否则c[i][j] = max(c[i-1][j], c[i][j-1])。最终返回c[m][n]即为序列X和序列Y的最长公共子序列长度。