Самая длинная повторяющаяся подпоследовательность: крайние случаи

• Для получения самого длинного значения лучше всего реализовать новую функцию с результатом dp сетки.

• Ваш алгоритм в порядке, вам нужно только увеличить новый dp на 1, когда s[i - 1] == s[j - 1]:

    n = len(s)
    dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if s[i - 1] == s[j - 1] and i != j:
                dp[i][j] = 1 + dp[i - 1][j - 1]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[-1][-1]

Если вы хотите построить самый длинный, вы можете использовать сетку dp и всякий раз, когда if s[i - 1] == s[j - 1] and i != j удовлетворяет, добавьте символ к самому длинному:

    def get_longest():
        i, j = n, n
        lrs = []
        while i > 0 and j > 0:
            if s[i - 1] == s[j - 1] and i != j:
                lrs.append(s[i - 1])
                i -= 1
                j -= 1
            elif dp[i - 1][j] > dp[i][j - 1]:
                i -= 1
            else:
                j -= 1

        return ''.join(lrs[::-1])

Код

def LRS(s):
    def get_longest():
        i, j = n, n
        lrs = []
        while i > 0 and j > 0:
            if s[i - 1] == s[j - 1] and i != j:
                lrs.append(s[i - 1])
                i -= 1
                j -= 1
            elif dp[i - 1][j] > dp[i][j - 1]:
                i -= 1
            else:
                j -= 1

        return ''.join(lrs[::-1])
    n = len(s)
    dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if s[i - 1] == s[j - 1] and i != j:
                dp[i][j] = 1 + dp[i - 1][j - 1]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    print(get_longest())
    return dp[-1][-1]


s = 'AXXXA'
print(LRS(s))

Принты

ХХ 2

Вы можете отслеживать индексы последних добавленных символов и следить за тем, чтобы, когда два символа одинаковы, их индексы должны отличаться не только друг от друга, но и от индекса последнего добавленного символа:

s = 'AXXXA'
n = len(s)
dp = [[('', 0, 0) for i in range(n + 1)] for j in range(n + 1)]

for i in range(1, n + 1):
    for j in range(1, n + 1):
        last = dp[i - 1][j - 1]
        if last[2] != i != j != last[1] and s[i - 1] == s[j - 1]:
            dp[i][j] = last[0] + s[i - 1], i, j
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], key=lambda t: t[0])

print(dp[n][n][0]) # outputs X

Демо: https://ideone.com/mSKgKy

На самом деле ваш первоначальный алгоритм и его ответ верны (... но это хороший вопрос, потому что другие могут запутаться в том, что означает LRS).

Учитывая ваш ввод (in), подпоследовательности (s1, s2):

in: AXXXA
s1:  XX
s2:   XX

Итак, XX (длина 2) здесь действительно правильный ответ.

X будет правильным ответом для непересекающейся версии задачи, где диапазоны, а не только отдельные индексы, должны быть непересекающимися.