Memoizzazione tramite dizionario in Python

Question

Quindi sto cercando di implementare la sottosuccessione comune più bassa in Python e stavo provando questa alternativa alla mia soluzione precedente. Ho provato ad usare un dizionario invece di una matrice 2-D per memorizzare i risultati.

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 

Sta tornando

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

che capisco è perché io non sto tornando niente di così come posso fare qualcosa di simile.

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

E sto cercando di implementarlo senza utilizzare alcun decoratore.

Answer 1

Prova questa

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