dynamic-programming
Algoritmi correlati alla successione
Ricerca…
La più lunga successiva in comune
Una delle implementazioni più importanti della programmazione dinamica è scoprire la più lunga sequenza secondaria . Definiamo prima alcune delle terminologie di base.
Sotto sequenza:
Una sottosequenza è una sequenza che può essere derivata da un'altra sequenza eliminando alcuni elementi senza modificare l'ordine degli elementi rimanenti. Diciamo che abbiamo una stringa ABC . Se cancelliamo zero o uno o più di un carattere da questa stringa otteniamo la sottosequenza di questa stringa. Quindi le sottosequenze della stringa ABC saranno { "A" , "B" , "C" , "AB" , "AC" , "BC" , "ABC" , "" }. Anche se rimuoviamo tutti i caratteri, la stringa vuota sarà anche una sottosequenza. Per scoprire la sottosequenza, per ogni personaggio in una stringa, abbiamo due opzioni: o prendiamo il personaggio o non lo facciamo. Quindi se la lunghezza della stringa è n , ci sono 2 n sottosequenze di quella stringa.
La più lunga comune successiva:
Come suggerisce il nome, tra tutte le sottosequenze comuni tra due stringhe, la sottosequenza comune più lunga (LCS) è quella con la lunghezza massima. Ad esempio: Le sottosequenze comuni tra "HELLOM" e "HMLD" sono "H" , "HL" , "HM" ecc. Qui "HLL" è la sottosequenza comune più lunga che ha lunghezza 3.
Metodo a forza bruta:
Possiamo generare tutte le sottosequenze di due stringhe usando il backtracking . Quindi possiamo confrontarli per scoprire le sottosequenze comuni. Dopo avremo bisogno di trovare quello con la lunghezza massima. Abbiamo già visto che ci sono 2 n sottosequenze di una stringa di lunghezza n . Ci vorrebbero anni per risolvere il problema se le nostre n croci 20-25 .
Metodo di programmazione dinamica:
Avviciniamoci al nostro metodo con un esempio. Supponiamo che, abbiamo due stringhe abcdaf e acbcf . Indichiamo questi con s1 e s2 . Quindi la sottosequenza comune più lunga di queste due stringhe sarà "abcf" , che ha lunghezza 4. Ancora una volta vi ricordo che le sottosequenze non devono essere continue nella stringa. Per costruire "abcf" , abbiamo ignorato "da" in s1 e "c" in s2 . Come lo scopriamo usando la programmazione dinamica?
Inizieremo con una tabella (una matrice 2D) con tutti i caratteri di s1 in una riga e tutti i caratteri di s2 nella colonna. Qui la tabella è 0-indexed e inseriamo i caratteri da 1 in poi. Attraverseremo il tavolo da sinistra a destra per ogni riga. La nostra tabella sarà simile a:
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 | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Qui ogni riga e colonna rappresentano la lunghezza della sottosequenza comune più lunga tra due stringhe se prendiamo i caratteri di quella riga e colonna e aggiungiamo al prefisso prima di esso. Ad esempio: Table [2] [3] rappresenta la lunghezza della sottosequenza comune più lunga tra "ac" e "abc" .
La colonna 0 ° rappresenta la sottosuccessione vuota di s1 . Allo stesso modo la riga 0 ° rappresenta la sottosequenza vuota di s2 . Se prendiamo una sottosequenza vuota di una stringa e proviamo ad abbinarla ad un'altra stringa, indipendentemente dalla lunghezza della seconda sottostringa, la sottosuccessione comune avrà lunghezza 0. Quindi possiamo riempire le righe 0-esime e le colonne 0-esime con 0. Noi abbiamo:
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 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Cominciamo. Quando riempiamo Table [1] [1] , ci stiamo chiedendo, se avessimo una stringa a e un'altra stringa a e nient'altro, quale sarà la sottosequenza comune più lunga qui? La lunghezza dell'LCS qui sarà 1. Ora diamo un'occhiata a Table [1] [2] . Abbiamo string ab e string a . La lunghezza dell'LCS sarà 1. Come puoi vedere, il resto dei valori sarà anche 1 per la prima riga poiché considera solo la stringa a con abcd , abcda , abcdaf . Quindi il nostro tavolo sarà simile a:
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 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Per la riga 2, che includerà ora c . Per la tabella [2] [1] abbiamo ac su un lato e una dall'altro. Quindi la lunghezza della LCS è 1. Da dove abbiamo preso questo 1? Dall'alto, che indica la LCS a tra due sottostringhe. Quindi, quello che stiamo dicendo è che se s1 [2] e s2 [1] non sono gli stessi, allora la lunghezza dell'LCS sarà il massimo della lunghezza di LCS in alto o a sinistra . Prendendo la lunghezza della LCS in alto denota che, non prendiamo il carattere corrente da s2 . Allo stesso modo, Prendendo la lunghezza del LCS a sinistra denota che, non prendiamo il carattere corrente da s1 per creare l'LCS. Noi abbiamo:
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 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Quindi la nostra prima formula sarà:
if s2[i] is not equal to s1[j]
Table[i][j] = max(Table[i-1][j], Table[i][j-1]
endif
Andando avanti, per Table [2] [2] abbiamo string ab e ac . Dato che c eb non sono gli stessi, mettiamo il massimo della cima o della sinistra qui. In questo caso, è ancora 1. Dopo di ciò, per Table [2] [3] abbiamo string abc e ac . Questa volta i valori correnti di entrambe le righe e colonne sono gli stessi. Ora la lunghezza dell'LCS sarà uguale alla lunghezza massima di LCS finora + 1. Come otteniamo la lunghezza massima di LCS finora? Controlliamo il valore diagonale, che rappresenta la migliore corrispondenza tra ab e a . Da questo stato, per i valori attuali, abbiamo aggiunto un altro carattere a s1 e s2, che è risultato essere lo stesso. Quindi ovviamente aumenterà la lunghezza di LCS. Inseriremo 1 + 1 = 2 nella Tabella [2] [3] . Noi abbiamo,
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 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Quindi la nostra seconda formula sarà:
if s2[i] equals to s1[j]
Table[i][j] = Table[i-1][j-1] + 1
endif
Abbiamo definito entrambi i casi. Usando queste due formule, possiamo popolare l'intera tabella. Dopo aver riempito il tavolo, sarà simile a questo:
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 lunghezza dell'LCS tra s1 e s2 sarà Table [5] [6] = 4 . Qui, 5 e 6 sono rispettivamente la lunghezza di s2 e s1 . Il nostro pseudo-codice sarà:
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 complessità temporale per questo algoritmo è: O (mn) dove m e n denota la lunghezza di ciascuna stringa.
Come scopriamo la sottosequenza comune più lunga? Inizieremo dall'angolo in basso a destra. Controlleremo da dove arriverà il valore. Se il valore proviene dalla diagonale, ovvero se Table [i-1] [j-1] è uguale a Table [i] [j] - 1 , spingiamo s2 [i] o s1 [j] (entrambi sono uguali) e si muovono in diagonale. Se il valore proviene dall'alto, ciò significa che se Tabella [i-1] [j] è uguale a Tabella [i] [j] , passiamo all'inizio. Se il valore proviene da sinistra, ciò significa che se Table [i] [j-1] è uguale a Table [i] [j] , ci spostiamo a sinistra. Quando raggiungiamo la colonna più a sinistra o più in alto, la ricerca termina. Quindi inseriamo i valori dallo stack e li stampiamo. Lo pseudo-codice:
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
Punto da notare: se la tabella [i-1] [j] e la tabella [i] [j-1] sono uguali a Tabella [i] [j] e Tabella [i-1] [j-1] non è uguale a Table [i] [j] - 1 , ci possono essere due LCS per quel momento. Questo pseudo-codice non considera questa situazione. Dovrai risolvere questo in modo ricorsivo per trovare più LCS.
La complessità temporale per questo algoritmo è: O (max (m, n)) .
Il più lungo aumento successivo
L'attività consiste nel trovare la lunghezza della sottosequenza più lunga in un determinato array di numeri interi in modo tale che tutti gli elementi della sottosequenza siano ordinati in ordine crescente. Ad esempio, la lunghezza della sottosequenza crescente più lunga (LIS) per {15, 27, 14, 38, 26, 55, 46, 65, 85} è 6 e la sottosequenza crescente più lunga è {15, 27, 38, 55, 65, 85} . Ancora una volta per {3, 4, -1, 0, 6, 2, 3} la lunghezza di LIS è 4 e la sottosequenza è {-1, 0, 2, 3} . Useremo la programmazione dinamica per risolvere questo problema.
Prendiamo il secondo esempio: Item = {3, 4, -1, 0, 6, 2, 3} . Inizieremo prendendo un array dp della stessa dimensione della nostra sequenza. dp [i] rappresenta la lunghezza della LIS se includiamo l'i-esimo elemento della nostra sequenza originale. All'inizio sappiamo che per ogni oggetto almeno la sottosequenza crescente più lunga è di lunghezza 1 . Questo è considerando il singolo elemento stesso. Quindi inizializzeremo l'array dp con 1 . Avremo due variabili io e j . Inizialmente sarò 1 e j sarà 0. Il nostro array sarà simile a:
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
Il numero sopra la matrice rappresenta l'elemento corrispondente della nostra sequenza. La nostra strategia sarà:
if Item[i] > Item[j]
dp[i] := dp[j] + 1
Ciò significa che se l'elemento a i è maggiore di elemento a j, la lunghezza della LIS che contiene elemento a j, aumenterà di lunghezza 1 se includiamo elemento ai con esso. Nel nostro esempio, per i = 1 e j = 0 , l' elemento [i] è maggiore dell'articolo [j] . Quindi dp [i] = dp [j] + 1 . Il nostro array sarà simile a:
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
Ad ogni passo, aumenteremo j fino a i e quindi resettiamo j a 0 e incrementiamo i . Per ora, j ha raggiunto i , quindi incrementiamo 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
Per i = 2 , j = 0 , Item [i] non è maggiore di Item [j] , quindi non facciamo nulla e incrementiamo 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
Per i = 2 , j = 1 , Item [i] non è maggiore di Item [j] , quindi non facciamo nulla e poiché j ha raggiunto il limite, incrementiamo i e resettiamo 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
Per i = 3 , j = 0 , Item [i] non è maggiore di Item [j] , quindi non facciamo nulla e incrementiamo 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
Per i = 3 , j = 1 , Item [i] non è maggiore di Item [j] , quindi non facciamo nulla e incrementiamo 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
Per i = 3 , j = 2 , Item [i] è maggiore di Item [j] , quindi dp [i] = dp [j] + 1 . Dopo che j ha raggiunto il suo limite, di nuovo abbiamo azzerato j a 0 e incrementiamo 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
Per i = 4 e j = 0 , l' elemento [i] è maggiore di Item [j] , quindi dp [i] = dp [j] + 1 . Successivamente, incrementiamo 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
Per i = 4 e j = 1 , l' elemento [i] è maggiore dell'articolo [j] . Possiamo anche notare che dp [i] = dp [j] + 1 ci fornirà 3 , il che significa che se prendiamo il LIS per Item [j] e aggiungiamo Item [i] con esso, otterremo un LIS migliore 3,4,6} di prima {3,6}. Quindi abbiamo impostato dp [i] = dp [j] + 1 . Quindi incrementiamo 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
Per i = 4 e j = 2 , l' elemento [i] è maggiore dell'articolo [j] . Ma per questo caso, se impostiamo dp [i] = dp [j] + 1 , otterremo 2 , che è {-1,6} non il migliore {3,4,6} che possiamo fare usando Item [ io] . Quindi scartiamo questo. Aggiungeremo una condizione alla nostra strategia, ovvero:
if Item[i]>Item[j] and dp[i]<dp[j] + 1
dp[i] := dp[j] + 1
Aumentiamo j di 1 . Seguendo questa strategia, se completiamo il nostro array dp , sembrerà:
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
Ora eseguiremo l'iterazione attraverso questo array e scopriremo il valore massimo, che sarà la lunghezza del LIS. Il nostro pseudo-codice sarà:
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 complessità temporale di questo algoritmo è O(n²) dove n è la lunghezza della sequenza.
Per scoprire la sequenza originale, abbiamo bisogno di scorrere all'indietro e abbinarlo alla nostra lunghezza. La procedura è:
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 complessità temporale di questo algoritmo è: O(n) .
La successiva conseguenza Palindromica
Dato una stringa qual è la sottosequenza palindromica più lunga (LPS) di essa? Prendiamo una stringa agbdba . LPS di questa stringa è abdba di lunghezza 5 . Ricorda, dal momento che stiamo cercando una sottosequenza , i caratteri non devono necessariamente essere continui nella stringa originale. La sottostringa palindromica più lunga della sequenza sarebbe bdb di lunghezza 3 . Ma ci concentreremo sulla sottosequenza qui. Useremo la programmazione dinamica per risolvere questo problema.
Inizialmente, prenderemo un array 2D della stessa dimensione della nostra sequenza originale. Per il nostro esempio: S = "agbdba" , prenderemo dp [6] [6] array. Qui, dp [i] [j] rappresenta la lunghezza dell'LPS che possiamo creare se consideriamo i caratteri da s [i] a s [j] . Per esempio. se la nostra stringa fosse aa , dp [0] [1] memorizzerebbe 2 . Ora considereremo diverse lunghezze della nostra stringa e scopriremo la lunghezza più lunga che possiamo ricavarne.
Lunghezza = 1 :
Qui, stiamo considerando solo 1 personaggio alla volta. Quindi se avessimo una stringa di lunghezza 1 , qual è il LPS che possiamo avere? Ovviamente la risposta è 1 . Come conservarlo? dp [i] [j] dove i è uguale a j rappresenta una stringa di lunghezza 1 . Quindi imposteremo dp [0] [0] , dp [1] [1] , dp [2] [2] , dp [3] [3] , dp [4] [4] , dp [5] [ Da 5] a 1 . Il nostro array sarà simile a:
+---+---+---+---+---+---+---+
| | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
| 0 | 1 | | | | | |
+---+---+---+---+---+---+---+
| 1 | | 1 | | | | |
+---+---+---+---+---+---+---+
| 2 | | | 1 | | | |
+---+---+---+---+---+---+---+
| 3 | | | | 1 | | |
+---+---+---+---+---+---+---+
| 4 | | | | | 1 | |
+---+---+---+---+---+---+---+
| 5 | | | | | | 1 |
+---+---+---+---+---+---+---+
Lunghezza = 2 :
Questa volta considereremo le stringhe di lunghezza 2 . Considerando ora le stringhe di lunghezza 2 , la lunghezza massima di LPS può essere 2 se e solo se i due caratteri della stringa sono uguali. Quindi la nostra strategia sarà:
j := i + Length - 1
if s[i] is equal to s[j]
dp[i][j] := 2
else
dp[i][j] := 1
Se riempiamo il nostro array seguendo la strategia per Length = 2 , otterremo:
+---+---+---+---+---+---+---+
| | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
| 0 | 1 | 1 | | | | |
+---+---+---+---+---+---+---+
| 1 | | 1 | 1 | | | |
+---+---+---+---+---+---+---+
| 2 | | | 1 | 1 | | |
+---+---+---+---+---+---+---+
| 3 | | | | 1 | 1 | |
+---+---+---+---+---+---+---+
| 4 | | | | | 1 | 1 |
+---+---+---+---+---+---+---+
| 5 | | | | | | 1 |
+---+---+---+---+---+---+---+
Lunghezza = 3 :
Ora guardiamo 3 caratteri alla volta per la nostra stringa originale. Da ora in poi il LPS che possiamo fare dalla nostra stringa sarà determinato da:
- Se il primo e l'ultimo personaggio corrispondono avremo almeno 2 elementi da cui possiamo creare l'LPS + se escludiamo il primo e l'ultimo carattere, quale mai il meglio che possiamo fare dalla rimanente stringa.
- Se il primo e l'ultimo personaggio non corrispondono, il LPS che possiamo fare verrà o escludendo il primo carattere o l'ultimo carattere, che abbiamo già calcolato.
Per estivare,
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
Se riempiamo l'array dp per Length = 3 a Length = 6 , otterremo:
+---+---+---+---+---+---+---+
| | 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 |
+---+---+---+---+---+---+---+
Questo è il nostro array dp richiesto e dp [0] [5] conterrà la lunghezza dell'LPS. La nostra procedura sarà simile a:
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 complessità temporale di questo algoritmo è O(n²) , dove n è la lunghezza della nostra stringa data. Il problema Palindromico di Successione più lungo è strettamente correlato alla Successione Comune Più Lunga. Se prendiamo la seconda stringa come l'opposto della prima stringa e calcoliamo la lunghezza e stampiamo il risultato, questa sarà la più lunga sottosequenza palindromica della stringa data. La complessità di tale algoritmo è anche O(n²) .