若X={A,B,C,B,D,A,B} ,Y={B,D,C,A,B,A} 试用动态规划法计算其最长公共子序列,用代码写出
时间: 2023-10-03 10:02:44 浏览: 38
动态规划的思路是建立一个二维数组dp,其中dp[i][j]表示X的前i个元素和Y的前j个元素的最长公共子序列的长度。边界条件为dp[0][j]=0和dp[i][0]=0,表示当其中一个序列为空时,最长公共子序列的长度为0。当X[i]=Y[j]时,dp[i][j]=dp[i-1][j-1]+1,表示当前元素匹配成功,最长公共子序列的长度加1;否则,dp[i][j]=max(dp[i-1][j],dp[i][j-1]),表示当前元素匹配失败,最长公共子序列的长度等于X的前i-1个元素和Y的前j个元素的最长公共子序列长度以及X的前i个元素和Y的前j-1个元素的最长公共子序列长度的较大值。
根据上述思路,可以写出如下代码:
```python
def longest_common_subsequence(X, Y):
m, n = len(X), len(Y)
dp = [[0] * (n + 1) for _ in range(m + 1)]
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])
return dp[m][n]
X = ['A', 'B', 'C', 'B', 'D', 'A', 'B']
Y = ['B', 'D', 'C', 'A', 'B', 'A']
print(longest_common_subsequence(X, Y)) # 输出4
```
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.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)
![](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)