Choose your language!

---

|

DP: Najduži zajednički podniz (LCS)

U ovoj lekciji upoznaćemo se sa problemom Najdužeg zajedničkog podniza (Longest Common Subsequence – LCS), koji je klasičan problem iz oblasti dinamičkog programiranja. Naučićemo kako da definišemo stanje, postavimo DP tabelu i analiziramo rešenje.

Tekst zadatka — Najduži zajednički podniz (LCS)

Datа su dva stringa X i Y. Potrebno je odrediti dužinu najdužeg zajedničkog podniza (Longest Common Subsequence — LCS) između ova dva stringa.

Podniz ne mora biti kontinualan — karakteri se mogu birati sa proizvoljnih pozicija, ali se njihov relativni redosled mora sačuvati.

Ulaz

• Prvi red sadrži string X
• Drugi red sadrži string Y

Izlaz

• Ispisati jedan ceo broj — dužinu najdužeg zajedničkog podniza

Primer

Ulaz:
AGGTAB
GXTXAYB

Izlaz:
4

Objašnjenje:
Jedan od najdužih zajedničkih podnizova je "GTAB".

Napomena

• Ako ne postoji nijedan zajednički karakter, rezultat je 0.
• Zadatak zahteva samo dužinu LCS-a, ne i sam podniz.

Vizualna interpretacija DP tabele (LCS)

Jedan od najčešćih problema kod razumevanja LCS algoritma jeste kako se popunjava DP tabela i zašto se u nekim slučajevima uzima maksimum iz susednih polja.

Posmatrajmo primer:

X = "AGGTAB"
Y = "GXTXAYB"

Kreiramo DP tabelu dimenzija (|X|+1) × (|Y|+1), gde dp[i][j] predstavlja dužinu LCS-a prefiksa X[0..i-1] i Y[0..j-1].

Početna DP tabela

      Ø  G  X  T  X  A  Y  B
   Ø  0  0  0  0  0  0  0  0
   A  0
   G  0
   G  0
   T  0
   A  0
   B  0
  

Prvi red i prva kolona su nule, jer LCS sa praznim stringom uvek ima dužinu 0.

Kako se popunjava jedno polje?

Posmatrajmo polje dp[i][j]:

• Ako su karakteri jednaki:
  X[i-1] == Y[j-1]
  tada:

  dp[i][j] = dp[i-1][j-1] + 1

  ➜ Krećemo se dijagonalno, jer smo produžili zajednički podniz.

• Ako karakteri nisu jednaki:

  dp[i][j] = max(dp[i-1][j], dp[i][j-1])

  ➜ Biramo bolju od dve opcije:

  • preskočiti karakter iz stringa X (gore)
  • preskočiti karakter iz stringa Y (levo)

Primer popunjene DP tabele

      Ø  G  X  T  X  A  Y  B
   Ø  0  0  0  0  0  0  0  0
   A  0  0  0  0  0  1  1  1
   G  0  1  1  1  1  1  1  1
   G  0  1  1  1  1  1  1  1
   T  0  1  1  2  2  2  2  2
   A  0  1  1  2  2  3  3  3
   B  0  1  1  2  2  3  3  4
  

Vrednost u donjem desnom uglu dp[|X|][|Y|] predstavlja dužinu najdužeg zajedničkog podniza. U ovom primeru to je 4.

Zašto gledamo maksimum iz levo i gore?

Kada se karakteri ne poklapaju, trenutni karakter ne može biti deo zajedničkog podniza. Zato ispitujemo dve mogućnosti:

• ignorisati karakter iz prvog stringa (gore)
• ignorisati karakter iz drugog stringa (levo)

Biramo onu opciju koja daje duži zajednički podniz, jer je cilj maksimizacija dužine LCS-a.

Opis problema

Dat su dva niza ili stringa X[1..n] i Y[1..m]. Cilj je pronaći najduži podniz koji se pojavljuje u oba niza. Podniz ne mora biti kontinualan.

Primer:

X = "AGGTAB"
Y = "GXTXAYB"
Najduži zajednički podniz: "GTAB", dužina = 4
  

Definicija stanja DP

Neka dp[i][j] predstavlja dužinu LCS-a prvih i karaktera niza X i prvih j karaktera niza Y.

Prelazi:

• Ako su poslednji karakteri jednaki: dp[i][j] = dp[i-1][j-1] + 1
• Ako nisu jednaki: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Osnovni slučajevi:

• dp[0][j] = 0 za sve j
• dp[i][0] = 0 za sve i

Detaljno objašnjenje problema Najdužeg zajedničkog podniza (LCS)

Problem najdužeg zajedničkog podniza (LCS – Longest Common Subsequence) jedan je od najvažnijih i najčešćih primera korišćenja dinamičkog programiranja. Datа su dva niza (često stringovi), a cilj je pronaći najduži podniz koji se pojavljuje u oba niza zadržavajući isti redosled elemenata, ali bez obaveze da budu uzastopni.

Šta je zapravo LCS?

Ako su zadati nizovi X = „ABCBDAB“ i Y = „BDCABA“, jedan od najdužih zajedničkih podnizova jeste BCBA, dužine 4. Važno je da elementi LCS-a moraju biti u istom redosledu u oba niza, ali između njih mogu da postoje preskočeni karakteri.

Zašto naivno rešenje nije efikasno?

Naivan pristup bi pokušao da generiše sve podnizove niza X (njih ima 2ⁿ), proveri koji se nalaze u Y i pronađe najduži. Međutim, broj podnizova raste eksponencijalno — za string od 30 karaktera postoji milijardu podnizova. U praksi je to neizvodljivo, pa je potrebna efikasnija metoda.

Zašto koristimo dinamičko programiranje?

Ključna ideja je da se problem LCS-a može podeliti na manje podprobleme. Dužina LCS-a za prefikse X[1…i] i Y[1…j] zavisi samo od LCS-a njihovih manjih prefiksa. Upravo zato kreiramo DP matricu gde svaki element predstavlja rezultat jednog podproblema koji se kasnije koristi za gradnju konačnog rešenja.

Definicija DP stanja

Neka dp[i][j] predstavlja dužinu LCS-a prvih i karaktera niza X i prvih j karaktera niza Y. Matrica dp se popunjava od najmanjih ka većim prefiksima.

Osnovni slučajevi

dp[0][j] = 0  (prazan niz nema zajednički podniz)
dp[i][0] = 0
    

Logika popunjavanja DP matrice

1) Ako se poslednji karakteri poklapaju

Ako važi X[i] == Y[j], onda taj karakter mora biti deo LCS-a. Zato je prelaz:

dp[i][j] = dp[i-1][j-1] + 1
    

2) Ako se poslednji karakteri ne poklapaju

Ako se X[i] ≠ Y[j], onda taj karakter ne može biti deo LCS-a. Zbog toga biramo bolji od dva moguća izbora:

dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    

Ovo znači: ili izbacujemo poslednji karakter X-a, ili poslednji karakter Y-a, i uzimamo najbolje rešenje od ta dva podproblema.

Kako izgleda DP matrica u praksi?

Za stringove dužina m i n, kreira se tabela dimenzija (m+1) × (n+1). Prvi red i prva kolona su nule. Svako polje se popunjava koristeći gore navedena pravila. Na kraju je dp[m][n] dužina najdužeg zajedničkog podniza.

Zašto je ovo efikasno?

DP pristup radi u vremenu O(m × n), što je ogromno ubrzanje u poređenju sa eksponencijalnim pristupom. Na primer, za dva stringa od 1000 karaktera DP izvršava oko milion operacija – to je trenutno u računarskom vremenu.

Sažetak DP rešenja

Stanje:        dp[i][j] = LCS(X[1..i], Y[1..j])
Baza:          dp[0][*] = dp[*][0] = 0
Poklapanje:    dp[i][j] = dp[i-1][j-1] + 1
Nepoklapanje:  dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    

Ovo je najpoznatiji klasični primer dinamičkog programiranja i priprema učenike za mnoge druge napredne algoritme koji koriste istu logiku podele problema na manje podprobleme sa preklapanjem.

Primer popunjavanja DP matrice za LCS

Uzećemo konkretan primer: X = "ABCBDAB", Y = "BDCABA". Matrica ispod prikazuje kako se korak po korak popunjava DP tabela. Redovi odgovaraju karakterima niza X, a kolone karakterima niza Y.

		B	D	C	A	B	A
	0	0	0	0	0	0	0
A	0	0	0	0	1	1	1
B	0	1	1	1	1	2	2
C	0	1	1	2	2	2	2
B	0	1	1	2	2	3	3
D	0	1	2	2	2	3	3
A	0	1	2	2	3	3	4
B	0	1	2	2	3	4	4

Konačan rezultat se nalazi u donjem desnom uglu matrice: dp[7][6] = 4, što znači da je dužina LCS-a jednaka 4.

Pseudokod za LCS algoritam

function LCS(X, Y):

    # Uzimamo dužine oba stringa
    m = dužina(X)
    n = dužina(Y)

    # Kreiramo DP matricu u kojoj će dp[i][j] da predstavlja
    # dužinu LCS-a za prve i karaktera X i prve j karaktera Y.
    # Matrica ima (m+1) redova i (n+1) kolona zbog slučajeva kada je
    # jedan od stringova "prazan".
    kreiraj matricu dp dimenzija (m+1) × (n+1)

    # Inicijalizacija baze DP-a:
    # Ako je jedan od stringova dužine 0, LCS je uvek 0.
    for i = 0..m:
        dp[i][0] = 0
    for j = 0..n:
        dp[0][j] = 0

    # Popunjavanje DP matrice red po red, kolonu po kolonu
    for i = 1..m:
        for j = 1..n:

            # Ako su trenutno posmatrani karakteri jednaki,
            # oni čine deo LCS-a. Zato dodajemo 1 rešenju
            # prethodnih prefiksa (i-1, j-1).
            if X[i] == Y[j]:
                dp[i][j] = dp[i-1][j-1] + 1

            # Ako se karakteri ne poklapaju, onda se najbolji LCS
            # dobija tako što izbacimo ili:
            #  - poslednji karakter iz X  (dp[i-1][j])
            #  - poslednji karakter iz Y  (dp[i][j-1])
            # Uzimamo maksimum ove dve opcije.
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    # Krajnji rezultat — dužina LCS-a — nalazi se
    # u donjem desnom ćošku matrice.
    return dp[m][n]

    

Python implementacija

def lcs(X, Y):
    m = len(X)
    n = len(Y)

    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]

    

C++ implementacija

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int lcs(string X, string Y) {
    int m = X.size();
    int n = Y.size();

    vector> dp(m + 1, vector(n + 1, 0));

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {

            if (X[i - 1] == Y[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;

            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    return dp[m][n];
}

    

Tabulacija i analiza rešenja

Popunjavanje DP tabele se vrši redom (bottom-up). Na kraju, dp[n][m] sadrži dužinu najdužeg zajedničkog podniza.

// DP: Najduži zajednički podniz (LCS)
#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
    // Dati stringovi
    string X = "AGGTAB";
    string Y = "GXTXAYB";

    // n i m su njihove dužine
    int n = X.size();
    int m = Y.size();

    // DP tabela dimenzija (n+1) × (m+1)
    // dp[i][j] predstavlja dužinu LCS-a između
    // prvih i karaktera stringa X i prvih j karaktera stringa Y.
    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));

    // Popunjavanje DP matrice — bottom-up pristup.
    // Krećemo od (1,1) jer je prvi red i prva kolona već 0
    // (bazični slučaj: poređenje sa praznim stringom → LCS = 0).
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {

            // Ako su karakteri isti — deo su LCS-a
            // pa dodajemo 1 rezultatu prethodnih prefiksa.
            if(X[i-1] == Y[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;

            // Ako nisu isti — uzimamo najbolji rezultat
            // između:
            // 1) izbacivanja poslednjeg karaktera iz X → dp[i-1][j]
            // 2) izbacivanja poslednjeg karaktera iz Y → dp[i][j-1]
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }

    // LCS dužina se nalazi u donjem desnom uglu DP tabele
    cout << "Duzina LCS-a: " << dp[n][m] << endl;

    // ----------------------------------------------
    //  Opcionalno: Rekonstrukcija stvarnog LCS-a.
    //  Krecemo od dp[n][m] i "vracamo se unazad" kroz DP tabelu.
    // ----------------------------------------------

    string lcs = "";
    int i = n, j = m;

    // Dok se nismo vratili do nultog reda ili kolone
    while(i > 0 && j > 0) {

        // Ako su karakteri jednaki — oni su deo LCS-a.
        // Dodajemo ih na početak rezultata.
        if(X[i-1] == Y[j-1]) {
            lcs = X[i-1] + lcs;
            i--;
            j--;
        }

        // Ako nisu jednaki, pomeramo se u onom smeru
        // gde je LCS duži (ka većoj vrednosti u DP tabeli).
        else if(dp[i-1][j] > dp[i][j-1]) {
            i--;
        } else {
            j--;
        }
    }

    // Ispis konačnog rekonstruisanog LCS niza
    cout << "LCS: " << lcs << endl;

    return 0;
}
  

Analiza:
– Vreme izvršavanja: O(n*m)
– Memorija: O(n*m) (može da se optimizuje na O(min(n,m)) korišćenjem samo dva reda)
– Primer prikazuje i rekonstrukciju samog podniza.

Skriveni mini kviz — Najduži zajednički podniz- LCS (Longest Common Subsequence)

Proveri da li razumeš osnovne ideje i DP rešenje za LCS problem.

Otvori kviz

Mini kviz: Najduži zajednički podniz (LCS)

1. Šta predstavlja dp[i][j] u LCS problemu?

Dužinu LCS-a prefiksa X[0..i-1] i Y[0..j-1]
Broj zajedničkih karaktera u stringovima
Najduži zajednički substring
Prikaži odgovor

2. Šta radimo kada su X[i-1] i Y[j-1] jednaki?

dp[i][j] = dp[i-1][j-1] + 1
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
dp[i][j] = 1
Prikaži odgovor

3. Zašto koristimo max(levo, gore) kada se karakteri ne poklapaju?

Biramo bolje rešenje iz izbacivanja jednog od karaktera
Zato što je to brže od dijagonale
Zato što DP tabela mora biti monotona
Prikaži odgovor

4. Kolika je vremenska složenost standardnog DP rešenja za LCS?

O(n + m)
O(n · m)
O(2ⁿ)
Prikaži odgovor

5. Kako se vrši rekonstrukcija samog LCS-a?

Kretanjem unazad od dp[n][m] kroz tabelu
Ponovnim pokretanjem DP algoritma
Sortiranjem karaktera
Prikaži odgovor

□ Resetuj kviz

Zadatak — Rekonstrukcija najdužeg zajedničkog podniza (LCS)

Data su dva stringa X i Y. Nakon popunjavanja DP tabele za Longest Common Subsequence (LCS), potrebno je rekonstruisati sam najduži zajednički podniz, a ne samo njegovu dužinu.

Ako postoji više rešenja, dozvoljeno je ispisati bilo koje.

Ulaz

• Prvi red: string X
• Drugi red: string Y

Izlaz

• Jedan string — najduži zajednički podniz

Primer

Ulaz:
AGGTAB
GXTXAYB

Izlaz:
GTAB

Prikaži uputstvo

Uputstvo — rekonstrukcija LCS-a

Rekonstrukcija LCS-a se vrši kretanjem unazad kroz DP tabelu, počevši od polja dp[n][m].

1. Ako je X[i-1] == Y[j-1]:
   • karakter pripada LCS-u
   • dodaje se u rezultat
   • pomeramo se dijagonalno: i--, j--
2. Ako karakteri nisu jednaki:
   • ako je dp[i-1][j] > dp[i][j-1] → idemo gore
   • inače → idemo levo
3. Pošto se ide unazad, dobijeni string je obrnut i na kraju se mora okrenuti.

// Pseudokod
while (i > 0 && j > 0):
  if X[i-1] == Y[j-1]:
    dodaj X[i-1] u LCS
    i--, j--
  else if dp[i-1][j] > dp[i][j-1]:
    i--
  else:
    j--
    

Prikaži rešenje

Rešenje — Rekonstrukcija LCS-a (C++)

// Rekonstrukcija Longest Common Subsequence (LCS)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    string X, Y;
    cin >> X >> Y;

    int n = X.size(), m = Y.size();

    vector> dp(n + 1, vector(m + 1, 0));

    // Popunjavanje DP tabele
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(X[i-1] == Y[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }

    // Rekonstrukcija LCS-a
    string lcs = "";
    int i = n, j = m;

    while(i > 0 && j > 0) {
        if(X[i-1] == Y[j-1]) {
            lcs.push_back(X[i-1]);
            i--; j--;
        } else if(dp[i-1][j] > dp[i][j-1]) {
            i--;
        } else {
            j--;
        }
    }

    reverse(lcs.begin(), lcs.end());
    cout << lcs << endl;
    return 0;
}
    

Složenost

• Vreme: O(n · m)
• Memorija: O(n · m)

Težak zadatak za vežbu — nivo SIO / Državno takmičenje

Sledeći zadatak je namenjen za naprednu praksu i zahteva primenu LCS koncepta na veće ulazne nizove.

Zadatak: Najduži zajednički podniz više nizova

Dat je skup od k stringova: S1, S2, ..., Sk. Cilj je pronaći dužinu najdužeg zajedničkog podniza koji se pojavljuje u svim stringovima.

Primer:

k = 3
S1 = "AGGTAB"
S2 = "GXTXAYB"
S3 = "GTTAB"
Najduži zajednički podniz svih stringova: "GTAB", dužina = 4
  

Uputstvo za rešavanje

• Razmisli kako se standardni LCS između dva stringa može proširiti na više nizova.
• Definiši DP stanje, npr. dp[i1][i2][...][ik] ili alternativno koristi iterativnu redukciju na parove stringova.
• Identifikuj bazne slučajeve: prazan string daje dužinu 0.
• Koristi bottom-up tabulaciju ili memoizaciju (top-down) da popuniš tabelu i izračunaš dužinu LCS.
• Analiziraj memorijske i vremenske složenosti — za veće ulaze može biti potrebna optimizacija ili redukcija dimenzija.

Napomena: Ovaj zadatak je odlična vežba za pripremu za SIO i državna takmičenja. Pokušaj prvo da osmisliš DP pristup i prelaze, a zatim implementiraj kod. Ne gledaj rešenje unapred.

Savet: Ako se želiš dodatno pripremiti, prvo reši standardni LCS za dva stringa sa rekonstrukcijom podniza, pa zatim proširi na više stringova.

Zadatak — Najduži zajednički podniz (3 stringa)

Data su tri stringa A, B i C. Potrebno je pronaći najduži zajednički podniz koji se pojavljuje u sva tri stringa.

Primer

Ulaz:
AGGTAB
GXTXAYB
GTTAB

Izlaz:
GTAB

Prikaži uputstvo

Uputstvo

• Problem je proširenje standardnog LCS-a sa 2 na 3 stringa.
• Koristi se 3D DP tabela: dp[i][j][k].
• dp[i][j][k] predstavlja dužinu LCS-a prefiksa: A[0..i-1], B[0..j-1], C[0..k-1].
• Ako su karakteri jednaki: dp[i][j][k] = dp[i-1][j-1][k-1] + 1
• Inače: dp[i][j][k] = max( dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1] )
• Vreme: O(n · m · p), Memorija: O(n · m · p)

Prikaži rešenje

Rešenje — LCS za tri stringa (3D DP)

// LCS za tri stringa
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    string A, B, C;
    cin >> A >> B >> C;

    int n = A.size(), m = B.size(), p = C.size();

    vector<vector<vector<int>>> dp(
        n + 1,
        vector<vector<int>>(m + 1, vector<int>(p + 1, 0))
    );

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            for(int k = 1; k <= p; k++)
                if(A[i-1] == B[j-1] && A[i-1] == C[k-1])
                    dp[i][j][k] = dp[i-1][j-1][k-1] + 1;
                else
                    dp[i][j][k] = max({
                        dp[i-1][j][k],
                        dp[i][j-1][k],
                        dp[i][j][k-1]
                    });

    cout << dp[n][m][p] << endl;
    return 0;
}
    

Složenost

• Vreme: O(n · m · p)
• Memorija: O(n · m · p)

Još jedan napredni zadatak za vežbu — nivo SIO / Državno takmičenje

Ovaj zadatak kombinuje LCS sa dodatnom operacijom — brojanje različitih LCS podnizova.

Zadatak: Brojanje različitih LCS podnizova

Dat su dva stringa X i Y. Tvoj zadatak je da izračunaš koliko različitih podnizova maksimalne dužine LCS postoji.

Primer:

X = "ABCBDAB"
Y = "BDCABA"
Maksimalna dužina LCS = 4
Broj različitih LCS podnizova = 3
  

Uputstvo za rešavanje

• Prvo reši standardni LCS da izračunaš dužinu najdužeg zajedničkog podniza.
• Definiši DP stanje koje čuva ne samo dužinu LCS do indeksa i,j, već i broj različitih podnizova iste dužine.
• Koristi bottom-up ili top-down pristup sa memoizacijom da popuniš tabelu.
• Prati bazne slučajeve: prazan string daje dužinu 0 i broj podnizova 1.
• Pazi na duplikate: ako dva puta dođeš do istog LCS-a, broji ga samo jednom.
• Na kraju, dp[n][m] sadrži broj različitih LCS podnizova maksimalne dužine.

Napomena: Ovaj zadatak je odlična vežba za naprednu primenu DP i zahteva dobru analizu prelaza i optimizaciju memorije.

Savet: Pokušaj prvo da rešiš problem za male stringove i proveri rezultate ručno, pre nego što implementiraš za veće ulaze.

Zadatak (napredni): Brojanje različitih LCS podnizova

Data su dva stringa X i Y. Potrebno je izračunati:

• maksimalnu dužinu najdužeg zajedničkog podniza (LCS)
• koliko različitih LCS podnizova te maksimalne dužine postoji

Primer

• X = ABCBDAB
• Y = BDCABA

Maksimalna dužina LCS = 4
Broj različitih LCS podnizova = 3

Prikaži uputstvo

Uputstvo za rešavanje

1. Prvo se računa dužina LCS-a klasičnim DP-om sa tabelom len[i][j].
2. Zatim se uvodi dodatna DP tabela cnt[i][j] koja predstavlja broj različitih LCS podnizova maksimalne dužine za prefikse X[0..i-1] i Y[0..j-1].
3. Bazni slučaj:
   • ako je i = 0 ili j = 0
   • LCS dužina je 0
   • postoji tačno jedan podniz — prazan niz
4. Kada se karakteri ne poklapaju, može doći do dupliranja istih LCS-ova iz pravca „gore“ i „levo“. Zato se koristi inclusion–exclusion (oduzimanje cnt[i-1][j-1]).
5. Krajnji odgovor je cnt[n][m], ali se broje samo podnizovi čija je dužina jednaka len[n][m].

Savet: Probaj najpre na kratkim stringovima i ručno ispiši sve LCS-ove da proveriš da li se isti podniz ne broji više puta.

Prikaži rešenje

Rešenje — Brojanje različitih LCS podnizova (C++)

// Brojanje različitih LCS podnizova
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    string X = "ABCBDAB";
    string Y = "BDCABA";

    int n = X.size();
    int m = Y.size();

    vector<vector<int>> len(n + 1, vector<int>(m + 1, 0));
    vector<vector<long long>> cnt(n + 1, vector<long long>(m + 1, 0));

    // Bazni slučajevi
    for(int i = 0; i <= n; i++) cnt[i][0] = 1;
    for(int j = 0; j <= m; j++) cnt[0][j] = 1;

    // DP popunjavanje
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {

            if(X[i-1] == Y[j-1]) {
                len[i][j] = len[i-1][j-1] + 1;
                cnt[i][j] = cnt[i-1][j-1];
            } else {
                len[i][j] = max(len[i-1][j], len[i][j-1]);

                long long ways = 0;
                if(len[i-1][j] == len[i][j])
                    ways += cnt[i-1][j];
                if(len[i][j-1] == len[i][j])
                    ways += cnt[i][j-1];

                if(len[i-1][j] == len[i][j] &&
                   len[i][j-1] == len[i][j] &&
                   len[i-1][j-1] == len[i][j]) {
                    ways -= cnt[i-1][j-1];
                }

                cnt[i][j] = max(0LL, ways);
            }
        }
    }

    cout << "Maksimalna duzina LCS: " << len[n][m] << endl;
    cout << "Broj razlicitih LCS podnizova: " << cnt[n][m] << endl;

    return 0;
}
    

Zašto ovaj pristup radi?

• len[i][j] osigurava da brojimo samo optimalne podnizove
• cnt[i][j] broji različite LCS-ove bez duplikata
• inclusion–exclusion uklanja ponovljene puteve u DP tabeli
• obrazac važi za mnoge probleme „brojanja optimalnih rešenja“

Detaljno objašnjenje logike rešenja

Dinamička tabela len određuje koliko je dugačak optimalni LCS, dok tabela cnt računa koliko različitih LCS-ova te dužine postoji.

Svaka ćelija (i, j) predstavlja problem za prefikse X[0..i-1] i Y[0..j-1]. LCS se može formirati:

• dijagonalno (↖) – ako se karakteri poklapaju
• odozgo (↑) – ako zanemarimo karakter iz X
• sleva (←) – ako zanemarimo karakter iz Y

Kada se optimalna dužina može dobiti i odozgo i sleva, iste LCS sekvence se pojavljuju u oba pravca. Zato se primenjuje princip uključenja–isključenja i oduzima se cnt[i-1][j-1].

Na taj način se osigurava da se svaki različit LCS string broji tačno jednom, bez obzira na broj putanja kroz DP tabelu.

Za dati primer postoje tačno tri različita LCS-a dužine 4:

BCBA
BDAB
BCAB
      

Konkretno grananje u ovom primeru

U ovom zadatku ne postoji samo jedan LCS, već više različitih podnizova iste maksimalne dužine. Na osnovu DP tabele vidi se da postoje tri različite putanje koje daju LCS dužine 4.

Vizuelno (po slovima):

• LCS #1
  B  C  B  A
• LCS #2
  B  D  A  B
• LCS #3
  B  C  A  B

□ Sva tri podniza:

• imaju maksimalnu dužinu 4
• pojavljuju se kao podnizovi u X i u Y
• različiti su kao stringovi

---

Zašto ih nema više?

Iako u DP tabeli postoji veliki broj različitih putanja od ćelije (n, m) do (0, 0), različite putanje mogu proizvesti isti LCS string.

Na primer, sledeće dve putanje:

↖ ↑ ← ↖     i     ↖ ← ↑ ↖
  

mogu voditi do istog niza karaktera. Iako su putanje različite, rezultat (LCS string) je isti, pa se mora brojati samo jednom.

---

Kako se to rešava algoritamski (intuicija)

Pored standardne DP tabele za dužinu:

dpLen[i][j] = dužina LCS-a za X[0..i-1] i Y[0..j-1]
  

uvodi se i druga tabela:

dpCount[i][j] = broj različitih LCS podnizova
               maksimalne dužine
  

Osnovna pravila:

1. Ako su karakteri jednaki:

   
   count[i][j] = count[i-1][j-1]
         

   Svaki optimalni LCS se produžava za taj zajednički karakter.

2. Ako karakteri nisu jednaki:
   • Ako je dpLen[i-1][j] > dpLen[i][j-1]:

     
     count[i][j] = count[i-1][j]
               

   • Ako je dpLen[i][j-1] > dpLen[i-1][j]:

     
     count[i][j] = count[i][j-1]
               

   • Ako su dužine jednake:

     
     count[i][j] = count[i-1][j] + count[i][j-1]
                   - count[i-1][j-1]
               

     Oduzimanjem count[i-1][j-1] uklanjaju se duplikati koji dolaze iz oba pravca.

□ Oduzimanje je ključno – bez njega bi se isti LCS podniz prebrojavao više puta.

---

Konačan rezultat za dati primer

X = ABCBDAB
Y = BDCABA

Maksimalna dužina LCS = 4
Broj različitih LCS = 3
  

4. Povezane stranice

• Uvod u DP — osnovna ideja
• DP: Fibonacci sa memoizacijom
• DP: Problem ranca (Knapsack problem)
• DP: Subset Sum (uskoro)

Sledeća lekcija može biti Subset Sum problem ili dodatni primeri LCS-a za vežbu i takmičenja.

---

Prethodno
​|< DP: Problem ranca (Knapsack problem)

Sledeće
DP: Subset Sum problem >|

---