最長的公共子序列（還原序列）

Question

我有2個序列，需要找到最長的公共子序列。不知道爲什麼我的功能恢復不起作用。

#sequenses 
A=[1,2,3] 
B=[2,3,1,5] 
#table AxB 
rows=[0]*(len(B)+1) 
table=[rows for l in range(len(A)+1)] 
for i in range(len(A)): 
    for k in range(len(B)): 
     if A[i]==B[k]: 
      table[i+1][k+1]=table[i][k]+1 
     else: 
      table[i+1][k+1]=max(table[i][k+1], table[i+1][k]) 
print(table) 
lst=[]#subsequence 
#function to restore subsequence by walking through table 
def restore(s1,s2):#s1=len(A)-1, s2=len(B)-1 
    if s1==-1 or s2==-1: 
     pass 
    elif A[s1]==B[s2]: 
     print (1) 
     lst.append(A[s1]) 
     restore(s1-1, s2-1) 
    else: 
     if table[s1][s2+1]==table[s1+1][s2+1]: 
      restore(s1-1,s2) 
     else: 
      restore(s1, s2-1) 
    return lst 

如果我做

print (restore(2,3)) 

函數返回

[] 

我認爲，這個問題是索引，但無法找到它在哪裏。

Answer 1

這是你的第一個問題：

rows=[0]*(len(B)+1) 
table=[rows for l in range(len(A)+1)] 

Python使用引用的名單。所以當你製作一堆rows時，它實際上是對同一個rows列表的多個引用。看看這個測試代碼：

>>> rows = [0]*5 
>>> table = [rows for l in range(5)] 
>>> table 
[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]] 
>>> table[0][2] = 4 
>>> table 
[[0, 0, 4, 0, 0], [0, 0, 4, 0, 0], [0, 0, 4, 0, 0], [0, 0, 4, 0, 0], [0, 0, 4, 0, 0]] 

看看如何重複單個更改？這是因爲我有5個引用相同的列表，而不是5個列表。試試這個：

table = [None]*(len(A)+1) 
for i in range(len(table)): 
    table[i] = [0]*(len(B)+1)