dynamic-programming
Subsecuencias relacionadas con los algoritmos
Buscar..
La subsecuencia común más larga
Una de las implementaciones más importantes de la Programación Dinámica es encontrar la Subsecuencia Común Más Larga . Vamos a definir algunas de las terminologías básicas primero.
Subsecuencia
Una subsecuencia es una secuencia que puede derivarse de otra secuencia al eliminar algunos elementos sin cambiar el orden de los elementos restantes. Digamos que tenemos una cadena ABC . Si borramos cero o uno o más de un carácter de esta cadena obtenemos la subsecuencia de esta cadena. Así que las subsecuencias de la cadena ABC serán { "A" , "B" , "C" , "AB" , "AC" , "BC" , "ABC" , "" }. Incluso si eliminamos todos los caracteres, la cadena vacía también será una subsecuencia. Para averiguar la subsecuencia, para cada carácter de una cadena, tenemos dos opciones: o tomamos el carácter o no. Entonces, si la longitud de la cadena es n , hay 2 n subsecuencias de esa cadena.
Subsecuencia más larga:
Como el nombre sugiere, de todas las subsecuencias comunes entre dos cadenas, la subsecuencia común más larga (LCS) es la que tiene la longitud máxima. Por ejemplo: las subsecuencias comunes entre "HELLOM" y "HMLD" son "H" , "HL" , "HM", etc. Aquí "HLL" es la subsecuencia común más larga que tiene la longitud 3.
Método de fuerza bruta:
Podemos generar todas las subsecuencias de dos cadenas usando backtracking . Luego podemos compararlos para descubrir las subsecuencias comunes. Después tendremos que averiguar el que tiene la longitud máxima. Ya hemos visto que hay 2 n subsecuencias de una cadena de longitud n . Tomaría años resolver el problema si nuestra n cruza 20-25 .
Método de programación dinámica:
Abordemos nuestro método con un ejemplo. Supongamos que tenemos dos cadenas abcdaf y acbcf . Vamos a denotar estos con s1 y s2 . Por lo tanto, la subsecuencia común más larga de estas dos cadenas será "abcf" , que tiene una longitud 4. De nuevo, les recuerdo que las subsecuencias no tienen que ser continuas en la cadena. Para construir "abcf" , ignoramos "da" en s1 y "c" en s2 . ¿Cómo podemos descubrir esto utilizando la programación dinámica?
Comenzaremos con una tabla (una matriz 2D) que tiene todos los caracteres de s1 en una fila y todos los caracteres de s2 en la columna. Aquí la tabla tiene un índice de 0 y colocamos los caracteres de 1 en adelante. Recorreremos la tabla de izquierda a derecha para cada fila. Nuestra mesa se verá como:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Aquí, cada fila y columna representan la longitud de la subsecuencia común más larga entre dos cadenas si tomamos los caracteres de esa fila y columna y agregamos el prefijo anterior. Por ejemplo: la Tabla [2] [3] representa la longitud de la subsecuencia común más larga entre "ac" y "abc" .
La columna 0 representa la subsecuencia vacía de s1 . De manera similar, la fila 0 representa la subsecuencia vacía de s2 . Si tomamos una subsecuencia vacía de una cadena y tratamos de hacerla coincidir con otra, no importa cuán larga sea la longitud de la segunda subcadena, la subsecuencia común tendrá una longitud de 0. Entonces podemos llenar las filas 0-th y las columnas 0-th con 0's. Obtenemos:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Vamos a empezar. Cuando llenemos la Tabla [1] [1] , nos preguntamos, si tuviéramos una cadena a y otra cadena a y nada más, ¿cuál será la subsecuencia común más larga aquí? La longitud del LCS aquí será 1. Ahora veamos la Tabla [1] [2] . Tenemos la cadena ab y la cadena a . La longitud del LCS será 1. Como puede ver, el resto de los valores también serán 1 para la primera fila, ya que considera solo la cadena a con abcd , abcda , abcdaf . Así nuestra mesa se verá como:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Para la fila 2, que ahora incluirá c . Para la Tabla [2] [1] tenemos ac en un lado y a en el otro lado. Entonces, la longitud del LCS es 1. ¿De dónde obtuvimos este 1? Desde la parte superior, que denota el LCS a entre dos subcadenas. Entonces, lo que estamos diciendo es que si s1 [2] y s2 [1] no son lo mismo, entonces la longitud del LCS será la máxima de la longitud del LCS en la parte superior o en la izquierda . Tomar la longitud del LCS en la parte superior indica que no tomamos el carácter actual de s2 . De manera similar, tomar la longitud del LCS a la izquierda denota eso, no tomamos el carácter actual de s1 para crear el LCS. Obtenemos:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Así que nuestra primera fórmula será:
if s2[i] is not equal to s1[j]
Table[i][j] = max(Table[i-1][j], Table[i][j-1]
endif
Continuando, para la Tabla [2] [2] tenemos la cadena ab y ac . Como c y b no son iguales, ponemos el máximo de la parte superior o izquierda aquí. En este caso, es nuevamente 1. Después de eso, para la Tabla [2] [3] tenemos la cadena abc y ac . Esta vez los valores actuales de la fila y la columna son los mismos. Ahora la longitud de la LCS será igual a la longitud máxima de la LCS hasta ahora + 1. ¿Cómo obtenemos la longitud máxima de la LCS hasta ahora? Verificamos el valor diagonal, que representa la mejor coincidencia entre ab y a . Desde este estado, para los valores actuales, agregamos un carácter más a s1 y s2 que resultó ser el mismo. Por lo tanto, la duración de la LCS por supuesto aumentará. Pondremos 1 + 1 = 2 en la Tabla [2] [3] . Obtenemos,
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | 1 | 2 | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Así que nuestra segunda fórmula será:
if s2[i] equals to s1[j]
Table[i][j] = Table[i-1][j-1] + 1
endif
Hemos definido ambos casos. Usando estas dos fórmulas, podemos rellenar toda la tabla. Después de llenar la mesa, se verá así:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | 1 | 2 | 2 | 2 | 2 | 2 |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | 1 | 2 | 3 | 3 | 3 | 3 |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | 1 | 2 | 3 | 3 | 3 | 4 |
+-----+-----+-----+-----+-----+-----+-----+-----+
La longitud del LCS entre s1 y s2 será la Tabla [5] [6] = 4 . Aquí, 5 y 6 son la longitud de s2 y s1 respectivamente. Nuestro pseudo-código será:
Procedure LCSlength(s1, s2):
Table[0][0] = 0
for i from 1 to s1.length
Table[0][i] = 0
endfor
for i from 1 to s2.length
Table[i][0] = 0
endfor
for i from 1 to s2.length
for j from 1 to s1.length
if s2[i] equals to s1[j]
Table[i][j] = Table[i-1][j-1] + 1
else
Table[i][j] = max(Table[i-1][j], Table[i][j-1])
endif
endfor
endfor
Return Table[s2.length][s1.length]
La complejidad del tiempo para este algoritmo es: O (mn) donde m y n denota la longitud de cada cadena.
¿Cómo encontramos la subsecuencia común más larga? Comenzaremos desde la esquina inferior derecha. Comprobaremos de donde viene el valor. Si el valor proviene de la diagonal, es decir, si la Tabla [i-1] [j-1] es igual a la Tabla [i] [j] - 1 , presionamos s2 [i] o s1 [j] (ambos son lo mismo) y se mueven en diagonal. Si el valor viene de arriba, eso significa que si la Tabla [i-1] [j] es igual a la Tabla [i] [j] , nos movemos hacia la parte superior. Si el valor viene de la izquierda, eso significa que si la Tabla [i] [j-1] es igual a la Tabla [i] [j] , nos movemos hacia la izquierda. Cuando llegamos a la columna de la izquierda o de la parte superior, nuestra búsqueda termina. Luego sacamos los valores de la pila y los imprimimos. El pseudocódigo:
Procedure PrintLCS(LCSlength, s1, s2)
temp := LCSlength
S = stack()
i := s2.length
j := s1.length
while i is not equal to 0 and j is not equal to 0
if Table[i-1][j-1] == Table[i][j] - 1 and s1[j]==s2[i]
S.push(s1[j]) //or S.push(s2[i])
i := i - 1
j := j - 1
else if Table[i-1][j] == Table[i][j]
i := i-1
else
j := j-1
endif
endwhile
while S is not empty
print(S.pop)
endwhile
Puntos a destacar: si tanto la Tabla [i-1] [j] como la Tabla [i] [j-1] son iguales a la Tabla [i] [j] y la Tabla [i-1] [j-1] no es igual a la Tabla [i] [j] - 1 , puede haber dos LCS para ese momento. Este pseudocódigo no considera esta situación. Tendrás que resolver esto recursivamente para encontrar múltiples LCS.
La complejidad del tiempo para este algoritmo es: O (máx (m, n)) .
La subsecuencia cada vez mayor
La tarea es encontrar la longitud de la subsecuencia más larga en una matriz dada de enteros, de modo que todos los elementos de la subsecuencia se clasifiquen en orden ascendente. Por ejemplo, la longitud de la subsecuencia creciente más larga (LIS) para {15, 27, 14, 38, 26, 55, 46, 65, 85} es 6 y la subsecuencia creciente más larga es {15, 27, 38, 55, 65, 85} . Nuevamente, para {3, 4, -1, 0, 6, 2, 3} la longitud de LIS es 4 y la subsecuencia es {-1, 0, 2, 3} . Usaremos la programación dinámica para resolver este problema.
Tomemos el segundo ejemplo: Item = {3, 4, -1, 0, 6, 2, 3} . Comenzaremos tomando un dp de matriz del mismo tamaño de nuestra secuencia. dp [i] representa la longitud del LIS si incluimos el elemento i th de nuestra secuencia original. Al principio, sabemos que, para cada uno de los elementos, al menos la subsecuencia de mayor crecimiento es de longitud 1 . Eso es considerando el elemento único en sí. Así que vamos a inicializar la matriz dp con 1 . Tendremos dos variables i y j . Inicialmente i será 1 y j a ser 0. Nuestra matriz se verá como:
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
El número sobre la matriz representa el elemento correspondiente de nuestra secuencia. Nuestra estrategia será:
if Item[i] > Item[j]
dp[i] := dp[j] + 1
Eso significa que si el elemento en i es mayor que el elemento en j , la longitud del LIS que contiene el elemento en j , aumentará en longitud 1 si incluimos el elemento en i con él. En nuestro ejemplo, para i = 1 y j = 0 , el elemento [i] es mayor que el elemento [j] . Entonces dp [i] = dp [j] + 1 . Nuestra matriz se verá como:
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
En cada paso, aumentaremos j hasta i y luego restableceremos j a 0 e incrementaremos i . Por ahora, j ha alcanzado i , por lo que incrementamos i a 2 .
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
Para i = 2 , j = 0 , el elemento [i] no es mayor que el elemento [j] , por lo que no hacemos nada e incrementamos j .
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
Para i = 2 , j = 1 , el elemento [i] no es mayor que el elemento [j] , por lo que no hacemos nada y dado que j ha alcanzado su límite, incrementamos i y restablecemos j a 0 .
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
Para i = 3 , j = 0 , el elemento [i] no es mayor que el elemento [j] , por lo que no hacemos nada e incrementamos j .
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
Para i = 3 , j = 1 , el elemento [i] no es mayor que el elemento [j] , por lo que no hacemos nada e incrementamos j .
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
Para i = 3 , j = 2 , el elemento [i] es mayor que el elemento [j] , por lo que dp [i] = dp [j] + 1 . Después de eso, ya que j ha alcanzado su límite, nuevamente restablecemos j a 0 e incrementamos i .
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 2 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
Para i = 4 y j = 0 , el elemento [i] es mayor que el elemento [j] , por lo que dp [i] = dp [j] + 1 . Después de eso, incrementamos j .
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 2 | 2 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
Para i = 4 y j = 1 , el elemento [i] es mayor que el elemento [j] . También podemos notar que dp [i] = dp [j] + 1 nos proporcionará 3 , lo que significa que si tomamos el LIS para el artículo [j] y le agregamos el artículo [i] , obtendremos un mejor LIS { 3,4,6} que antes {3,6}. Entonces configuramos dp [i] = dp [j] + 1 . Luego incrementamos j .
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 2 | 3 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
Para i = 4 y j = 2 , el elemento [i] es mayor que el elemento [j] . Pero para este caso, si establecemos dp [i] = dp [j] + 1 , obtendremos 2 , que es {-1,6} no es el mejor {3,4,6} que podemos hacer usando el Elemento [ i] . Así que descartamos este. Agregaremos una condición a nuestra estrategia, que es:
if Item[i]>Item[j] and dp[i]<dp[j] + 1
dp[i] := dp[j] + 1
Incrementamos j en 1 . Siguiendo esta estrategia, si completamos nuestra matriz dp , se verá así:
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value | 1 | 2 | 1 | 2 | 3 | 3 | 4 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
Ahora recorreremos esta matriz y descubriremos el valor máximo, que será la longitud del LIS. Nuestro pseudo-código será:
Procedure LISLength(Item):
n := Item.length
dp[] := new Array(n)
for i from 0 to n
dp[i] := 1
end for
for i from 1 to n
for j from 0 to i
if Item[i]>Item[j] and dp[i]<dp[j] + 1
dp[i] := dp[j] + 1
end if
end for
end for
l := -1
for i from 0 to n
l := max(l, dp[i])
end for
Return l
La complejidad del tiempo de este algoritmo es O(n²) donde n es la longitud de la secuencia.
Para descubrir la secuencia original, necesitamos iterar hacia atrás y hacerla coincidir con nuestra longitud. El procedimiento es:
Procedure LIS(Item, dp, maxLength):
i := Item.length
while dp[i] is not equal to maxLength
i := i - 1
end while
s = new Stack()
s.push(Item[i])
maxLength := maxLength - 1
current := Item[i]
while maxLength is not equal to 0
i := i-1
if dp[i] := maxLength and Item[i] < current
current := Item[i]
s.push(current)
maxLength := maxLength - 1
end if
end while
while s is not empty
x := s.pop
Print(s)
end while
La complejidad temporal de este algoritmo es: O(n) .
Secuencia palindrómica más larga
Dada una cadena, ¿cuál es la subsecuencia palindrómica (LPS) más larga? Tomemos una cuerda agbdba . El LPS de esta cuerda es abdba de longitud 5 . Recuerde, ya que estamos buscando una subsecuencia , los caracteres no necesitan ser continuos en la cadena original. La subcadena palindrómica más larga de la secuencia sería bdb de longitud 3 . Pero nos concentraremos en la subsecuencia aquí. Vamos a utilizar la programación dinámica para resolver este problema.
Al principio, tomaremos una matriz 2D de la misma dimensión de nuestra secuencia original. Para nuestro ejemplo: S = "agbdba" , tomaremos dp [6] [6] array. Aquí, dp [i] [j] representa la longitud del LPS que podemos hacer si consideramos los caracteres de s [i] a s [j] . Por ejemplo. si nuestra cadena fuera aa , dp [0] [1] almacenaría 2 . Ahora consideraremos diferentes longitudes de nuestra cadena y descubriremos la longitud más larga posible que podamos hacer con ella.
Longitud = 1 :
Aquí, estamos considerando solo 1 personaje a la vez. Entonces, si tuviéramos una cadena de longitud 1 , ¿cuál es el LPS que podemos tener? Por supuesto que la respuesta es 1 . ¿Cómo almacenarlo? dp [i] [j] donde i es igual a j representa una cadena de longitud 1 . Así que vamos a configurar dp [0] [0] , dp [1] [1] , dp [2] [2] , dp [3] [3] , dp [4] [4] , dp [5] [ 5] a 1 . Nuestra matriz se verá como:
+---+---+---+---+---+---+---+
| | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
| 0 | 1 | | | | | |
+---+---+---+---+---+---+---+
| 1 | | 1 | | | | |
+---+---+---+---+---+---+---+
| 2 | | | 1 | | | |
+---+---+---+---+---+---+---+
| 3 | | | | 1 | | |
+---+---+---+---+---+---+---+
| 4 | | | | | 1 | |
+---+---+---+---+---+---+---+
| 5 | | | | | | 1 |
+---+---+---+---+---+---+---+
Longitud = 2 :
Esta vez consideraremos cadenas de longitud 2 . Ahora, considerando cadenas de longitud 2 , la longitud máxima de LPS puede ser 2 si y solo si los dos caracteres de la cadena son iguales. Entonces nuestra estrategia será:
j := i + Length - 1
if s[i] is equal to s[j]
dp[i][j] := 2
else
dp[i][j] := 1
Si llenamos nuestra matriz siguiendo la estrategia para Length = 2 , obtendremos:
+---+---+---+---+---+---+---+
| | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
| 0 | 1 | 1 | | | | |
+---+---+---+---+---+---+---+
| 1 | | 1 | 1 | | | |
+---+---+---+---+---+---+---+
| 2 | | | 1 | 1 | | |
+---+---+---+---+---+---+---+
| 3 | | | | 1 | 1 | |
+---+---+---+---+---+---+---+
| 4 | | | | | 1 | 1 |
+---+---+---+---+---+---+---+
| 5 | | | | | | 1 |
+---+---+---+---+---+---+---+
Longitud = 3 :
Ahora estamos viendo 3 caracteres a la vez para nuestra cadena original. A partir de ahora, el LPS que podemos hacer a partir de nuestra cadena estará determinado por:
- Si el primer y el último carácter coinciden, tendremos al menos 2 elementos de los que podemos hacer el LPS + si excluimos el primer y el último carácter, lo que sea mejor que podamos hacer de la cadena restante.
- Si el primer y el último carácter no coinciden, el LPS que podemos crear provendrá de la exclusión del primer carácter o del último, que ya hemos calculado.
Para veranear,
j := i + Length - 1
if s[i] is equal to s[j]
dp[i][j] := 2 + dp[i+1][j-1]
else
dp[i][j] := max(dp[i+1][j], dp[i][j-1])
end if
Si llenamos la matriz dp para Longitud = 3 a Longitud = 6 , obtendremos:
+---+---+---+---+---+---+---+
| | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
| 0 | 1 | 1 | 1 | 1 | 3 | 5 |
+---+---+---+---+---+---+---+
| 1 | | 1 | 1 | 1 | 3 | 3 |
+---+---+---+---+---+---+---+
| 2 | | | 1 | 1 | 3 | 3 |
+---+---+---+---+---+---+---+
| 3 | | | | 1 | 1 | 1 |
+---+---+---+---+---+---+---+
| 4 | | | | | 1 | 1 |
+---+---+---+---+---+---+---+
| 5 | | | | | | 1 |
+---+---+---+---+---+---+---+
Esta es nuestra matriz de dp requerida y dp [0] [5] contendrá la longitud del LPS. Nuestro procedimiento se verá como:
Procedure LPSLength(S):
n := S.length
dp[n][n]
for i from 0 to n
dp[i][i] := 1
end for
for i from 0 to (n-2)
if S[i] := S[i+1]
dp[i][i+1] := 2
else
dp[i][i+1] := 1
end if
end for
Length := 3
while Length <= n
for i from 0 to (n - Length)
j := i + Length - 1
if S[i] is equal to s[j]
dp[i][j] := 2 + dp[i+1][j-1]
else
dp[i][j] := max(dp[i+1][j], dp[i][j-1])
end if
end for
Length := Length + 1
end while
Return dp[0][n-1]
La complejidad del tiempo de este algoritmo es O(n²) , donde n es la longitud de nuestra cadena dada. El problema de la subsecuencia palindrómica más larga está estrechamente relacionado con la subsecuencia común más larga. Si tomamos la segunda cadena como la inversa de la primera y calculamos la longitud e imprimimos el resultado, esa será la subsecuencia palindrómica más larga de la cadena dada. La complejidad de ese algoritmo también es O(n²) .