如何在指数时间内找到最长公共子序列？

Question

我可以使用动态编程以正确的方式执行此操作,但我无法弄清楚如何在指数时间内执行此操作.

我正在寻找两个字符串之间最大的公共子序列.注意:我的意思是子序列而不是子串,构成序列的符号不必是连续的.

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))