algorithm - 从蛮力解决方案中导出 LCS 的子解决方案表

Question

我正在使用动态规划解决 LCS 问题。我在不查看解决方案的情况下自己推导出 DP 解决方案时遇到了问题。

我目前的推理是给定两个字符串，P 和 Q:

• 我们可以枚举 P 的所有子序列，其大小为 2^n。
• 我们还可以枚举 Q 的所有子序列，其大小为 2^m。

因此，如果我们要检查共享子序列，运行时间将为 O(2^n * 2^m) 或 O(2^(n+m)) 。

我不明白我们如何从这种蛮力解决方案过渡到动态规划解决方案。子解表的推导逻辑是什么？

我只是不明白我们如何从这一点直接跳到 DP 的子解决方案表。这样做的逻辑是什么？

我知道我们需要确定重叠的子解决方案。但是我找不到一个很好的解释来识别这个然后进入子解决方案表。

让我知道这个问题是否有意义。

Answer 1

这是为该算法创造魔力的基本思想。

考虑 2 个字符串 S1 和 S2，

S1 = c1,c2,c3,........cm, length = m

和

S2 = b1,b2,b3,........bn, length = n

假设你有一个函数LCS(arg1,arg2)，其中

arg1 = S1,m , string S1 of length of m

和

arg2 = S2,n , 长度为 n 的字符串 S2

和LCS(arg1,arg2) 将为我们提供 2 个参数的最长公共(public)子序列的长度。

现在假设两个字符串的最后一个字符相同。

bn = cm

并假设没有其他两个字符相同。这意味着:

LCS(arg1,arg2) = 1(last character) + 0(remaining strings)

现在如果你已经理解了上面的等式，那么很明显，如果不是没有其他两个字符匹配，我们确实有一些匹配(在剩余的字符串中)那么:

LCS(arg1,arg2) = 1(last character) + LCS(arg1 - cm,arg2 - bn)(Remaining strings)

但是如果最后两个字符不匹配，那么肯定我们必须考虑每个字符串中的倒数第二个字符，这就是为什么当 < strong>最后 2 个字符不匹配:

LCS(arg1,arg2) = max(LCS(arg1 - cm,arg2) , LCS(arg1 ,arg2 - bn))