请用动态规划算法完成最长公共子序列问题程序,并通过测试
时间: 2023-06-26 21:10:17 浏览: 34
好的,以下是我给你编写的Python程序:
```python
def lcs(X, Y):
m = len(X)
n = len(Y)
# 创建 DP 表格
dp = [[0] * (n+1) for _ in range(m+1)]
# 填充 DP 表格
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
while i > 0 and j > 0:
if X[i-1] == Y[j-1]:
lcs = X[i-1] + lcs
i -= 1
j -= 1
elif dp[i-1][j] > dp[i][j-1]:
i -= 1
else:
j -= 1
return lcs
# 测试
X = 'AGGTAB'
Y = 'GXTXAYB'
print("最长公共子序列为", lcs(X, Y))
```
输出结果为:
```
最长公共子序列为 GTAB
```
程序通过了测试,可以正确地求解最长公共子序列问题。
相关推荐
![](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)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)