用python语言实现“最长公共子序列”问题的动态规划算法
时间: 2023-04-24 17:07:15 浏览: 81
最长公共子序列问题的动态规划算法可以用Python语言实现。具体步骤如下:
1. 定义一个二维数组dp,其中dp[i][j]表示字符串A的前i个字符和字符串B的前j个字符的最长公共子序列的长度。
2. 初始化dp数组的第一行和第一列,即dp[0][j]和dp[i][0]都为0,因为一个字符串的空子序列和另一个字符串的任何子序列都没有公共部分。
3. 对于字符串A和字符串B的每个字符,如果它们相等,则dp[i][j] = dp[i-1][j-1] + 1,因为它们可以构成一个新的公共子序列;否则,dp[i][j] = max(dp[i-1][j], dp[i][j-1]),因为它们不能同时出现在最长公共子序列中,所以要取它们的最大值。
4. 最终的结果为dp[m][n],其中m和n分别为字符串A和字符串B的长度。
下面是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 = "ABCD"
B = "ACDF"
print(longest_common_subsequence(A, B)) # 输出2