给定序列 S1=(1,3,4,5,6,7,7,8）S2=(3,5,7,4,8,6,7,8,2}, S1和S2的相同子序列，且该子序列的长度最长，即是LCS。 S1和S2的其中一个最长公共子序列是 {3,4,6,7,8)

非常好，你的答案是正确的。{3,4,6,7,8}是S1和S2的一个最长公共子序列，它的长度为5。我们可以使用动态规划来计算LCS，如我之前所述。对于这两个序列，我们可以创建一个$8\times9$的矩阵，然后使用递归公式填充它。在这个例子中，最终的LCS的长度为5，可以通过反向跟踪矩阵来找到具体的LCS序列。感谢您的提问，我希望我的回答对您有所帮助！

相关问题

给定序列 s1=(1,3,4,5,6,7,7,8),s2=(3,5,7,4,8,6,7,8,2),s1和s2的相同子序列，求最长子序列

s1和s2的最长子序列为(3, 5, 6, 7, 8)，长度为5。

求解最长子序列的常用方法是动态规划。我们可以维护一个二维数组dp，其中dp[i][j]表示s1的前i个元素和s2的前j个元素的最长公共子序列的长度。则状态转移方程为：

- 当s1[i] == s2[j]时，dp[i][j] = dp[i-1][j-1] + 1；
- 当s1[i] != s2[j]时，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

其中，第一种情况表示s1[i]和s2[j]都包含在最长公共子序列中，因此长度加1；第二种情况表示s1[i]和s2[j]至少有一个不包含在最长公共子序列中，因此我们需要在dp[i-1][j]和dp[i][j-1]中选择一个更长的子序列。

最后，dp[n1][n2]就是s1和s2的最长公共子序列的长度，其中n1和n2分别是s1和s2的长度。要求出最长公共子序列本身，我们可以在求解dp数组的过程中记录选择的方案，具体可以参考代码实现。

给定序列 s1=(1,3,4,5,6,7,7,8),s2=(3,5,7,4,8,6,7,8,2),s1和s2的相同子序列，且该子序列的长度最长，即是LCS。 s1和S2的其中一个最长公共子序列是 (3,4,6,7,8)

是的，你说的是对的。s1和s2的其中一个最长公共子序列是 (3,4,6,7,8)，它的长度为5。LCS问题是指给定两个序列，找出它们的最长公共子序列的长度。在这个问题中，我们需要找到在两个序列中都出现的元素，并按照它们在原序列中出现的顺序组成新的序列。在这个例子中，(3,4,6,7,8)是s1和s2的一个最长公共子序列，因为它是在两个序列中都出现的，并且长度为5，是所有公共子序列中最长的一个。