Попытка реализовать DP сверху вниз с Python, считаю, что кэширование не работает

Question

Это домашнее задание, но с текущей блокировкой я не могу попросить своего репетитора о помощи, поэтому я подумал, что я буду использовать целое значение rnet:)

Я пытаюсь реализовать специально top -ddown (таким образом, кэширование) DP для алгоритма самой длинной общей подпоследовательности. И вот что я написал:

def lcs(s1, s2, known=None):
    if(known == None):
        known = {}
    if len(s1) == 0:
        return 0
    if len(s2) == 0:
        return 0
    else:
        if((s1, s2) in known):
            return known[(s1, s2)]
        elif(s1[-1] == s2[-1]):
            now_known = (1 + lcs(s1[:-1], s2[:-1]))
            known[(s1, s2)] = now_known
            return now_known
        else:
            now_known = max((lcs(s1, s2[:-1])), (lcs(s1[:-1], s2)))
            known[(s1, s2)] = now_known
            return now_known

Мое понимание того, что я написал, таково:

• Мой код проверяет, пуста ли какая-либо из строк, если это В этом случае самая длинная общая подпоследовательность будет 0
• . Затем мой код проверяет, находятся ли две строки, которые он проверяет, в кэше, если он есть, он возвращает значения, связанные с ним в кэше.
• Мой код затем проверяет, является ли последний элемент в двух строках одинаковым, и в этом случае самые длинные подпоследовательности будут равны 1 плюс lcs остальной части строки.
• В противном случае мой код рекурсивно вызывает сам по себе дважды, по одному разу для каждой строки минус последний элемент

Когда приведенный выше код выполняется для двух небольших строк:

s1 = "abcde"
s2 = "qbxxd"
lcs = lcs(s1, s2)
print(lcs)

Я получаю правильный вывод 2 :) Однако , при работе на больших входах, таких как:

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

Мой код истек. Это, плюс некоторое тестирование операторов печати (тестирование того, что добавляется к «известному», когда я добавляю к «известному»), заставляет меня поверить, что я неправильно реализую свое кэширование. Это может быть простая глупая проблема с исправлением ошибок, и в этом случае я извиняюсь, но я считаю, что это проблема с моим пониманием кеширования. Кроме того, мне известно о «кэше lru», которое выполняет кэширование для меня, однако для целей этого домашнего задания я должен написать собственное кэширование.

Любое понимание будет высоко оценено.

Answer 1

Как отмечалось в комментариях, вы не передаете known рекурсивные вызовы. Поэтому он всегда начинается с None, затем заполняется {}, и вы никогда не извлекаете выгоду из кеширования.

Мне лично нравится следующий шаблон

def lcs(s1, s2):
    cache = {}

    def _lcs (i, j):
        if (i, j) not in cache:
            ... (logic here) ...

        return cache[(i, j)]

    return _lcs(0, 0)

Идея кеш и последовательности теперь создаются один раз, а вы просто играете с индексами. Я также не забываю передать кеш. : -)