给定序列 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)
时间: 2023-09-26 08:07:49 浏览: 20
是的,你说的是对的。s1和s2的其中一个最长公共子序列是 (3,4,6,7,8),它的长度为5。LCS问题是指给定两个序列,找出它们的最长公共子序列的长度。在这个问题中,我们需要找到在两个序列中都出现的元素,并按照它们在原序列中出现的顺序组成新的序列。在这个例子中,(3,4,6,7,8)是s1和s2的一个最长公共子序列,因为它是在两个序列中都出现的,并且长度为5,是所有公共子序列中最长的一个。
相关问题
给定序列 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,3,6,7,8,2},s1和s2的相同子序列,且该子序列的长度最长,即是LCS。s1和s2的 其中一个最长公共子序列是{3,4,6,7,8}建表,画图
好的,下面是s1和s2的LCS的长度以及动态规划表格和对应的状态转移图:
LCS的长度为5。
动态规划表格:
| LCS长度 | 0 | 1 | 2 | 3 | 4 | 5 |
| :---------: | :-: | :-: | :-: | :-: | :-: | :-: |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 | 1 |
| 2 | 0 | 0 | 1 | 1 | 1 | 1 |
| 3 | 0 | 1 | 1 | 1 | 2 | 2 |
| 4 | 0 | 1 | 1 | 2 | 2 | 2 |
| 5 | 0 | 1 | 1 | 2 | 2 | 3 |
| 6 | 0 | 1 | 1 | 2 | 2 | 3 |
| 7 | 0 | 1 | 1 | 2 | 3 | 4 |
| 8 | 0 | 1 | 1 | 2 | 3 | 5 |
状态转移图:
![状态转移图](https://img-blog.csdn.net/20180515141612491?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxMzQ2OTMwOTM2MDkxODk0Mw==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/q/80)