最长公共子序列（longest common subsequence）问题如下：给定两个序列A=a1,a2,…,aM和B=b1,b2,…,bN，找出A和B二者共有的最长子列C=c1,c2,…,ck的长度k。例如，若： A=d,y,n,a,m,i,c 和 B=p,r,o,g,r,a,m,m,i,n,g 则最长公共子序列为a,m，器长度为2。给出一个算法求解最长公共子序列问题。你的算法应该以O(MN)时间运行。

区块链毕设网qklbishe.com为您提供问题的解答

最长公共子序列（longest common subsequence）问题如下：给定两个序列A=a₁,a₂,…,a_M和B=b₁,b₂,…,b_N，找出A和B二者共有的最长子列C=c₁,c₂,…,c_k的长度k。例如，若：

A=d,y,n,a,m,i,c

和

B=p,r,o,g,r,a,m,m,i,n,g

则最长公共子序列为a,m，器长度为2。给出一个算法求解最长公共子序列问题。你的算法应该以O(MN)时间运行。

经典DP：

def LCS(seq1, seq2):

table = [[float(‘inf’)]*(len(seq2)+1) for i in range(len(seq1)+1)]

for j in range(len(seq2)+1):

table[len(seq1)][j] = 0

for i in range(len(seq1)+1):

table[i][len(seq2)] = 0

for i in range(len(seq1)-1, -1, -1):

for j in range(len(seq2)-1, -1, -1):

if seq1[i] == seq2[j]:

table[i][j] = table[i+1][j+1] + 1

else:

table[i][j] = max(table[i][j+1], table[i+1][j]) # val(i,j) <– val(i+1,j)和val(i,j+1)中较大的

return table[0][0]

40:31

以上就是关于问题最长公共子序列（longest common subsequence）问题如下：给定两个序列A=a1,a2,…,aM和B=b1,b2,…,bN，找出A和B二者共有的最长子列C=c1,c2,…,ck的长度k。例如，若： A=d,y,n,a,m,i,c 和 B=p,r,o,g,r,a,m,m,i,n,g 则最长公共子序列为a,m，器长度为2。给出一个算法求解最长公共子序列问题。你的算法应该以O(MN)时间运行。的答案

欢迎关注区块链毕设网-
专业区块链毕业设计成品源码，定制。

区块链NFT链游项目方科学家脚本开发培训