python动态规划策略实现最长公共子序列。 最长公共子序列问题:对两个类型相同的序列(输入),用动态规划方法计算他们的最长公共子序列,并输出最长公共子序列的长度值。
时间: 2023-08-13 20:31:51 浏览: 34
好的,这是一个经典的动态规划问题,最长公共子序列(LCS)问题。以下是 Python 代码实现:
```python
def lcs(X, Y):
# 创建一个二维数组
m = len(X)
n = len(Y)
L = [[None]*(n+1) for i in range(m+1)]
# 填充L [i] [0] = 0 和 L [0] [j] = 0
for i in range(m+1):
for j in range(n+1):
if i == 0 or j == 0:
L[i][j] = 0
# 填充L [i] [j],如果X [i-1] == Y [j-1],则L [i] [j] = L [i-1] [j-1] +1,否则L [i] [j] = max(L [i-1] [j],L [i] [j-1])
for i in range(1, m+1):
for j in range(1, n+1):
if X[i-1] == Y[j-1]:
L[i][j] = L[i-1][j-1] + 1
else:
L[i][j] = max(L[i-1][j], L[i][j-1])
# L [m] [n]存储LCS的长度值
return L[m][n]
```
这个函数接受两个序列 X 和 Y 作为输入,并返回它们的最长公共子序列的长度。
相关推荐
![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_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)
![](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)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![py](https://img-home.csdnimg.cn/images/20210720083646.png)