algorithm - 如何在指数时间内找到最长公共(public)子序列？

Question

我可以使用动态规划以正确的方式做到这一点，但我不知道如何在指数时间内做到这一点。

我正在寻找两个字符串之间最大的公共(public)子序列。注意:我指的是子序列，而不是子字符串，组成序列的符号不需要是连续的。

Answer 1

只需将动态编程代码中的表中的查找替换为递归调用。换句话说，只需执行 LCS 的递归公式即可。问题:

编辑

在伪代码中(实际上几乎是 python):

def lcs(s1, s2):
 if len(s1)==0 or len(s2)==0: return 0
 if s1[0] == s2[0]: return 1 + lcs(s1[1:], s2[1:])
 return max(lcs(s1, s2[1:]), lcs(s1[1:], s2))