最長的公共子序列Algo

Question

在最長的公共子序列（LCS）問題中，爲什麼我們匹配字符串的最後一個字符。例如 請考慮輸入字符串「AGGTAB」和「AXTXAYB」。最後的字符與字符串匹配。因此LCS的長度可以寫成：

L(「AGGTAB」, 「AXTXAYB」) = 1 + L(「AGGTA」, 「AXTXAY」) 

豈不的算法中仍產生最佳的搜索，如果我們匹配字符串首字符。例如

考慮輸入字符串「AGGTAB」和「AXTXAYB」。首字符匹配字符串。因此LCS的長度可以寫成：

L(「AGGTAB」, 「AXTXAYB」) = 1 + L(「GGTAB」, 「XTXAYB」) 

LCS問題：Longest Common Subsequence Problem

Answer 1

是的，這是一回事。

計算兩個反轉序列的LCS與逆轉反轉前的兩個序列的LCS相同。換句話說，

REVERSE(LCS(A,B)) = LCS(REVERSE(A), REVERSE(B)) 

假設LCS從端部減小，在右側的操作將去從所述相對的端部，但是實現相同的結果。

這就是爲什麼你可以使用前綴的原因，就像他們在解釋中使用後綴的方式一樣：在這個過程中你會得到同樣的遞歸減少。

此外，如果您願意，您可以在兩端進行折扣。然而，這會使算法複雜化，而不會給你任何加速的回報。

Answer 2

是的，你能做到這一點不會改變時間複雜度。從最後開始只是一個約定的問題。

Answer 3

那麼事實證明，你可以直接使用長度變量（比如M，N）由用戶提供的，如果我們從去年進行LCS遞歸的。另一方面，如果從start索引執行，則必須創建額外的變量。這就是以前的方法被認爲是標準的原因，否則沒有複雜性差異，一切都是一樣的。

LCS (M, N) 
{ 
if(M==0 || N==0) 
return 0; 
elseif (a[M]!=b[N]) 
return max(LCS(M,N-1), LCS(M-1,N)); 
else 
return 1 + LCS(M-1,N-1); 
}