最長公共子序列重現

Question

爲lcs復發是：

L[i,j] = max(L[i-1,j], L[i,j-1]) if a[i] != a[j] 

你能告訴我，爲什麼它是i-1或j-1？爲什麼不是L[i,j] = L[i-1,j-1]正確？

Answer 1

您正在考慮a[i] != a[j]的情況，這意味着您當前比較兩個序列A和B的字母不同。因此，最長公共子序列的長度是兩件事情之一：

1. 甲減去它的第一字符和B，當前子串的最長公共子序列即L[i-1,j];
2. A的最長公共子序列和B的當前子字符串減去它的第一個字符，即L[i,j-1]。

如果L[i-1,j-1]是正確的，這將意味着，在A和B的當前角色不計，他們沒有得到一個「機會」是序列的一部分。

例如參見this explanation（注意它在序列中向前而不是向後）。