Articole recomandate

De exemplu, pentru n=10 și șirul A=(5, 10, 7, 4, 5, 8, 9, 8, 10, 2), cel mai lung subșir crescător va conține 5 elemente (5, 7, 8, 9, 10) sau (4, 5, 8, 9, 10).

Problema este una clasică și se rezolvă prin programare dinamică. Subșirul cerut se mai numește și subșir crescător maximal.

O soluție \(O(n^2)\)

Determinarea lungimii maxime

Pentru a determina lungimea maximă a unui subșir crescător al lui A, vom construi un șir suplimentar LG[], cu proprietatea că LG[i] este lungimea maximă a unui subșir care se începe în A[i]. Atunci lungimea maximă a unui subșir crescător va fi cel mai mare element din tabloul LG.

Vom construi șirul LG progresiv, începând de la ultimul element din A, bazându-ne pe următoarele observații:

• LG[i] ≥ 1, ∀i
• LG[n] = 1
• vom determina LG[i] astfel: analizăm toate elementele A[j], cu j>i și îl alegem pe acela pentru care LG[j] este maxim și A[i]≤A[j]. Fie jmax indicele acestui element. Atunci LG[i] devine LG[i] = LG[jmax] + 1 – elementul A[i] se lipește de subșirul care începe în A[jmax].

Secvență C++:

LG[n] = 1;
for(int i = n - 1 ; i > 0 ; i --)
{
    LG[i] = 1;
    for(int j = i + 1 ; j <= n; ++ j)
        if(A[i] <= A[j] && LG[i] < LG[j] + 1)
            LG[i] = LG[j] + 1;
}

După construirea șirului LG, lungimea subșirului maximal se determină ca fiind cea mai mare valoare din tabloul LG.

int pmax = 1;
for(int i = 2 ; i <= n ; i ++)
    if(LG[i] > LG[pmax])
        pmax = p;
cout << LG[pmax];

Reconstituirea subșirului

Există mai multe modalități de reconstituire a subșirului maximal. De asemenea, trebuie spus că pot exista mai multe șiruri maximale; în unele probleme poate fi determinat oricare, în altele trebuie determinat un subșir cu proprietăți suplimentare.

O soluție constă în construirea unui șir suplimentar, Next cu următoarea semnificație: Next[i] este următorul element în subșirul crescător maximal care începe cu A[i]. Dacă nu există un element următor, atunci LG[i] = -1. Acest tabloul se construiește în același timp cu LG, astfel:

LG[n] = 1, Next[n] = -1;
for(int i = n - 1 ; i > 0 ; i --)
{
    LG[i] = 1 , Next[n] = -1;
    for(int j = i + 1 ; j <= n; ++ j)
        if(A[i] <= A[j] && LG[i] < LG[j] + 1)
            LG[i] = LG[j] + 1, Next[i] = j;
}

Pentru a afișa subșirul, vom extrage informațiile necesare din șirul Next, pornind de la indicele pmax determinat mai sus:

int p = pmax;
do
{
    cout << p << " ";
    p = Next[p];
}
while(p != -1);

Putem reconstitui subșirul fără a construi șirul Next. La fiecare pas al structurii repetitive de mai sus vom determina un indice pUrm cu proprietatea că LG[pUrm]==LG[p]-1 și A[p] ≤ A[pUrm]:

int p = pmax;
do
{
    cout << p << " ";
    int pUrm = p + 1;
    while(pUrm <= n && ! (A[pUrm] >= A[p] && LG[pUrm] == LG[p] - 1))
        pUrm ++;
    if(pUrm <= n)
        p = pUrm;
    else
        p = -1;
}
while(p != -1);

Altă soluție \(O(n^2)\)

Putem regândi algoritmul de mai sus, astfel încât LG[i] să reprezinte lungime a maximă a unui subșir maximal care se termină în A[i].

• evident, LG[1]=1;
• pentru fiecare element A[i] din șirul dat, vom parcurge elementele din fața sa și îl vom alege pe A[p] atfel încât A[p]≤A[i] și LG[p] este maxim. În acest caz, A[i] se adaugă la subșirul care se încheie în A[p], adică LG[i] devine LG[p]+1.

Lungimea subșriului maximal este cea mai mare valoare din LG, iar recosntituirea lui se face asemănător cu metoda de mai sus, folosind un șir de predecesori Prev[], unde Prev[i] este elementul din fața lui A[i] în subșirul crescător maximal care se încheie în A[i].

O soluție \(O(n \cdot \log n)\)

Algoritmul de mai sus are complexitate pătratică. Următoarea idee permite obținerea unui algoritm \(O(n \cdot \log{n})\).

Vom construi șirul D[], unde D[j] reprezintă un element al șirului A în care se termină un subșir crescător maximal de lungime j. Numărul de elemente pe care le va avea la final tabloul D va reprezenta lungimea subșirului crescător maximal al întregului șir A.

Vom construi șirul D în felul următor:

• fie k lungimea șirului D. Inițializăm k=1 și D[k]=A[1];
• parcurgem șirul A, începând de la al doilea element:
  • dacă A[i]≥D[k], îl adăugăm pe A[i] în șirul D – subșirul crescător maximal al lui A crește cu încă un element
  • dacă A[i]<D[k], vom înlocui cu A[i] pe cel mai mai mic element din D care este mai mare decât acesta

ATENȚIE: Șirul D[] nu conține un subșir crescător al șirului A[]!

Exemplu

Pentru A=(5, 10, 7, 4, 5, 8, 9, 8, 10, 2).

Inițial k=1; D[k]=5; parcurgem șirul A, începând de la al doilea element:

Observații

• valorile din șirul D sunt în ordine crescătoare
• fiecare element din șirul A modifică exact un element din șirul D (prin adăugare sau înlocuire).

Aceste observații ne permit să folosim căutarea binară pentru a stabili elementul din D care va fi înlocuit la fiecare pas: vom căuta primul element din D care este mai mare decât A[i]. Acest lucru poate fi realizat manual sau folosind funcția STL upper_bound. Complexitatea va fi \(O(n \cdot \log k)\).

Secvență C++

k = 1, D[k] = A[1];
for(int i = 2 ; i <= n ; i ++)
{
    if(A[i] >= D[k])
        P[++k] = A[i];
    else
    {
        int st = 1 , dr = k , poz = k + 1;
        while(st <= dr)
        {
            int m = (st + dr) / 2;
            if(D[m] > A[i])
                poz = m , dr = m - 1;
            else
                st = m + 1;
        }
        D[poz] = A[i];
    }
}
cout << k << endl;

Reconstituirea subșirului

Pentru a reconstitui sub șirul crescător maximal vom folosi încă un șir P[], unde P[i] reprezintă poziția în șirul D unde a fost plasat (prin adăugare sau prin înlocuire) A[i]. Acesta este construit, pas cu pas, odată cu șirul D[]. Dacă un element A[i] face parte din subșirul crescător maximal, atunci P[i] reprezintă poziția sa în subșir.

Pentru exemplul de mai sus, șirul P[] va fi la final (1,2,2,1,2,3,4,4,5,1).

Reconstituirea propriu-zisă a subșirului se face în felul următor:

• fie k – lungimea subșirului crescător maximal;
• căutăm în șirul P[] un element egal cu k. Fie Ik poziția sa. Atunci A[Ik] reprezintă ultimul element al subșirului crescător maximal – cel de pe poziția k;
• căutăm în șirul P[] un element egal cu k-1, anterior elementului de indice Ik. Fie Ik-1 poziția sa.
• analog se caută în P[] valorile k-2, k-3, ..., 2, 1.
• subșirul crescător maximal va fi (A[I1], A[I2], ..., A[Ik]).

Secvența C++

În secvența de mai jos șirul I[] construit va conține indicii elementelor din A[] care fac parte din subșirul comun maximal.

k = 1;
D[k] = A[1];
P[1] = 1;
for(int i = 2 ; i <= n ; i ++)
	if(A[i] >= D[k])
		D[++k] = A[i], P[i] = k;
	else
	{
		int st = 1 , dr = k , p = k + 1;
		while(st <= dr)
		{
			int m = (st + dr) / 2;
			if(D[m] > A[i])
				p = m, dr = m - 1;
			else
				st = m + 1;
		}
		D[p] = A[i];
		P[i] = p;
	}
int j = n;
for(int i = k ; i >= 1 ; i --)
{
	while(P[j] != i)
		j --;
	I[i] = j;
}

Probleme propuse

• #sclm
• #plopi1
• #radiera
• #sclmprime
• #joc6
• #sclm2
• #inserari

Introducere

Considerăm o matrice (labirint, teren, etc.) cu n linii și m coloane și un mobil aflat inițial în elementul de coordonate (1,1) – colțul stânga-sus, care se poate deplasa din elementul curent, de coordonate (i,j) în unul dintre elementele de coordonate (i+1,j) – aflat pe linia următoare, și (i,j+1) – aflat pe următoarea coloană. Să se determine în câte moduri poate ajunge mobilul în elementul de coordonate (n,m) – colțul dreapta-jos.

Problema are cel puțin două soluții, una care folosește metoda programării dinamice și una care se bazează pe combinatorică.

Rezolvare cu programare dinamică

Să constatăm mai întâi că numărul de drumuri căutat depinde de n și m – la mintea cocoșului, am putea spune. În general, numărul de drumuri de la poziția (1,1) la poziția (i,j) depinde de i și j, și numai de acestea. Atunci, formula recursivă care calculează rezultatul pentru (i,j) va depinde numai de i și de j!

Ne propunem să determinăm numărul de modalități în care mobilul ajunge de la poziția (1,1) în poziția (i,j). Fie acest număr \(F_{i,j}\). Constăm următoarele:

• în orice element de pe linia 1 se poate ajunge într-un singur mod, dinspre stânga, deoarece în poziția (1,j) se poate ajunge numai din poziția (1,j-1). Astfel, \(F_{1,j} = 1\).
• în orice element de pe coloana 1 se poate ajunge într-un singur mod, dinspre linia anterioară, deoarece în poziția (i,1) se poate ajunge numai din poziția (i-1,1). Astfel, \(F_{i,1} = 1\).
• în poziția (i,j) (cu i>1 și j>1) se poate ajunge în două moduri:
  • de sus, din poziția (i-1,j);
  • din stânga, din poziția (i,j-1);
• atunci numărul de posibilități de a ajunge în poziția (i,j) este numărul de posibilități de a ajunge în poziția (i-1,j) adunat cu numărul de posibilități de a ajunge în poziția (i,j-1). Astfel, \(F_{i,j} = F_{i-1,j} + F_{i,j-1}\).
• rezultatul este \(F_{n,m}\).

În concluzie:

\( F_{i,j} = \begin{cases}
1& \text{dacă } i = 1 \text{ sau } j = 1, \\
F_{i-1,j} + F_{i,j-1}& \text{ dacă } i > 1 \text{ și } j > 1
\end{cases} \)

Deoarece formulele se suprapun, implementarea recursivă este foarte lentă. În consecință vom folosi o structură de date suplimentară, mai precis un tablou bidimensional în care A[i][j] reprezintă numărul de modalități de a ajunge din poziția (1,1) în poziția (i,j).

Acest tablou poate fi construit în maniera bottom-up:

int n, m, A[NN][NN];
...
for(int i = 1 ; i <= n ; ++ i)
	A[i][1] = 1;
for(int j = 1 ; j <= m ; ++ j)
	A[1][j] = 1;
for(int i = 2 ; i <= n ; ++ i)
	for(int j = 2 ; j <= m ; ++ j)
		A[i][j] = (A[i-1][j] + A[i][j-1]) % 9901;
cout << A[n][m];

De asemenea, recurența poate fi rezolvată în maniera top-down, cu memoizare:

int n, m, A[NN][NN];

int F(int i , int j)
{
    if(A[i][j] != 0)
        return A[i][j];
    if(i == 1 || j == 1)
        A[i][j] = 1;
    else
        A[i][j] = (F(i-1,j) + F(i,j-1)) % 9901;
    return A[i][j];
}
...
cout << F(n,m);

Rezolvare folosind calcul combinatorial

Pentru această soluție, să observăm că oricare traseu din poziția (1,1) în poziția (n,m), are respectă regulile de deplasare, va face exact n-1 pași spre dreapta și exact m-1 pași în jos. Traseele diferă numai prin ordinea acestor pași, nu prin numărul lor!

Atunci numărul de trasee este egal cu numărul de combinații de n-1 pași spre stânga și m-1 pași spre în jos; altfel spus n+m-2 pași, dintre care n-1 sunt în jos, adică: \(C_{n+m-2}^{n-1}\).

Observații

• numărul de trasee crește foarte repede. Pentru valori relativ mici ale lui n și m se produce overflow. Pentru valori mai mari ale acestora este necesară implementarea operațiilor cu numere mari!
• de multe ori, pentru a rezolva problema cu valori mai mari ale lui n și m, fără însă a implementa operații cu numere mari, se cere determinarea restului împărțirii rezultatului la o valoare dată MOD, adică realizarea operațiilor modulo MOD!
• rezolvarea cu programare dinamică are complexitatea timp \(O(n \cdot m)\). Spațiul de memorie poate fi optimizat, folosind doar două tablouri unidimensionale, unul pentru linia curentă și celălalt pentru linia precedentă. Asta deoarece în calculul valorilor de pe linia curentă i se folosesc doar elemente de pe aceasta și de pe linia precedentă, i-1.
• complexitatea rezolvării cu combinări este cea a algoritmului de determinare a combinărilor. Acestea pot fi determinate fie folosind formula uzuală, fie folosind triunghiul lui Pascal.

Probleme propuse

• #Cladire
• #Cladire1
• #Alice_XI
• #PacMan_XI
• #Expozitie

Programarea dinamică este o metodă de rezolvare a unor probleme de informatică în care se cere de regulă determinarea unei valori maxime sau minime, sau numărarea elementelor unei mulțimi.

Similar cu metoda Divide et Impera, problema se împarte în subprobleme:

• de aceeași natură cu problema inițială;
• de dimensiuni mai mici;
• spre deosebire de Divide et Impera, problemele nu mai sunt independente, ci se suprapun – probleme superpozabile!
• rezolvarea optimă a problemei inițiale depinde de rezolvarea optimă a subproblemelor – principiul optimalității!

Observație: Subproblemele se mai numesc și stări ale problemei.

Problemă: Se dă o scară cu N trepte. Un individ se află în partea de jos a scării și poate să urce câte o treaptă la un pas, sau câte două trepte la un pas. În câte moduri poate urca scara?

Exemplu: Observăm că dacă scara are o treaptă, ea poate fi urcată într-un singur mod, iar dacă are două trepte, sunt două modalități de a urca scara: doi pași de o treaptă sau un un pas de două trepte. Pentru N=4, scara poate fi urcată în 5 moduri:

• 1 1 1 1
• 1 1 2
• 1 2 1
• 2 1 1
• 2 2

Rezolvare: Este o problemă de numărare; dacă numerotăm treptele, observăm că pe treapta N se poate ajunge de pe treapta N-1 (cu un pas de o treaptă) sau de pe treapta N-2 (cu un pas de două trepte), cazurile N=1 și N=2 fiind particulare. Atunci, numărul de variate de a urca N trepte este egal cu numărul de variante de a urca N-1 trepte, plus numărul de variante de a urca N-2 trepte. Deducem deci următoarea relație de recurență, în care \( T(n) \) reprezintă numărul de modalități de a urca o scară cu n trepte:

$$ T(n) = \begin{cases}1, & n = 1\\ 2, & n = 2\\ T(n-1)+T(n-2), & n > 2 \end{cases} $$

Constatăm că formula anterioară respectă proprietățile descrise mai sus pentru probleme rezolvabile prin programare dinamică: subprobleme de același tip, de dimensiuni mai mici și care se suprapun; în determinarea lui \(T(n)\) intervine \(T(n-1)\) și \(T(n-2)\). În determinarea lui \(T(n-1)\) apare din nou \(T(n-2)\), ș.a.m.d., situație care face ca utilizarea recursivității să fie foarte ineficientă.

De fapt, putem observa că formula de mai sus este de fapt definiția șirului lui Fibonacci, despre care am văzut deja că are o soluție de complexitate \(O(n) \), construind termenii în ordine crescătoare, folosind eventual un tablou unidimensional (sau doar trei variabile simple).

Determinarea relației de recurență este o caracteristică a programării dinamice, și una dintre dificultățile principale în rezolvarea problemei. Capacitatea de a identica relațiile de recurență – și deci de a rezolva problema – se dezvoltă treptat, prin rezolvarea de probleme.

Odată identificată relația de recurență, este necesară stabilirea unui algoritm de rezolvare a recurenței. Datorită suprapunerii subproblemelor, utilizarea recursivității este foarte neeficientă. De regulă se folosește o structură de date suplimentară – tablou unidimensional, bidimensional sau cu mai multe dimensiuni (în funcție de numărul variabilelor care intervin în relația de recurență).

Soluția problemei se află într-un element al tabloului sau se poate determina folosind o parte a elementelor acestuia. Elementele tabloului se vor determina unul câte unul, până când sunt determinate toate elementele necesare pentru aflarea soluției!

Pentru problema scării, notăm tabloul necesar cu V[]. Este un tablou unidimensional deoarece în relația de recurență apare o singură variabilă (n); formula recursivă devine:

• V[1] = 1, V[2]=2;
• V[n] = V[n-1] + V[n-2], pentru n>2;

Inițializăm primele două elemente ale tabloului, iar celelalte elemente vor fi construite unul după altul, de la stânga spre dreapta. Rezultatul se va găsi în V[n].

V[1] = 1, V[2] = 2;
for(int i = 3 ; i <= n ; i ++)
    V[i] = V[i-1] + V[i-2];
cout << V[n];

Metoda folosită mai sus pentru rezolvarea recurenței se numește bottom-up. Tabloul se construiește “de jos în sus”, element cu element, până la cel căutat. Toate elementele tabloului au fost completate cu valori.

O altă metodă de rezolvare a recurenței este top-down, “de sus în jos”. Metoda folosește recursivitatea, dar, pentru a evita rezolvarea de mai multe ori a subproblemelor, folosește memoizarea: soluția fiecărei subprobleme rezolvate este memorată într-un tablou și când trebuie să rezolvăm aceeași subproblemă cunoaștem deja soluția!

Următoarea secvență rezolvă problema scării (șirul lui Fibonacci) folosind memoizarea:

long long V[100];

long long T(int n)
{
    if(V[n] != 0)
        return V[n];        
    if(n < 3)
        V[n] = n;
    else
        V[n] = T(n-1) + T(n-2);
    return V[n];
}

Concluzii

• o problemă se rezolvă prin metoda programării dinamice dacă se poate descompune în subprobleme superpozabile și care respectă principiul optimalității;
• se identifică relația de recurență pentru subprobleme și structura de date ajutătoare;
• se rezolvă recurența, folosind metoda bottom-up sau top-down.