dynamic-programming
Algorytmy związane z kolejnością
Szukaj…
Najdłuższa wspólna kolejność
Jedną z najważniejszych implementacji programowania dynamicznego jest znalezienie najdłuższej wspólnej podsekwencji . Najpierw zdefiniujmy niektóre podstawowe terminologie.
Kolejność:
Podsekwencja to sekwencja, którą można uzyskać z innej sekwencji poprzez usunięcie niektórych elementów bez zmiany kolejności pozostałych elementów. Powiedzmy, że mamy ciąg ABC . Jeśli usuniemy zero lub jeden lub więcej niż jeden znak z tego ciągu, otrzymamy podsekwencję tego ciągu. Tak więc podsekwencje ciągu ABC będą to { „A” , „B” , „C” , „AB” , „AC” , „BC” , „ABC” , „” }. Nawet jeśli usuniemy wszystkie znaki, pusty ciąg będzie również podsekwencją. Aby znaleźć podsekwencję, dla każdego znaku w ciągu mamy dwie opcje - albo przyjmujemy znak, albo nie. Jeśli więc długość ciągu wynosi n , istnieją 2 n podciągów tego ciągu.
Najdłuższa wspólna kolejność:
Jak sama nazwa wskazuje, spośród wszystkich wspólnych podsekwencji między dwoma łańcuchami najdłuższa wspólna podsekwencja (LCS) to ta o maksymalnej długości. Na przykład: Wspólne podsekwencje między „HELLOM” i „HMLD” to „H” , „HL” , „HM” itd. Tutaj „HLL” jest najdłuższym wspólnym podsekwencją o długości 3.
Metoda Brute-Force:
Możemy wygenerować wszystkie podsekwencje dwóch łańcuchów za pomocą śledzenia wstecznego . Następnie możemy je porównać, aby znaleźć typowe podsekwencje. Po tym będziemy musieli znaleźć ten o maksymalnej długości. Widzieliśmy już, że istnieją 2 n podsekwencje ciągu o długości n . Rozwiązanie problemu zajęłoby lata, gdyby nasze n przekroczyło 20-25 .
Metoda programowania dynamicznego:
Podejdźmy do naszej metody z przykładem. Załóżmy, że mamy dwa ciągi abcdaf i acbcf . Oznaczmy je za pomocą s1 i s2 . Zatem najdłuższym wspólnym podsekwencją tych dwóch ciągów będzie „abcf” , który ma długość 4. Ponownie przypominam, podsekwencje nie muszą być ciągłe w ciągu. Aby skonstruować „abcf” , zignorowaliśmy „da” w s1 i „c” w s2 . Jak możemy się tego dowiedzieć za pomocą programowania dynamicznego?
Zaczniemy od tabeli (tablicy 2D) zawierającej wszystkie znaki s1 w rzędzie i wszystkie znaki s2 w kolumnie. Tutaj tabela jest indeksowana do 0, a my umieszczamy znaki od 1 do kolejnych. Przejdziemy przez tabelę od lewej do prawej dla każdego wiersza. Nasz stół będzie wyglądał następująco:
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 | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Tutaj każdy wiersz i kolumna reprezentują długość najdłuższego wspólnego podsekwencji między dwoma łańcuchami, jeśli weźmiemy znaki tego wiersza i kolumny i dodamy do przedrostka przed nim. Na przykład: Tabela [2] [3] reprezentuje długość najdłuższej wspólnej podsekwencji między „ac” i „abc” .
0-ta kolumna reprezentuje pustą podsekwencję s1 . Podobnie 0-ty rząd reprezentuje pustą podsekwencję s2 . Jeśli weźmiemy pusty podciąg łańcucha i spróbujemy dopasować go do innego łańcucha, bez względu na długość drugiego podłańcucha, wspólny podciąg będzie miał długość 0. Możemy więc wypełnić 0-te rzędy i 0-te kolumny zerami. Otrzymujemy:
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 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Zaczynajmy. Kiedy wypełniamy tabelę [1] [1] , zadajemy sobie pytanie, czy jeśli mielibyśmy ciąg a i kolejny ciąg a i nic więcej, jaka będzie najdłuższa wspólna podsekwencja? Długość LCS tutaj będzie wynosić 1. Spójrzmy teraz na Tabelę [1] [2] . Mamy ciąg ab i ciąg a . Długość LCS będzie wynosić 1. Jak widać, reszta wartości będzie również równa 1 dla pierwszego wiersza, ponieważ uwzględnia tylko łańcuch a z abcd , abcda , abcdaf . Nasz stół będzie wyglądał następująco:
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 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Dla wiersza 2, który będzie teraz obejmował c . Dla tabeli [2] [1] mamy ac z jednej strony i a z drugiej strony. Zatem długość LCS wynosi 1. Skąd wzięliśmy ten 1? Od góry, co oznacza LCS a między dwoma podciągami. Mówimy więc, że jeśli s1 [2] i s2 [1] nie są takie same, to długość LCS będzie maksymalną długością LCS u góry lub po lewej stronie . Biorąc pod uwagę długość LCS u góry, oznacza to, że nie bierzemy obecnej postaci z s2 . Podobnie, biorąc pod uwagę długość LCS po lewej stronie, oznacza to, że nie bierzemy obecnego znaku z s1, aby utworzyć LCS. Otrzymujemy:
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 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Tak więc naszą pierwszą formułą będzie:
if s2[i] is not equal to s1[j]
Table[i][j] = max(Table[i-1][j], Table[i][j-1]
endif
Przechodząc dalej, do tabeli [2] [2] mamy ciąg ab i ac . Ponieważ C i B nie są takie same, możemy umieścić maksymalnie górę lub w lewo tutaj. W tym przypadku jest to znowu 1. Następnie, dla tabeli [2] [3] mamy ciąg abc i ac . Tym razem aktualne wartości zarówno wiersza, jak i kolumny są takie same. Teraz długość LCS będzie równa maksymalnej dotychczasowej długości LCS + 1. Jak uzyskać maksymalną długość LCS do tej pory? Sprawdzamy wartość przekątną, która reprezentuje najlepsze dopasowanie między ab a a . Z tego stanu dla bieżących wartości dodaliśmy jeszcze jeden znak do s1 i s2, które okazały się być takie same. Długość LCS oczywiście wzrośnie. W tabeli [2] [3] umieścimy 1 + 1 = 2 . Dostajemy
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 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Zatem naszą drugą formułą będzie:
if s2[i] equals to s1[j]
Table[i][j] = Table[i-1][j-1] + 1
endif
Zdefiniowaliśmy oba przypadki. Korzystając z tych dwóch formuł, możemy wypełnić całą tabelę. Po wypełnieniu tabeli będzie wyglądać następująco:
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 |
+-----+-----+-----+-----+-----+-----+-----+-----+
Długość LCS między s1 i s2 będzie wynosić Tabela [5] [6] = 4 . Tutaj 5 i 6 są odpowiednio długością s2 i s1 . Nasz pseudo-kod będzie:
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]
Złożoność czasowa dla tego algorytmu wynosi: O (mn) gdzie m i n oznacza długość każdego łańcucha.
Jak znaleźć najdłuższą wspólną podsekwencję? Zaczniemy od prawego dolnego rogu. Sprawdzimy, skąd pochodzi wartość. Jeśli wartość pochodzi z przekątnej, to znaczy, jeśli tabela [i-1] [j-1] jest równa tabeli [i] [j] - 1 , naciskamy albo s2 [i], albo s1 [j] (oba są takie same) i poruszają się po przekątnej. Jeśli wartość pochodzi z góry, oznacza to, że jeśli Tabela [i-1] [j] jest równa Tabeli [i] [j] , przechodzimy na górę. Jeśli wartość pochodzi z lewej strony, oznacza to, że jeśli Tabela [i] [j-1] jest równa Tabeli [i] [j] , przechodzimy w lewo. Gdy dojdziemy do lewej lub najwyższej kolumny, nasze wyszukiwanie się kończy. Następnie usuwamy wartości ze stosu i drukujemy je. Pseudo-kod:
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
Należy zauważyć: jeśli zarówno Tabela [i-1] [j], jak i Tabela [i] [j-1] jest równa Tabeli [i] [j] i Tabela [i-1] [j-1] nie jest równe tabeli [i] [j] - 1 , dla tego momentu mogą istnieć dwa LCS. Ten pseudo-kod nie uwzględnia tej sytuacji. Musisz rozwiązać to rekurencyjnie, aby znaleźć wiele LCS.
Złożoność czasowa dla tego algorytmu wynosi: O (maks. (M, n)) .
Najdłuższa rosnąca kolejność
Zadanie polega na znalezieniu długości najdłuższego podsekwencji w danej tablicy liczb całkowitych, tak aby wszystkie elementy podsekwencji były sortowane w porządku rosnącym. Na przykład długość najdłużej rosnącego podsekwencji (LIS) dla {15, 27, 14, 38, 26, 55, 46, 65, 85} wynosi 6, a najdłuższy rosnący podsekwencja to {15, 27, 38, 55, 65, 85} . Znów dla {3, 4, -1, 0, 6, 2, 3} długości LIS wynosi 4, a podsekwencja to {-1, 0, 2, 3} . Użyjemy programowania dynamicznego, aby rozwiązać ten problem.
Weźmy drugi przykład: Item = {3, 4, -1, 0, 6, 2, 3} . Zaczniemy od pobrania tablicy dp tego samego rozmiaru z naszej sekwencji. dp [i] reprezentuje długość LIS jeśli uwzględnimy I th element naszej pierwotnej kolejności. Na samym początku wiemy, że dla każdego elementu co najmniej najdłużej rosnąca podsekwencja ma długość 1 . Jest tak, biorąc pod uwagę sam pojedynczy element. Więc zainicjujemy tablicę dp 1 . Będziemy mieć dwie zmienne i i j . Początkowo będzie 1 i J będzie 0. Nasza tablica będzie wyglądać następująco:
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
Liczba powyżej tablicy reprezentuje odpowiedni element naszej sekwencji. Nasza strategia będzie:
if Item[i] > Item[j]
dp[i] := dp[j] + 1
Oznacza to, że jeśli element w i jest większy niż element w j , długość LIS zawierającego element w j zwiększy się o długość 1, jeśli dołączymy do niego element w i . W naszym przykładzie dla i = 1 i j = 0 , pozycja [i] jest większa niż pozycja [j] . Więc dp [i] = dp [j] + 1 . Nasza tablica będzie wyglądać następująco:
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
Na każdym kroku zwiększamy j do i, a następnie resetujemy j do 0 i zwiększamy i . Na razie j osiągnął i , więc zwiększamy i do 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
Dla i = 2 , j = 0 , pozycja [i] nie jest większa niż pozycja [j] , więc nic nie robimy i zwiększamy wartość 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
Dla i = 2 , j = 1 , pozycja [i] nie jest większa niż pozycja [j] , więc nic nie robimy, a ponieważ j osiągnął swój limit, zwiększamy i resetujemy j do 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
Dla i = 3 , j = 0 , pozycja [i] nie jest większa niż pozycja [j] , więc nie robimy nic i zwiększamy wartość 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
Dla i = 3 , j = 1 , pozycja [i] nie jest większa niż pozycja [j] , więc nie robimy nic i zwiększamy wartość 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
Dla i = 3 , j = 2 , pozycja [i] jest większa niż pozycja [j] , więc dp [i] = dp [j] + 1 . Po tym, jak j osiągnął limit, ponownie resetujemy j do 0 i zwiększamy 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
Dla i = 4 i j = 0 , pozycja [i] jest większa niż pozycja [j] , więc dp [i] = dp [j] + 1 . Następnie zwiększamy 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
Dla i = 4 i j = 1 , pozycja [i] jest większa niż pozycja [j] . Możemy również zauważyć, że dp [i] = dp [j] + 1 zapewni nam 3 , co oznacza, że jeśli weźmiemy LIS dla przedmiotu [j] i dodamy do niego przedmiot [i] , otrzymamy lepszy LIS { 3,4,6} niż wcześniej {3,6}. Więc ustawiamy dp [i] = dp [j] + 1 . Następnie zwiększamy 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
Dla i = 4 i j = 2 pozycja [i] jest większa niż pozycja [j] . Ale w tym przypadku, jeśli ustawimy dp [i] = dp [j] + 1 , otrzymamy 2 , co oznacza {-1,6} nie najlepszy {3,4,6}, jaki możemy zrobić używając Item [ i] . Więc odrzucamy ten. Dodamy warunek do naszej strategii, czyli:
if Item[i]>Item[j] and dp[i]<dp[j] + 1
dp[i] := dp[j] + 1
Zwiększamy j o 1 . Zgodnie z tą strategią, jeśli uzupełnimy naszą tablicę dp , będzie ona wyglądać następująco:
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
Teraz przejdziemy przez tę tablicę i znajdziemy maksymalną wartość, która będzie długością LIS. Nasz pseudo-kod będzie:
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
Złożoność czasowa tego algorytmu wynosi O(n²) gdzie n jest długością sekwencji.
Aby znaleźć oryginalną sekwencję, musimy iterować wstecz i dopasowywać ją do naszej długości. Procedura jest następująca:
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
Złożoność czasowa tego algorytmu wynosi: O(n) .
Najdłuższa sekwencja palindromowa
Biorąc pod uwagę ciąg, jaka jest jego najdłuższa podsekwencja palindromowa (LPS)? Weźmy ciąg agbdba . LPS tego ciągu to abdba o długości 5 . Pamiętaj, ponieważ ponieważ szukamy podciągów , znaki nie muszą być ciągłe w oryginalnym ciągu. Najdłuższym palindromowym podciągiem sekwencji będzie bdb o długości 3 . Ale tutaj skoncentrujemy się na podsekwencji . Użyjemy programowania dynamicznego, aby rozwiązać ten problem.
Najpierw weźmiemy tablicę 2D o tym samym wymiarze z naszej oryginalnej sekwencji. W naszym przykładzie: S = "agbdba" weźmiemy tablicę dp [6] [6] . Tutaj dp [i] [j] reprezentuje długość LPS, którą możemy zrobić, jeśli weźmiemy pod uwagę znaki od s [i] do s [j] . Na przykład. jeśli nasz ciąg to aa , dp [0] [1] zapisze 2 . Teraz rozważymy różne długości naszego sznurka i ustalimy możliwie najdłuższą możliwą długość.
Długość = 1 :
Rozważamy tutaj tylko 1 postać na raz. Więc jeśli mielibyśmy ciąg długości 1 , jaki byłby LPS? Oczywiście odpowiedź brzmi 1 . Jak go przechowywać? dp [i] [j] gdzie i jest równe j oznacza ciąg o długości 1 . Więc ustawimy dp [0] [0] , dp [1] [1] , dp [2] [2] , dp [3] [3] , dp [4] [4] , dp [5] [ 5] do 1 . Nasza tablica będzie wyglądać następująco:
+---+---+---+---+---+---+---+
| | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
| 0 | 1 | | | | | |
+---+---+---+---+---+---+---+
| 1 | | 1 | | | | |
+---+---+---+---+---+---+---+
| 2 | | | 1 | | | |
+---+---+---+---+---+---+---+
| 3 | | | | 1 | | |
+---+---+---+---+---+---+---+
| 4 | | | | | 1 | |
+---+---+---+---+---+---+---+
| 5 | | | | | | 1 |
+---+---+---+---+---+---+---+
Długość = 2 :
Tym razem rozważymy łańcuchy o długości 2 . Biorąc pod uwagę ciągi o długości 2 , maksymalna długość LPS może wynosić 2 tylko wtedy, gdy dwa znaki ciągu są takie same. Tak więc naszą strategią będzie:
j := i + Length - 1
if s[i] is equal to s[j]
dp[i][j] := 2
else
dp[i][j] := 1
Jeśli wypełnimy naszą tablicę zgodnie ze strategią dla Length = 2 , otrzymamy:
+---+---+---+---+---+---+---+
| | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
| 0 | 1 | 1 | | | | |
+---+---+---+---+---+---+---+
| 1 | | 1 | 1 | | | |
+---+---+---+---+---+---+---+
| 2 | | | 1 | 1 | | |
+---+---+---+---+---+---+---+
| 3 | | | | 1 | 1 | |
+---+---+---+---+---+---+---+
| 4 | | | | | 1 | 1 |
+---+---+---+---+---+---+---+
| 5 | | | | | | 1 |
+---+---+---+---+---+---+---+
Długość = 3 :
Teraz patrzymy na 3 znaki na raz dla naszego oryginalnego ciągu. Od teraz LPS, który możemy wykonać z naszego łańcucha, będzie określony przez:
- Jeśli pierwszy i ostatni znak pasują do siebie, będziemy mieli co najmniej 2 elementy, z których możemy zrobić LPS +, jeśli wykluczymy pierwszy i ostatni znak, co najlepsze, co możemy zrobić z pozostałego ciągu.
- Jeśli pierwszy i ostatni znak nie pasują do siebie, LPS, który możemy wykonać, będzie pochodził z wykluczenia pierwszego znaku lub ostatniego znaku, który już obliczyliśmy.
Summerize
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
Jeśli wypełnimy tablicę dp dla Length = 3 do Length = 6 , otrzymamy:
+---+---+---+---+---+---+---+
| | 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 |
+---+---+---+---+---+---+---+
To jest nasza wymagana tablica dp, a dp [0] [5] będzie zawierać długość LPS. Nasza procedura będzie wyglądać następująco:
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]
Złożoność czasowa tego algorytmu wynosi O(n²) , gdzie n jest długością podanego ciągu. Najdłuższy problem podsekwencji palindromicznej jest ściśle związany z najdłuższą wspólną podsekwencją. Jeśli weźmiemy drugi ciąg jako odwrotność pierwszego ciągu i obliczymy długość i wydrukujemy wynik, będzie to najdłuższa podsekwencja palindromiczna danego ciągu. Złożoność tego algorytmu wynosi również O(n²) .