递归显示在 python 中查找最长公共子序列的错误

Question

这是ideone link。我想通过动态规划解决著名的 lcs 问题，但无法解决此错误。当我运行这个函数时它说如下：

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

a = "ABCBDABA"
b = "BDCABAD"
d = dict()
def lcs(m, n):
    if m == 0 or n == 0:
        return 0
    key = str(m) + "|" + str(n)
    if key not in d.keys():
        #print(key)           
        if a[m - 1] == b[n - 1]:
            d[key] = lcs(m - 1, n - 1) + 1
        else:
            d[key] = max(lcs(m - 1, n), lcs(m, n - 1))
    else:
        return d[key]

lcs(len(a), len(b))
print(d)

Answer 1

错误发生在哪一行？我猜是这条线

d[key] = lcs(m - 1, n - 1) + 1

因为错误是说您要添加两个对象，一个是 int 类型，另一个没有指定类型（Python 调用 NoneType）。这意味着当您给它输入 m - 1 和 n - 1 时，您的 lcs 函数不会 returning 任何东西。发生这种情况是因为函数中唯一的 return 语句出现在最外层的 else 条件中。

也就是说，当键 str(m) + "|" + str(n) 不在字典中时，您需要函数 return 某个东西，也许是一个整数。

我不知道这是否是您要查找的输出，但我添加了 return 语句：

a = "ABCBDABA"
b = "BDCABAD"
d = dict()
def lcs(m, n):
    if m == 0 or n == 0:
        return 0
    key = str(m) + "|" + str(n)
    if key not in d.keys():
        #print(key)           
        if a[m - 1] == b[n - 1]:
            d[key] = lcs(m - 1, n - 1) + 1
        else:
            d[key] = max(lcs(m - 1, n), lcs(m, n - 1))
        return d[key]
    else:
        return d[key]

lcs(len(a), len(b))
print(d)

现在上面的代码，当运行，returns:

{'1|6': 1, '1|4': 1, '2|5': 2, '2|6': 2, '1|1': 0, '1|2': 0, '1|3': 0, '2|1': 1, '2|2': 1, '2|3': 1, '2|4': 1, '3|3': 2, '3|4': 2, '3|5': 2, '3|6': 2, '4|5': 3, '4|6': 3, '5|7': 4, '3|1': 1, '3|2': 1, '4|1': 1, '4|2': 1, '4|3': 2, '4|4': 2, '5|2': 2, '5|3': 2, '5|4': 2, '5|5': 3, '6|6': 4, '6|7': 4, '6|4': 3, '7|5': 4, '7|6': 4, '7|7': 4, '8|6': 5, '8|7': 5}

递归显示在 python 中查找最长公共子序列的错误

Recursion showing error for finding longest common sub-sequence in python

python

debugging

recursion

lcs