Wyobraź sobie, że masz dwa napisy: A = ABCDGH oraz B = AEDFHR.

Chcemy znaleźć najdłuższy wspólny podciąg LCS (ang. Longest Common Subsequence), czyli taki ciąg znaków, który:

• występuje w obu napisach w tej samej kolejności,

• ale nie musi zajmować kolejnych pozycji (to nie jest podciąg spójny, tylko podciąg).

Dla naszych ciągów jednym ze wspólnych podciągów jest np. ADH.

Pytanie brzmi: jaki jest najdłuższy możliwy taki podciąg i jak go znaleźć w sposób systematyczny, a nie „na oko”?

Klasyczne, „siłowe” sprawdzanie wszystkich podciągów byłoby skrajnie nieefektywne. Z pomocą przychodzi programowanie dynamiczne: zamiast rozwiązywać duży problem naraz, rozbijemy go na wiele mniejszych, częściowo się pokrywających podproblemów, zapiszemy ich wyniki w tabeli i wykorzystamy je ponownie.

Krok po kroku wygląda to tak:

1. Tworzymy tabelę
   Budujemy tablicę dp o wymiarach [n+1]x[m+1], gdzie n to długość ciągu A, a m długość ciągu B.
   W naszym przykładzie: n = 6 (ABCDGH), m = 6 (AEDFHR), więc tablica ma rozmiar 7 x 7.
   Wiersze odpowiadają kolejnym prefiksom ciągu A, kolumny - prefiksom ciągu B. Wartość dp[i][j] będzie oznaczać długość LCS dla pierwszych i znaków A oraz pierwszych j znaków B.

2. Inicjalizacja
   Gdy któryś z prefiksów ma długość 0 (czyli porównujemy z pustym ciągiem), długość LCS wynosi 0.
   Dlatego pierwszy wiersz i pierwszą kolumnę wypełniamy zerami.

3. Wypełnianie tabeli regułą przejścia
   Dla każdej pary indeksów (i,j) (od 1 do n i od 1 do m):

   • Jeśli znaki są równe, tzn. A[i‑1] = B[j‑1], to: dp[i][j] = dp[i‑1][j‑1] + 1 Dodajemy 1 do wyniku dla krótszych prefiksów, bo znaleźliśmy wspólny znak, który może wydłużyć podciąg.

   • Jeśli znaki są różne, to:
     dp[i][j] = max(dp[i‑1][j],dp[i][j‑1])
     LCS dla tych prefiksów jest tak długi, jak najlepszy LCS po „pominięciu” jednego znaku z jednego z ciągów.

4. Przykładowe kroki dla naszych ciągów
   Porównujemy kolejne litery:

   • Dla i=1 (A z pierwszego ciągu) i j=1 (A z drugiego): znaki są równe, więc
     dp[1][1] = dp[0][0] + 1 = 1.

   • Dla i=2 (B) i j=1 (A): znaki różne, więc
     dp[2][1] = max(dp[1][1],dp[2][0]) = max(1,0) = 1.

   • Dla i=3 (C) i j=3 (D): znaki różne, więc bierzemy maksimum z lewej lub z góry.

   • Dla i=4 (D) i j=3 (D): znaki równe, więc
     dp[4][3] = dp[3][2] + 1.

   Kontynuując w ten sposób, wypełniamy całą tabelę.

   • Dla i=1 (A z pierwszego ciągu) i j=1 (A z drugiego): znaki są równe, więc
     dp[1][1] = dp[0][0] + 1 = 1.

   • Dla i=2 (B) i j=1 (A): znaki różne, więc
     dp[2][1] = max(dp[1][1],dp[2][0]) = max(1,0) = 1.

   • Dla i=3 (C) i j=3 (D): znaki różne, więc bierzemy maksimum z lewej lub z góry.

   • Dla i=4 (D) i j=3 (D): znaki równe, więc
     dp[4][3] = dp[3][2] + 1.

5. Odczyt wyniku
   Po wypełnieniu tablicy, wartość w komórce dp[n][m] (czyli w prawym dolnym rogu) to długość najdłuższego wspólnego podciągu.
   W naszym przykładzie będzie to 3. Jednym z podciągów o tej długości jest ADH.

6. Odtwarzanie samego podciągu
   Mając tabelę, możemy „cofnąć się” od komórki dp[n][m] do dp[0][0], poruszając się w górę lub w lewo, a gdy trafimy na komórkę, w której znaki były równe, czyli powstała z dp[i‑1][j‑1] + 1, dopisujemy ten znak do wyniku. W ten sposób odzyskujemy konkretny LCS, a nie tylko jego długość.

W tym rozdziale przejdziemy przez ten proces dokładniej: narysujemy tabelę, przeanalizujemy kolejne kroki i pokażemy, jak z ogólnej idei programowania dynamicznego przejść do konkretnego, działającego algorytmu dla problemu najdłuższego wspólnego podciągu.

A ponieważ każdy ciąg porównany z pustym ma LCS równy 0, cała pierwsza kolumna to zera.

Możesz to zobaczyć tutaj:

Pierwsza kolumna = 0, bo oznacza:

LCS (A[1..i], "") = 0 dla każdego i.

Co to jest pusty prefiks?

Prefiks to po prostu „początek ciągu”. Np. prefiksy słowa ABCD to:

• "" (pusty)

• A

• AB

• ABC

• ABCD

Pusty prefiks to pierwszy z nich - ciąg o długości 0, czyli nic.

W tabeli LCS oznaczamy go jako:

• wiersz 0 -”pierwsze 0 znaków ciągu A”

• kolumna 0 -”pierwsze 0 znaków ciągu B”

Dlaczego potrzebujemy pustego prefiksu? Bo tabela dynamiczna zawsze zaczyna się od najprostszego przypadku. A najprostszy przypadek brzmi:

Jeśli porównujesz jakikolwiek ciąg z pustym ciągiem, to najdłuższy wspólny podciąg ma długość 0.

To dlatego:

• cała pierwsza kolumna to zera,

• cały pierwszy wiersz to zera.

Jak odtworzyć LCS z tabeli?

Zasady cofania

Startujemy z komórki dp[6][6] = 3 (ostatni wiersz, ostatnia kolumna).

1. Jeśli dp[i][j] == dp[i‑1][j], idziemy w górę - znak A nie należy do LCS.

2. Jeśli dp[i][j] == dp[i][j‑1], idziemy w lewo - znak B nie należy do LCS.

3. Jeśli A[i] == B[j], to znaleźliśmy literę LCS:

   • dopisujemy ją (na początek wyniku),

   • przechodzimy po skosie: do dp[i‑1][j‑1].

Przejście krok po kroku:

1. Start: dp[6][6]=3

Porównujemy H z R → różne.

dp[6][5] = 3, dp[5][6] = 2 → idziemy w lewo.

2. dp[6][5]=3

A[6] = H, B[5] = H → znaki równe!

Dodajemy H do wyniku. Przechodzimy do dp[5][4].

3. dp[5][4] = 2

G vs F → różne.

dp[5][3] = 2, dp[4][4] = 2 → możemy iść w lewo lub w górę.

Wybieramy np. w górę.

4. dp[4][4] = 2

D vs F → różne.

dp[4][3] = 2, dp[3][4] = 1 → idziemy w lewo.

5. dp[4][3] = 2

A[4] = D, B[3] = D → znaki równe!

Dodajemy D do wyniku. Przechodzimy do dp[3][2].

6. dp[3][2] = 1

C vs E → różne.

dp[3][1] = 1, dp[2][2] = 1 → idziemy np. w górę.

7. dp[2][2] = 1

B vs E → różne.

dp[2][1] = 1, dp[1][2] = 1 → idziemy w górę.

8. dp[1][2] = 1

A[1] = A, B[1] = A → znaki równe!

Dodajemy A do wyniku. Przechodzimy do dp[0][1].

Koniec - dotarliśmy do pierwszego wiersza.

Wynik

Zebrane litery (od końca): H, D, A → po odwróceniu:

LCS = ADH

Jak czytać tę ścieżkę

Zaczynamy od prawego dolnego rogu:

• dp[6][6] = 3 → strzałka ← (idziemy w lewo)

• dp[6][5] = 3 → strzałka ↖ → litera H

• dp[5][4] = 2 → strzałka ↑

• dp[4][4] = 2 → strzałka ←

• dp[4][3] = 2 → strzałka ↖ → litera D

• dp[3][2] = 1 → strzałka ↑

• dp[2][2] = 1 → strzałka ↑

• dp[1][2] = 1 → strzałka ↖ → litera A

Zebrane litery (od końca): H,D,A → po odwróceniu: LCS = ADH

Legenda:

• ↖ znak należy do LCS

• ↑ ruch w górę

• ← ruch w lewo

        j →      0    A    E    D    F    H    R
               +----+----+----+----+----+----+----+
i=0      ""    | 0  | 0  | 0  | 0  | 0  | 0  | 0  |
               +----+----+----+----+----+----+----+
i=1      A     | 0  | 1↖ | 1← | 1← | 1← | 1← | 1← |
               +----+----+----+----+----+----+----+
i=2      B     | 0  | 1↑ | 1↑ | 1↑ | 1↑ | 1↑ | 1↑ |
               +----+----+----+----+----+----+----+
i=3      C     | 0  | 1↑ | 1↑ | 1↑ | 1↑ | 1↑ | 1↑ |
               +----+----+----+----+----+----+----+
i=4      D     | 0  | 1↑ | 1↑ | 2↖ | 2← | 2← | 2← |
               +----+----+----+----+----+----+----+
i=5      G     | 0  | 1↑ | 1↑ | 2↑ | 2↑ | 2↑ | 2↑ |
               +----+----+----+----+----+----+----+
i=6      H     | 0  | 1↑ | 1↑ | 2↑ | 2↑ | 3↖ | 3← |
               +----+----+----+----+----+----+----+

Legenda:

• ↖ znak należy do LCS

• ↑ ruch w górę

• ← ruch w lewo

Odczytany podciąg

Idąc po strzałkach ↖, trafiamy kolejno na litery: 

• H

• D

• A

Po odwróceniu: LCS = ADH