n elemente, numere naturale. Determinați un cel mai lung subșir crescător al șirului.
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.
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, ∀iLG[n] = 1LG[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];
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);
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].
LG[1]=1;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].
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:
k lungimea șirului D. Inițializăm k=1 și D[k]=A[1];A, începând de la al doilea element:
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 elementA[i]<D[k], vom înlocui cu A[i] pe cel mai mai mic element din D care este mai mare decât acestaATENȚIE: Șirul D[] nu conține un subșir crescător al șirului A[]!
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:
i |
A[i] |
Condiție | Acțiune | D[] |
| 1 | 5 | - | - | (5) |
| 2 | 10 | A[i]>=D[k] |
adăugare | (5, 10) |
| 3 | 7 | A[i]<D[k] |
înlocuire | (5, 7) |
| 4 | 4 | A[i]<D[k] |
înlocuire | (4, 7) |
| 5 | 5 | A[i]<D[k] |
înlocuire | (4, 5) |
| 6 | 8 | A[i]>=D[k] |
adăugare | (4, 5, 8) |
| 7 | 9 | A[i]>=D[k] |
adăugare | (4, 5, 8, 9) |
| 8 | 8 | A[i]<D[k] |
înlocuire | (4, 5, 8, 8) |
| 9 | 10 | A[i]>=D[k] |
adăugare | (4, 5, 8, 8, 10) |
| 10 | 2 | A[i]<D[k] |
înlocuire | (2, 5, 8, 8, 10) |
D sunt în ordine crescătoareA 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)\).
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;
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:
k – lungimea subșirului crescător maximal;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;P[] un element egal cu k-1, anterior elementului de indice Ik. Fie Ik-1 poziția sa.P[] valorile k-2, k-3, ..., 2, 1.(A[I1], A[I2], ..., A[Ik]).Î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;
}
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ă.
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:
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\).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\).(i,j) (cu i>1 și j>1) se poate ajunge în două moduri:
(i-1,j);(i,j-1);(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}\).Î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);
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}\).
n și m se produce overflow. Pentru valori mai mari ale acestora este necesară implementarea operațiilor cu numere mari!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!i se folosesc doar elemente de pe aceasta și de pe linia precedentă, i-1.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:
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 11 1 21 2 12 1 12 2Rezolvare: 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