我可以使用动态编程以正确的方式做到这一点，但我不知道如何在指数时间内做到这一点。
我正在寻找两个字符串之间最大的公共子序列。
注意：我的意思是子序列而不是子串，组成序列的符号不必是连续的。
只需用递归调用替换动态编程代码中表中的查找即可。换句话说，只需实现以下的递归公式：LCS https://en.wikipedia.org/wiki/Longest_common_subsequence_problem问题：
EDIT
在伪代码中（实际上几乎是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))
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
