Воспоминание с использованием словаря в Python

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