动态规划最长公共子序列算法代码
时间: 2023-07-08 07:35:32 浏览: 51
以下是动态规划最长公共子序列的算法代码,时间复杂度为 O(mn):
```python
def lcs_dp(str1, str2):
m, n = len(str1), len(str2)
dp = [[0] * (n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if str1[i-1] == str2[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]
```
其中,`dp[i][j]` 表示 `str1` 的前 `i` 个字符和 `str2` 的前 `j` 个字符的最长公共子序列长度。当 `str1[i-1] == str2[j-1]` 时,它可以由 `dp[i-1][j-1]` 增加一位字符得到;否则,它可以由 `dp[i-1][j]` 或 `dp[i][j-1]` 中的较大值得到。最终返回 `dp[m][n]` 即可得到最长公共子序列的长度。
相关问题
最长公共子序列动态规划改进算法代码
最长公共子序列(Longest Common Subsequence,简称LCS)是一种经典的动态规划问题。下面是一种改进的动态规划算法代码:
```python
def lcs_dp(s1, s2):
m = len(s1)
n = 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])
# 构造最长公共子序列
lcs = ""
i, j = m, n
while i > 0 and j > 0:
if s1[i - 1] == s2[j - 1]:
lcs = s1[i - 1] + lcs
i -= 1
j -= 1
elif dp[i - 1][j] > dp[i][j - 1]:
i -= 1
else:
j -= 1
return lcs
# 示例调用
s1 = "ABCD"
s2 = "ACDF"
result = lcs_dp(s1, s2)
print("最长公共子序列:", result)
```
动态规划求最长公共子序列算法设计
态规划求最长公共子序列算法设计如下:
1. 定义状态:设dp[i][j]为字符串A的前i个字符和字符串B的前j个字符的最长公共子序列长度。
2. 状态转移方程:当A[i] == B[j]时,dp[i][j] = dp[i-1][j-1] + 1;否则,dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
3. 边界条件:dp[j] = dp[i] = 0。
4. 最终结果:dp[m][n],其中m和n分别为字符串A和B的长度。
下面是Python代码实现:
```python
def lcs(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]
```