8.最长公共子序列问题

【问题描述】

若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。如果给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。现给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，要求使用动态规划算法思想，找出X和Y的最长公共子序列。

【输入形式】

输入以空格分割的字符，第一行对应第一条序列，第二行对应第二条序列。

【输出形式】

字符数组形式的最长公共子序列。

【样例输入】

z x y
x y y

【样例输出】

['x', 'y']

【样例说明】

第一行输入为第一条序列，包含z x y三个字符；输出为最长公共子序列，包含两个字符，以数组形式输出。

思路

动态规划：

状态表示：dp[i][j]表示a的[0_i]和b的[0j]的最长公共子序列的长度的最大值
状态计算：
- 如果a[i]==a[j],则dp[i][j]=dp[i-1][j-1]+1
- 否则，dp[i][j]=max(dp[i-1][j],dp[i][j-1])

代码

a = input().split()
b = input().split()
n, m = len(a), len(b)
# dp[i][j]表示a[0:i]和b[0:j]的最长公共子序列长度
dp = [[0 for i in range(m + 1)] for j in range(n + 1)]for i in range(1, n + 1):for j in range(1, m + 1):if a[i - 1] == b[j - 1]:  # a[i - 1]和b[j - 1]相等，那么dp[i][j]就是dp[i - 1][j - 1] + 1dp[i][j] = dp[i - 1][j - 1] + 1else:  # a[i - 1]和b[j - 1]不相等，那么dp[i][j]就是dp[i - 1][j]和dp[i][j - 1]的最大值dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
# 回溯  输出最长公共子序列
res = []
i = n
j = m
while i > 0 and j > 0:if a[i - 1] == b[j - 1]:  # a[i - 1]和b[j - 1]相等，那么a[i - 1]就是最长公共子序列的一个元素res.append(a[i - 1])i -= 1j -= 1elif dp[i - 1][j] > dp[i][j - 1]:  # a[i - 1]和b[j - 1]不相等，那么dp[i][j]就是dp[i - 1][j]和dp[i][j - 1]的最大值i -= 1else:j -= 1
res.reverse()
print(res)