аюсь решить проблему динамического программирования из Cormem'sВведение в алгоритмы 3-е издание (стр. 405), который просит следующее:

Палиндром - это непустая строка в некотором алфавите, которая читает одно и то же вперед и назад. Примерами палиндромов являются все строки длиной 1,civic, racecar, а такжеaibohphobia (боязнь палиндромов).

Дайте эффективный алгоритм, чтобы найти самый длинный палиндром, который является подпоследовательностью заданной входной строки. Например, учитывая входcharacterваш алгоритм должен вернутьсяcarac.

Ну, я мог бы решить это двумя способами:

Первое решение:

Самая длинная подпоследовательность палиндрома (LPS) строки - это простоСамая длинная общая подпоследовательность о себе и его обратной. (Я построил это решение после решения другого связанного вопроса, который проситСамая длинная возрастающая подпоследовательность последовательности). Так как это просто вариант LCS, он также требует O (n²) времени и O (n²) памяти.

Второе решение:

Второе решение немного сложнее, но также следует общему шаблону LCS. Это происходит из-за следующего повторения:

lps(s[i..j]) = 
    s[i] + lps(s[i+1]..[j-1]) + s[j], if s[i] == s[j];
    max(lps(s[i+1..j]), lps(s[i..j-1])) otherwise

Псевдокод для расчета длины lps следующий:

compute-lps(s, n):

    // palindromes with length 1
    for i = 1 to n:
        c[i, i] = 1
    // palindromes with length up to 2
    for i = 1 to n-1:
        c[i, i+1] = (s[i] == s[i+1]) ? 2 : 1

    // palindromes with length up to j+1
    for j = 2 to n-1:
        for i = 1 to n-i:
            if s[i] == s[i+j]:
                c[i, i+j] = 2 + c[i+1, i+j-1]
            else:
                c[i, i+j] = max( c[i+1, i+j] , c[i, i+j-1] )

Это все еще занимает O (n²) времени и памяти, если я хочу эффективносооружать lps (потому что мне понадобятся все ячейки на столе). Анализируя связанные проблемы, такие как LIS, которые могут быть решены с помощью подходов, отличных от LCS, с меньшим объемом памяти (LIS разрешима с O (n) памятью), мне было интересно, возможно ли решить это с помощью O (n) памяти, слишком.

LIS достигает этой границы, связывая возможные последовательности, но с палиндромами это сложнее, потому что здесь важен не предыдущий элемент в подпоследовательности, а первый. Кто-нибудь знает, возможно ли это сделать, или память предыдущих решений оптимальна?