头歌求字符串序列“abcdbab”和“bdcaba”的最长公共子序列的代码
时间: 2023-10-20 19:05:30 浏览: 59
好的,以下是Python代码实现:
```python
def longest_common_subsequence(s1, s2):
m, n = len(s1), len(s2)
dp = [[0] * (n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
s1 = "abcdbab"
s2 = "bdcaba"
print(longest_common_subsequence(s1, s2))
```
输出结果为 4,即最长公共子序列的长度。
相关问题
头歌求字符串序列“abcdbab”和“bdcaba”的最长公共子序列
我们可以使用动态规划算法来求解这个问题。
首先,定义状态:令 dp[i][j] 表示字符串 s1 的前 i 个字符和字符串 s2 的前 j 个字符的最长公共子序列长度。
然后,初始化状态:dp[0][j] 和 dp[i][0] 均为 0。
接着,考虑状态转移方程:
当 s1[i-1] == s2[j-1] 时,dp[i][j] = dp[i-1][j-1] + 1;
当 s1[i-1] != s2[j-1] 时,dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
最后,最长公共子序列的长度即为 dp[n][m],其中 n 和 m 分别是字符串 s1 和 s2 的长度。
按照上述算法,我们可以得到以下动态规划表格:
| dp | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| :----: | - | - | - | - | - | - | - |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 2 | 0 | 1 | 1 | 1 | 1 | 2 | 2 |
| 3 | 0 | 1 | 1 | 1 | 2 | 2 | 2 |
| 4 | 0 | 1 | 2 | 2 | 2 | 2 | 2 |
| 5 | 0 | 1 | 2 | 2 | 3 | 3 | 3 |
| 6 | 0 | 1 | 2 | 2 | 3 | 3 | 4 |
因此,字符串序列“abcdbab”和“bdcaba”的最长公共子序列长度为 4,即序列“bcba”。
求字符串序列“ABCDBAB”和“BDCABA”的最长公共子序列
这是一个经典的动态规划问题,可以使用动态规划算法来求解。
首先,定义一个二维数组dp,其中dp[i][j]表示序列1中前i个字符和序列2中前j个字符的最长公共子序列的长度。
然后,我们可以通过以下公式来计算dp[i][j]的值:
如果序列1的第i个字符等于序列2的第j个字符,则dp[i][j] = dp[i-1][j-1] + 1。
如果序列1的第i个字符不等于序列2的第j个字符,则dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
最后,dp[len1][len2]即为所求的最长公共子序列的长度,其中len1和len2分别为序列1和序列2的长度。
对于字符串序列“ABCDBAB”和“BDCABA”,可以通过动态规划算法求得它们的最长公共子序列为“BCBA”,其长度为4。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)