使用字典记忆

Question

所以我正在尝试在 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])

我正在尝试不使用任何装饰器来实现它。

Answer 1

试试这个

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

使用字典记忆

Memoization using dictionary

python

memoization