最长公共子序列重现

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（注意它在序列中向前而不是向后）。