字典记忆法
提问于 2015-11-10 03:14:53
因此，我试图在Python中实现最低的公共子序列，并尝试替代以前的解决方案。我试着用字典代替二维矩阵来回溯结果。
def lcs(s1, s2):
cache = {}
if len(s1) == 0 or len(s2) == 0:
return 0
if (s1, s2) in cache:
return cache[s1, s2]
else:
if s1[-1] == s2[-1]:
cache[s1, s2] = 1 + lcs(s1[:-1], s2[:-1])
else:
cache[s1, s2] = max(lcs(s1[:-1], s2), lcs(s1, s2[:-1]))
print cache它又回来了
TypeError: unsupported operand type(s) for +: 'int' and 'NoneType'我明白这是因为我什么都不还，所以我怎么能做这样的事情。
return cache[s1, s2] = 1 + lcs(s1[:-1], s2[:-1])我试图在不使用任何装饰师的情况下实现它。
回答 1
Stack Overflow用户
回答已采纳
发布于 2015-11-10 03:19:11
尝尝这个
cache = {}
def lcs(s1, s2):
global cache
if len(s1) == 0 or len(s2) == 0:
return 0
if (s1, s2) in cache:
return cache[(s1, s2)]
else:
if s1[-1] == s2[-1]:
cache[(s1, s2)] = 1 + lcs(s1[:-1], s2[:-1])
else:
cache[(s1, s2)] = max(lcs(s1[:-1], s2), lcs(s1, s2[:-1]))
return cache[(s1, s2)]页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/33628707
复制
腾讯云开发者
