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

### 回答1：
最长公共子序列是指在两个序列中都出现的最长的子序列。给定序列x和y，要找到它们的最长公共子序列，可以使用动态规划算法。具体来说，可以定义一个二维数组dp，其中dp[i][j]表示序列x的前i个元素和序列y的前j个元素的最长公共子序列的长度。然后，可以按照以下方式递推计算dp数组：

1. 如果xi等于yj，则dp[i][j] = dp[i-1][j-1] + 1；
2. 如果xi不等于yj，则dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

最终，dp[m][n]就是序列x和y的最长公共子序列的长度。要找到具体的最长公共子序列，可以倒序遍历dp数组，根据dp数组的值和递推公式，依次确定最长公共子序列的每个元素。

### 回答2：
最长公共子序列（LCS）是指在两个序列中找到最长的相同子序列，该子序列不需要在原序列中连续出现，只需要保持相对顺序一致即可。

求解最长公共子序列问题的经典算法是动态规划。步骤如下：

1. 设置一个(m+1)*(n+1)的矩阵dp，其中dp[i][j]表示序列x前i个元素和序列y前j个元素的LCS长度。

2. 初始化dp[0][j]=dp[i][0]=0。

3. 从1开始遍历i和j，如果xi=yj，则dp[i][j]=dp[i-1][j-1]+1；否则，dp[i][j]=max(dp[i-1][j],dp[i][j-1])。

4. 最终得到的dp[m][n]即为x和y的LCS长度。

5. 可以通过回溯dp矩阵得到最长公共子序列。从dp[m][n]开始，向左上方查找，每次找到xi=yj时添加到LCS中，直到回溯到dp[0][0]为止。

例如，对于序列x=[1,3,5,7,9]和序列y=[3,5,7,8,9]，动态规划表如下：

0 1 2 3 4 5
0 0 0 0 0 0 0
1 0 0 1 1 1 1
2 0 1 1 2 2 2
3 0 1 1 2 2 2
4 0 1 1 2 2 2
5 0 1 1 2 2 3

dp[5][5]=3，表明x和y的LCS长度为3。回溯得到LCS为[3,5,9]。

总之，动态规划算法是求解最长公共子序列问题的一种可行方法，其时间复杂度为O(mn)。

### 回答3：
最长公共子序列（Longest Common Subsequence，LCS）是求两个序列中最长公共子序列的问题，该问题广泛应用于数据处理、算法设计、生物信息学等领域。

给定两个序列x={x1，x2，…，xm}和y={y1，y2，…，yn}，LCS问题即为在两个序列中查找最长的公共子序列。

为了解决LCS问题，需要使用动态规划（Dynamic Programming）算法，其基本思路为将一个大问题分为多个小问题，并将小问题的解合并起来得到原问题的解。

动态规划算法应用于求解LCS问题的过程如下：

1. 构造一个二维数组C[m+1][n+1]，其中C[i][j]表示序列x中前i个元素与序列y中前j个元素的最长公共子序列的长度。

2. 初始化数组C的边界条件，即C[i][0]=0和C[0][j]=0，其中0<=i<=m, 0<=j<=n。

3. 根据LCS的定义，当xi=yj时，C[i][j]=C[i-1][j-1]+1，否则C[i][j]=max{C[i-1][j],C[i][j-1]}。

4. 得到C[m][n]即为序列x和y的最长公共子序列的长度。

5. 对于C[m][n]中的每个元素，可以根据C[][]数组的值和下标回溯得到最长公共子序列。

例如，对于序列x=“ABCBDAB”和y=“BDCABA”，根据上述动态规划算法求得的C[][]数组如下：

| |B|D|C|A|B|A|
|-|-|-|-|-|-|-|
| |0|0|0|0|0|0|
|A|0|0|0|0|1|1|
|B|0|0|0|0|1|1|
|C|0|0|1|1|1|1|
|B|0|0|1|1|2|2|
|D|0|1|1|1|2|2|
|A|0|1|1|2|2|3|
|B|0|1|1|2|3|3|

可见，序列x和y的最长公共子序列长度为3，即“BCA”。