Рекурсия, показывающая ошибку при поиске самой длинной общей подпоследовательности в python

В какой строке возникает ошибка? Я предполагаю, что это линия

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

потому что ошибка говорит о том, что вы добавляете два объекта, один из которых имеет тип int, а другой не имеет указанного типа (который Python называет NoneType). Это означает, что ваша функция lcs ничего не возвращает, когда вы вводите ей входные данные m - 1 и n - 1. Это происходит потому, что единственный оператор return в вашей функции встречается в самом внешнем условии else.

Другими словами, вам нужно, чтобы ваша функция что-то возвращала, возможно, целое число, когда ключ str(m) + "|" + str(n) отсутствует в словаре.

Я не знаю, тот ли это результат, который вы ищете, но я добавил оператор возврата:

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)

и теперь приведенный выше код при запуске возвращает:

{'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}