如何使用动态规划编写函数来查找最长的公共子序列？

Question

明确地说，我是在寻找子序列本身，而不是长度。我已经写了这个函数，它大部分时间都可以工作，但在某些情况下它不工作。我必须在没有任何循环或导入的情况下递归地编写它。为了提高效率，我使用了一个备忘录功能，但没有包括在这里

当s1=“abcde”和s2=“qbxxd”（正确返回“bd”）时，此函数起作用，但当s1=“看着我，我能飞！”和s2=“看着，这是一只苍蝇”时，此函数不起作用，它应该返回“看着，一只苍蝇”，但我得到的是“看着一只苍蝇”。不管出于什么原因，逗号和空格都会被忽略。我尝试了s1=“ab，cde”和s2=“qbxx，d”，它们正确地返回“b，d”

def lcs(s1, s2):
"""y5tgr"""
i = len(s1)
j = len(s2)
if i == 0 or j == 0:
    return ""
if s1[i-1] == s2[j-1]:
    return lcs(s1[:-1], s2[:-1]) + s1[i-1]
else:
    return max(lcs(s1[:-1], s2), lcs(s1, s2[:-1]))

我感觉问题出在最后一行和max函数上。我见过使用for和while循环的解决方案，但没有

Answer 1

对于字符串，max采用字典中最后一个的字符串：

>>> max("a", "b")
'b'
>>> max("aaaaa", "b")
'b'
>>> 

当然不是你需要的；你似乎在寻找这两个词中的长。 您不需要循环，只需要比较：

lsc1 = lcs(s1[:-1], s2)
lcs2 = lcs(s1, s2[:-1])
return lcs1 if len(lcs1) > len(lcs2) else lcs2

Answer 2

只需稍作修改即可修复代码（没错，问题出在max中）

只需更改max，就可以使用它的键函数找到max length的字符串

def lcs(s1, s2):
    """y5tgr"""
    i = len(s1)
    j = len(s2)
    if i == 0 or j == 0:
        return ""
    if s1[i-1] == s2[j-1]:
        return lcs(s1[:-1], s2[:-1]) + s1[i-1]
    else:
        # Find max based upon the string length
        return max(lcs(s1[:-1], s2), lcs(s1, s2[:-1]), key=len)

然而，如果没有记忆，这是非常缓慢的

带有备忘录的代码（以提高性能）

Memoization Decorator Reference

import functools

def memoize(obj):
    cache = obj.cache = {}

    @functools.wraps(obj)
    def memoizer(*args, **kwargs):
        if args not in cache:
            cache[args] = obj(*args, **kwargs)
        return cache[args]
    return memoizer

@memoize
def lcs(s1, s2):
    """y5tgr"""
    i = len(s1)
    j = len(s2)
    if i == 0 or j == 0:
        return ""
    if s1[i-1] == s2[j-1]:
        return lcs(s1[:-1], s2[:-1]) + s1[i-1]
    else:
        return max(lcs(s1[:-1], s2), lcs(s1, s2[:-1]), key=len)

测试

s1 = "Look at me, I can fly!"
s2 = "Look at that, it's a fly"
print(lcs(s1, s2))

输出

Look at ,  a fly