无动态规划的长度最长公共子序列

Question

我正在做一个练习，在没有动态编程的情况下寻找最长的公共子序列(LSC)，到目前为止，我有返回最长公共子序列的代码，但我还需要返回序列的长度，我必须做什么？

这是返回最长公共子序列的代码

def lcs(str1, str2):
    
    if len(str1) == 0 or len(str2) == 0:
        return ""
    if str1[-1] == str2[-1]:
        return lcs(str1[:-1], str2[:-1]) + str1[-1]
  
    t1 = lcs(str1[:-1], str2)
    t2 = lcs(str1, str2[:-1])
    if len(t1) > len(t2):
        return t1
    else:
        return t2

如何返回序列的长度？

Answer 1

只需让您的return语句返回在原始语句中返回的字符串的长度：

def lcs(str1, str2):
    if len(str1) == 0 or len(str2) == 0:
        return 0 #len("")
    if str1[-1] == str2[-1]:
        return lcs(str1[:-1], str2[:-1]) + 1
    return max(lcs(str1[:-1], str2),lcs(str1, str2[:-1]))