最长公共子序列记忆

Question

我尝试优化最长公共子序列问题的递归解决方案，但遇到了一些问题

我尝试一下：

cache = {}
def lcs1(s1,s2,i=0,j=0):
    if i>=len(s1) or j>=len(s2):
        return 0
    if (i,j) in cache:
        return cache[(i,j)]
    if s1[i] == s2[j]:
        cache[(i,j)] = 1 + lcs1(s1,s2,i+1,j+1)
    else:
        cache[(i,j)] = max(lcs1(s1,s2,i+1,j),lcs1(s1,s2,i,j+1))        
    return max(cache.values())

print(lcs1("AGGTAB","GXTXAYB"))

但它返回 5 而不是 4

Answer 1

返回

cache[i,j]

而不是

max(cache.values())

。