我可以使用动态规划以正确的方式做到这一点，但我不知道如何在指数时间内做到这一点。
我正在寻找两个字符串之间最大的公共(public)子序列。 注意:我指的是子序列，而不是子字符串，组成序列的符号不需要是连续的。
最佳答案
只需将动态编程代码中的表中的查找替换为递归调用。换句话说，只需执行 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))
关于algorithm - 如何在指数时间内找到最长公共(public)子序列？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9010479/