在Python中使用字典的記憶

Question

所以我試圖實現Python中的最低公共子序列，並試圖將此替代方案用於我以前的解決方案。我嘗試使用字典而不是2-D矩陣來記憶結果。

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