3. 用动态规划解决最长公共子序列问题。 (15分)
时间: 2023-06-26 16:09:13 浏览: 62
最长公共子序列问题是指,给定两个序列(可以是字符串、数组等),求它们最长的公共子序列的长度。一个序列的子序列是从原序列中删除一些元素(可以不连续)而不改变其余元素顺序得到的序列。
动态规划算法可以解决最长公共子序列问题。假设要求的两个序列为a和b,它们的长度分别为m和n。设dp[i][j]表示a[0:i]和b[0:j]的最长公共子序列长度,则有以下状态转移方程:
- 当a[i] = b[j]时,dp[i][j] = dp[i-1][j-1] + 1;
- 当a[i] ≠ b[j]时,dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
最终的答案即为dp[m-1][n-1]。
下面是Python代码实现:
```python
def longest_common_subsequence(a, b):
m, n = len(a), len(b)
dp = [[0] * (n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if a[i-1] == b[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]
# 测试
a = "abcde"
b = "ace"
print(longest_common_subsequence(a, b)) # 输出3,即"ace"是两个序列的最长公共子序列
```
时间复杂度为O(mn),空间复杂度也为O(mn)。