给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列

最长公共子序列（Longest Common Subsequence，LCS）是指在两个序列中以相同顺序出现，长度最长的子序列。

可以使用动态规划算法来解决此问题。假设X和Y的长度分别为m和n，则构建一个(m+1)×(n+1)的二维数组dp，其中dp[i][j]表示X前i个元素和Y前j个元素的LCS的长度。

当i=0或j=0时，dp[i][j]=0，因为其中一个序列为空，它们的LCS长度为0。

当xi=yj时，dp[i][j]=dp[i-1][j-1]+1，因为xi和yj都在LCS中。

当xi≠yj时，dp[i][j]=max(dp[i-1][j], dp[i][j-1])，因为xi和yj至少有一个不在LCS中，所以LCS长度为X前i-1个元素和Y前j个元素的LCS长度或X前i个元素和Y前j-1个元素的LCS长度的最大值。

最终，dp[m][n]即为X和Y的LCS的长度。

要找出LCS本身，可以从dp[m][n]开始，如果xi=yj，则该元素在LCS中，将其加入结果序列中，并向左上方移动一步；否则，如果dp[i-1][j]>dp[i][j-1]，则向上方移动一步；否则，向左方移动一步。重复此过程，直到回到dp[0][0]。

下面是Python代码实现：

def lcs(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])
    # 构造LCS
    i, j = m, n
    lcs = []
    while i > 0 and j > 0:
        if X[i-1] == Y[j-1]:
            lcs.append(X[i-1])
            i -= 1
            j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    lcs.reverse()
    return dp[m][n], lcs

例如，对于X={A,B,C,B,D,A,B}和Y={B,D,C,A,B,A}，运行lcs(X,Y)将返回(4, ['B', 'C', 'B', 'A'])，其中4是LCS的长度，['B', 'C', 'B', 'A']是LCS本身。