Estoy tratando de resolver un problema de programación dinámica de @ Corm Introducción a los algoritmos 3a edición (pág. 405) que pregunta lo siguiente:

Un palíndromo es una cadena no vacía sobre un alfabeto que lee el mismo hacia adelante y hacia atrás. Ejemplos de palíndromos son todas las cadenas de longitud 1,civic, racecar yaibohphobia (miedo a los palíndromos).

Proporcione un algoritmo eficiente para encontrar el palíndromo más largo que sea una subsecuencia de una cadena de entrada dada. Por ejemplo, dada la entradacharacter, su algoritmo debería devolvercarac.

Bueno, podría resolverlo de dos maneras:

Primera solución:

a Subsecuencia de Palindrome más larga (LPS) de una cadena es simplemente la La mayor secuencia común de sí mismo y su reverso. (Construí esta solución después de resolver otra pregunta relacionada que pide laSecuencia creciente más larga de una secuencia). Como se trata simplemente de una variante LCS, también requiere tiempo O (n²) y memoria O (n²).

Segunda solución:

La segunda solución es un poco más elaborada, pero también sigue la plantilla general de LCS. Proviene de la siguiente recurrencia:

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

l pseudocódigo para calcular la longitud de lps es el siguiente:

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] )

Todavía me toma O (n²) tiempo y memoria si quiero efectivamenteconstrui the lps (porque necesitaré todas las celdas de la tabla). Al analizar problemas relacionados, como LIS, que se pueden resolver con enfoques distintos de los LCS con menos memoria (LIS se puede resolver con memoria O (n)), me preguntaba si es posible resolverlo con memoria O (n), también

LIS logra este límite al vincular las subsecuencias candidatas, pero con palíndromos es más difícil porque lo que importa aquí no es el elemento anterior en la subsecuencia, sino el primero. ¿Alguien sabe si es posible hacerlo, o las soluciones anteriores son óptimas para la memoria?