Memoization za pomocą słownika w Pythonie

Question

Tak więc próbuję wdrożyć Najczęściej wspólny podciąg w Pythonie i próbowałem tej alternatywy do mojego poprzedniego rozwiązania. Próbowałem użyć słownika zamiast matrycy 2-D do zapamiętania wyników.

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 

To powrocie

TypeError: unsupported operand type(s) for +: 'int' and 'NoneType' 

co rozumiem to, bo nie mam nic, więc jak mogę zrobić coś takiego zwrotu.

return cache[s1, s2] = 1 + lcs(s1[:-1], s2[:-1]) 

Próbuję go zaimplementować bez użycia dekoratorów.

Answer 1

Spróbuj

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