dynamic - 最长公共子序列递归

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. A的当前子串减去它的第一个字符和B的最长公共子序列，即L[i-1,j]；
2. A 的最长公共子序列和 B 的当前子串减去它的第一个字符，即L[i,j-1].

如果L[i-1,j-1]正确，则意味着 A 和 B 中的当前字符都不算数，它们没有“机会”成为子序列的一部分。

例如参见这个解释（注意它在序列中向前而不是向后工作）。