dynamic-programming
Vervolggerelateerde algoritmen
Zoeken…
Langste gemeenschappelijke gevolg
Een van de belangrijkste implementaties van Dynamic Programming is het achterhalen van de langste gemeenschappelijke opeenvolging . Laten we eerst enkele basisterminologieën definiëren.
Subsequence:
Een subreeks is een reeks die kan worden afgeleid uit een andere reeks door enkele elementen te verwijderen zonder de volgorde van de resterende elementen te wijzigen. Laten we zeggen dat we een tekenreeks ABC hebben . Als we nul of een of meer dan één teken uit deze tekenreeks wissen, krijgen we de deelreeks van deze tekenreeks. De deelreeksen van tekenreeks ABC zijn dus { "A" , "B" , "C" , "AB" , "AC" , "BC" , "ABC" , "" }. Zelfs als we alle tekens verwijderen, is de lege tekenreeks ook een deelreeks. Om de deelreeks te achterhalen, hebben we voor elke tekens in een string twee opties - ofwel nemen we het karakter, ofwel niet. Dus als de lengte van de string n is , zijn er 2 n deelreeksen van die string.
Langste gemeenschappelijke gevolg:
Zoals de naam al doet vermoeden, is van alle gemeenschappelijke deelreeksen tussen twee strings de langste gemeenschappelijke deelreeks (LCS) die met de maximale lengte. Bijvoorbeeld: de gemeenschappelijke deelreeksen tussen "HELLOM" en "HMLD" zijn "H" , "HL" , "HM" enz. Hier is "HLL" de langste gemeenschappelijke deelreeks met lengte 3.
Brute-Force methode:
We kunnen alle subreeksen van twee strings genereren met behulp van backtracking . Dan kunnen we ze vergelijken om de gemeenschappelijke deelreeksen te ontdekken. Nadat we die met de maximale lengte moeten vinden. We hebben al gezien dat er 2 n deelreeksen van een reeks van lengte n zijn . Het zou jaren duren om het probleem op te lossen als onze n 20-25 kruist.
Dynamische programmeermethode:
Laten we onze methode benaderen met een voorbeeld. Stel dat we twee tekenreeksen abcdaf en acbcf hebben . Laten we deze aangeven met s1 en s2 . Dus de langste gemene deelreeks van deze twee reeksen is "abcf" , die lengte 4 heeft. Nogmaals herinner ik u eraan, de volgordes hoeven niet continu in de reeks te zijn. Om "abcf" te construeren, negeerden we "da" in s1 en "c" in s2 . Hoe komen we hier achter met Dynamic Programming?
We beginnen met een tabel (een 2D-array) met alle tekens van s1 op een rij en alle tekens van s2 in kolom. Hier is de tabel 0-geïndexeerd en plaatsen we de tekens van 1 tot en met. We zullen de tabel voor elke rij van links naar rechts doorkruisen. Onze tafel ziet eruit als:
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 | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Hier vertegenwoordigen elke rij en kolom de lengte van de langste gemeenschappelijke deelreeks tussen twee tekenreeksen als we de tekens van die rij en kolom nemen en toevoegen aan het voorvoegsel ervoor. Bijvoorbeeld: Tabel [2] [3] vertegenwoordigt de lengte van de langste gemeenschappelijke deelreeks tussen "ac" en "abc" .
De 0-de kolom geeft de lege deelreeks van s1 weer . Op dezelfde manier vertegenwoordigt de 0-de rij de lege deelreeks van s2 . Als we een lege deelreeks van een string nemen en proberen deze te matchen met een andere string, ongeacht hoe lang de lengte van de tweede substring is, heeft de gemeenschappelijke deelreeks 0 lengte. Dus we kunnen de 0-de rijen en 0-de kolommen vullen met 0'en. We krijgen:
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 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Laten we beginnen. Als we tabel [1] [1] vullen, vragen we ons af of we een string a en een andere string a en niets anders hebben, wat is de langste gemeenschappelijke deel hier? De lengte van de LCS is hier 1. Laten we nu eens kijken naar tabel [1] [2] . We hebben string ab en string a . De lengte van de LCS is 1. Zoals u kunt zien, is de rest van de waarden ook 1 voor de eerste rij, omdat deze alleen string a beschouwt met abcd , abcda , abcdaf . Onze tafel ziet er dus uit als:
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 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Voor rij 2, die nu c bevat . Voor tabel [2] [1] hebben we ac aan de ene kant en een aan de andere kant. Dus de lengte van de LCS is 1. Waar hebben we deze 1 vandaan? Vanaf de top, waarbij de LCS duidt een tussen twee subreeksen. Dus wat we zeggen is, als s1 [2] en s2 [1] niet hetzelfde zijn, dan is de lengte van de LCS het maximum van de lengte van de LCS bovenaan of links . Als we de lengte van de LCS bovenaan nemen, geven we aan dat we het huidige teken van s2 niet nemen. Evenzo betekent het nemen van de lengte van de LCS aan de linkerkant dat we het huidige teken van s1 niet nemen om de LCS te maken. We krijgen:
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 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Dus onze eerste formule zal zijn:
if s2[i] is not equal to s1[j]
Table[i][j] = max(Table[i-1][j], Table[i][j-1]
endif
Verdergaand, voor tabel [2] [2] hebben we string ab en ac . Omdat c en b niet hetzelfde zijn, plaatsen we hier het maximum van de top of links. In dit geval is het weer 1. Daarna hebben we voor tabel [2] [3] tekenreeks abc en ac . Deze tijd huidige waarden van zowel rij als kolom zijn hetzelfde. Nu zal de lengte van de LCS gelijk zijn aan de maximale lengte van LCS tot nu toe + 1. Hoe krijgen we de maximale lengte van LCS tot nu toe? We controleren de diagonale waarde, die de beste overeenkomst tussen ab en a vertegenwoordigt . Vanuit deze status hebben we voor de huidige waarden nog een teken toegevoegd aan s1 en s2, wat toevallig hetzelfde was. Dus de lengte van LCS zal natuurlijk toenemen. We plaatsen 1 + 1 = 2 in tabel [2] [3] . We krijgen,
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 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Dus onze tweede formule zal zijn:
if s2[i] equals to s1[j]
Table[i][j] = Table[i-1][j-1] + 1
endif
We hebben beide gevallen gedefinieerd. Met behulp van deze twee formules kunnen we de hele tabel vullen. Na het vullen van de tabel ziet het er als volgt uit:
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 |
+-----+-----+-----+-----+-----+-----+-----+-----+
De lengte van de LCS tussen s1 en s2 is tabel [5] [6] = 4 . Hier zijn 5 en 6 respectievelijk de lengte van s2 en s1 . Onze pseudo-code zal zijn:
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]
De tijdcomplexiteit voor dit algoritme is: O (mn) waarbij m en n de lengte van elke reeks aangeeft.
Hoe komen we erachter wat de langst voorkomende deelreeks is? We beginnen vanuit de rechteronderhoek. We zullen controleren waar de waarde vandaan komt. Als de waarde uit de diagonaal komt, dat wil zeggen dat tabel [i-1] [j-1] gelijk is aan tabel [i] [j] - 1 , drukken we op s2 [i] of s1 [j] (beide hetzelfde zijn) en diagonaal bewegen. Als de waarde van boven komt, betekent dit dat als Tabel [i-1] [j] gelijk is aan Tabel [i] [j] , we naar de top gaan. Als de waarde van links komt, betekent dit dat als Tabel [i] [j-1] gelijk is aan Tabel [i] [j] , we naar links gaan. Wanneer we de meest linkse of bovenste kolom bereiken, eindigt onze zoekopdracht. Vervolgens halen we de waarden uit de stapel en drukken ze af. De pseudo-code:
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
Op te merken punt: als zowel tabel [i-1] [j] als tabel [i] [j-1] gelijk is aan tabel [i] [j] en tabel [i-1] [j-1] niet gelijk aan Tabel [i] [j] - 1 , er kunnen op dat moment twee LCS zijn. Deze pseudo-code houdt geen rekening met deze situatie. U moet dit recursief oplossen om meerdere LCS's te vinden.
De tijdcomplexiteit voor dit algoritme is: O (max (m, n)) .
Langst stijgende volgorde
De taak is om de lengte van de langste deelreeks in een bepaalde reeks gehele getallen te vinden, zodat alle elementen van de deelreeks in oplopende volgorde worden gesorteerd. De lengte van de langst toenemende deelreeks (LIS) voor {15, 27, 14, 38, 26, 55, 46, 65, 85} is bijvoorbeeld 6 en de langst toenemende deelreeks is {15, 27, 38, 55, 65, 85} . Opnieuw voor {3, 4, -1, 0, 6, 2, 3} lengte van LIS is 4 en de subreeks is {-1, 0, 2, 3} . We zullen dynamische programmering gebruiken om dit probleem op te lossen.
Laten we het tweede voorbeeld nemen: Item = {3, 4, -1, 0, 6, 2, 3} . We beginnen met het nemen van de array dp van dezelfde grootte van onze reeks. dp [i] vertegenwoordigt de lengte van het LIS als we het i- de item in onze oorspronkelijke reeks opnemen. In het allereerste begin weten we dat voor elk item ten minste de langst toenemende deelreeks van lengte 1 is . Dat is door het enkele element zelf te overwegen. Dus initialiseren we de dp- array met 1 . We hebben twee variabelen i en j . Aanvankelijk i bedraagt 1 en j zal zijn 0. Onze reeks ziet eruit als:
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
Het getal boven de reeks vertegenwoordigt het overeenkomstige element van onze reeks. Onze strategie zal zijn:
if Item[i] > Item[j]
dp[i] := dp[j] + 1
Dat betekent dat als element bij i groter is dan element bij j , de lengte van het LIS dat element bij j bevat, met lengte 1 toeneemt als we element at i erbij betrekken. In ons voorbeeld is artikel [i] voor i = 1 en j = 0 groter dan artikel [j] . Dus dp [i] = dp [j] + 1 . Onze reeks ziet eruit als:
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
Bij elke stap verhogen we j tot i en stellen we j vervolgens opnieuw in op 0 en verhogen we i . Voor nu heeft j i bereikt, dus we verhogen i tot 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
Voor i = 2 , j = 0 , is Item [i] niet groter dan Item [j] , dus we doen niets en verhogen 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
Voor i = 2 , j = 1 , is item [i] niet groter dan item [j] , dus we doen niets en omdat j zijn limiet heeft bereikt, verhogen we i en stellen j opnieuw in op 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
Voor i = 3 , j = 0 , is Item [i] niet groter dan Item [j] , dus we doen niets en verhogen 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
Voor i = 3 , j = 1 , is artikel [i] niet groter dan artikel [j] , dus we doen niets en verhogen 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
Voor i = 3 , j = 2 , is item [i] groter dan item [j] , dus dp [i] = dp [j] + 1 . Nadat j zijn limiet heeft bereikt, stellen we opnieuw j in op 0 en verhogen we 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
Voor i = 4 en j = 0 is item [i] groter dan item [j] , dus dp [i] = dp [j] + 1 . Daarna verhogen we 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
Voor i = 4 en j = 1 is item [i] groter dan item [j] . We merken ook dat dp [i] = dp [j] + 1 ons 3 levert, wat betekent dat als we het LIS voor item [j] nemen en item [i] toevoegen, we een beter LIS krijgen { 3,4,6} dan voorheen {3,6}. Dus stellen we dp [i] = dp [j] + 1 in . Dan verhogen we 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
Voor i = 4 en j = 2 is item [i] groter dan item [j] . Maar als we in dit geval dp [i] = dp [j] + 1 instellen , krijgen we 2 , wat {-1,6} is, niet de beste {3,4,6} die we kunnen doen met Item [ i] . Dus we negeren deze. We voegen een voorwaarde toe aan onze strategie, namelijk:
if Item[i]>Item[j] and dp[i]<dp[j] + 1
dp[i] := dp[j] + 1
We verhogen j met 1 . Naar aanleiding van deze strategie, als we onze dp-array te voltooien, zal het eruit:
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
Nu zullen we deze array doorlopen en de maximale waarde vinden, die de lengte van het LIS zal zijn. Onze pseudo-code zal zijn:
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
De tijdcomplexiteit van dit algoritme is O(n²) waarbij n de lengte van de reeks is.
Om de oorspronkelijke volgorde te achterhalen, moeten we achteruitgaan en deze afstemmen op onze lengte. De procedure is:
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
De tijdcomplexiteit van dit algoritme is: O(n) .
Langste palindromische sequentie
Wat is de langste palindrome deelreeks (LPS) ervan? Laten we een string nemen agbdba . De LPS van deze string is abdba van lengte 5 . Onthoud dat, aangezien we op zoek zijn naar deelreeksen , de karakters niet continu hoeven te zijn in de originele string. De langste palindrome substring van de reeks zou een lengte van 3 dB hebben . Maar we zullen ons hier concentreren op de deelreeks . We gaan dynamisch programmeren gebruiken om dit probleem op te lossen.
Eerst nemen we een 2D-array met dezelfde dimensie van onze oorspronkelijke reeks. Voor ons voorbeeld: S = "agbdba" , nemen we de array dp [6] [6] . Hier vertegenwoordigt dp [i] [j] de lengte van de LPS die we kunnen maken als we de tekens van s [i] tot s [j] beschouwen . Bijvoorbeeld. als onze string aa was , zou dp [0] [1] 2 opslaan. Nu zullen we verschillende lengtes van onze string overwegen en de langst mogelijke lengte vinden die we er van kunnen maken.
Lengte = 1 :
Hier overwegen we slechts 1 karakter per keer. Dus als we een reeks van lengte 1 hadden , wat is dan de LPS die we kunnen hebben? Natuurlijk is het antwoord 1 . Hoe bewaart u het? dp [i] [j] waar i gelijk is aan j staat voor een string van lengte 1 . Dus we zullen dp [0] [0] , dp [1] [1] , dp [2] [2] , dp [3] [3] , dp [4] [4] , dp [5] [ 5] tot 1 . Onze reeks ziet eruit als:
+---+---+---+---+---+---+---+
| | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
| 0 | 1 | | | | | |
+---+---+---+---+---+---+---+
| 1 | | 1 | | | | |
+---+---+---+---+---+---+---+
| 2 | | | 1 | | | |
+---+---+---+---+---+---+---+
| 3 | | | | 1 | | |
+---+---+---+---+---+---+---+
| 4 | | | | | 1 | |
+---+---+---+---+---+---+---+
| 5 | | | | | | 1 |
+---+---+---+---+---+---+---+
Lengte = 2 :
Deze keer zullen we strings van lengte 2 overwegen. Nu rekening houdend met strings met lengte 2 , kan de maximale lengte van LPS 2 zijn als en alleen als de twee tekens van de string hetzelfde zijn. Dus onze strategie zal zijn:
j := i + Length - 1
if s[i] is equal to s[j]
dp[i][j] := 2
else
dp[i][j] := 1
Als we onze matrix vullen volgens de strategie voor Lengte = 2 , krijgen we:
+---+---+---+---+---+---+---+
| | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
| 0 | 1 | 1 | | | | |
+---+---+---+---+---+---+---+
| 1 | | 1 | 1 | | | |
+---+---+---+---+---+---+---+
| 2 | | | 1 | 1 | | |
+---+---+---+---+---+---+---+
| 3 | | | | 1 | 1 | |
+---+---+---+---+---+---+---+
| 4 | | | | | 1 | 1 |
+---+---+---+---+---+---+---+
| 5 | | | | | | 1 |
+---+---+---+---+---+---+---+
Lengte = 3 :
Nu kijken we tegelijkertijd naar 3 karakters voor onze originele string. Vanaf nu worden de LPS die we kunnen maken van onze string bepaald door:
- Als de eerste en laatste tekens overeenkomen, hebben we ten minste 2 items waaruit we de LPS + kunnen maken als we het eerste en laatste teken uitsluiten, wat we ooit het beste kunnen maken van de resterende tekenreeks.
- Als de eerste en laatste tekens niet overeenkomen, komt de LPS die we kunnen maken van het eerste teken of het laatste teken, dat we al hebben berekend.
Zomers maken,
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
Als we de dp- array invullen voor Lengte = 3 tot Lengte = 6 , krijgen we:
+---+---+---+---+---+---+---+
| | 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 |
+---+---+---+---+---+---+---+
Dit is onze vereiste dp- array en dp [0] [5] zal de lengte van de LPS bevatten. Onze procedure ziet er als volgt uit:
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]
De tijdcomplexiteit van dit algoritme is O(n²) , waarbij n de lengte is van onze gegeven string. Het probleem met de langste palindromische opeenvolging hangt nauw samen met de langste gemeenschappelijke opeenvolging. Als we de tweede string als het omgekeerde van de eerste string nemen en de lengte berekenen en het resultaat afdrukken, is dat de langste palindrome deelreeks van de gegeven string. De complexiteit van dat algoritme is ook O(n²) .