De ce contează?
Stai la baza unei scări cu 5 trepte. La fiecare pas poți urca fie o treaptă, fie două deodată. În câte feluri diferite poți ajunge sus? Pare o întrebare de numărat pe degete — dar dacă scara are 40 de trepte, „pe degete” nu mai merge. Trucul: ca să afli în câte feluri ajungi pe o treaptă, te uiți doar la cele două trepte de unde ai fi putut păși ultima oară.
Intuiția
Pe o treaptă i poți ajunge doar din două locuri: fie de pe treapta i-1
(făcând un pas de 1), fie de pe treapta i-2 (făcând un pas de 2). Nu există
altă cale de a ajunge sus. Deci numărul de moduri de a fi pe treapta i este
suma modurilor de a fi pe i-1 și pe i-2: fiecare drum care ajungea acolo se
prelungește cu un singur pas final. Asta îți dă regula d[i] = d[i-1] + d[i-2],
cu cazurile de bază d[0] = 1 (un mod să stai la start) și d[1] = 1.
Declicul programării dinamice: o treaptă mare se sprijină complet pe câteva trepte mai mici, deja rezolvate. Dacă reții fiecare răspuns o singură dată, nu mai recalculezi nimic — îl citești gata făcut. De aici saltul de la „număr pe degete" la „umplu un tabel".
Vezi cum funcționează
Urmărește cum se umple tabelul d, celulă cu celulă: fiecare valoare nouă apare
ca suma celor două de dinaintea ei. Treptele deja calculate nu se mai ating —
exact asta înseamnă programarea dinamică.
Folosește ← și → ca să pășești prin algoritm, sau Redă pentru animație. Observă cum fiecare celulă nouă „trage” valoarea din cele două de la stânga ei și le adună.
Scrii direct definiția ca recursie: moduri(n) = moduri(n-1) + moduri(n-2), cu
moduri(0) = 1 și moduri(1) = 1. Funcționează imediat și e corectă.
Pentru a calcula moduri(n), ceri moduri(n-1) și moduri(n-2); fiecare cere
alte două, și tot așa. Arborele de apeluri se dublează la fiecare nivel: O(2^n).
La moduri(40) faci miliarde de apeluri și programul se blochează — deși
răspunsul e un număr mic.
Aceleași subprobleme reapar întruna: moduri(38) e cerut și de moduri(39), și
de moduri(40), iar fiecare îl recalculează de la zero. Dacă rețin rezultatul lui
d[i] o singură dată, îl pot refolosi în loc să-l recalculez.
Țin un tabel d[] și îl umplu o singură dată, de la mic la mare:
d[0] = d[1] = 1, apoi d[i] = d[i-1] + d[i-2] pentru i de la 2 la n.
Fiecare celulă se calculează exact o dată, deci O(n) în loc de O(2^n).
Algoritmul pas cu pas
Vrem d[6] pentru o scară de 6 trepte. Pornim de la cazurile de bază și urcăm,
adunând de fiecare dată cele două celule din stânga.
Cazurile de bază. Pe treapta 0 stai fără să urci (1 mod); pe treapta 1 ajungi doar cu un pas de 1 (tot 1 mod):
| d | 1 | 1 | ? | ? | ? | ? | ? |
| treapta | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
baza | baza |
Treapta 2. d[2] = d[1] + d[0] = 1 + 1 = 2:
| d | 1 | 1 | 2 | ? | ? | ? | ? |
| treapta | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
nou |
Treapta 3. d[3] = d[2] + d[1] = 2 + 1 = 3:
| d | 1 | 1 | 2 | 3 | ? | ? | ? |
| treapta | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
nou |
Treptele 4 și 5. d[4] = d[3] + d[2] = 3 + 2 = 5, apoi
d[5] = d[4] + d[3] = 5 + 3 = 8:
| d | 1 | 1 | 2 | 3 | 5 | 8 | ? |
| treapta | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
nou | nou |
Treapta 6. d[6] = d[5] + d[4] = 8 + 5 = 13:
| d | 1 | 1 | 2 | 3 | 5 | 8 | 13 |
| treapta | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
rezultat |
Recunoști șirul? 1, 1, 2, 3, 5, 8 este chiar șirul lui Fibonacci. Multe
probleme de programare dinamică 1D au exact această formă: fiecare stare se
sprijină pe câteva stări anterioare deja calculate.
Implementare C++
Construim tabelul de jos în sus (bottom-up): mai întâi cazurile de bază, apoi fiecare celulă din cele două de dinainte.
#include <iostream>
using namespace std;
int main() {
int n = 6;
long long d[100]; // d[i] = in cate moduri ajungi pe treapta i
d[0] = 1; // caz de baza: un mod sa stai la start
d[1] = 1; // caz de baza: un singur pas de 1
for (int i = 2; i <= n; i++) {
d[i] = d[i - 1] + d[i - 2]; // vii fie de la i-1, fie de la i-2
}
cout << d[n] << endl; // 13
return 0;
}Pentru n = 6 tabelul devine 1 1 2 3 5 8 13, iar programul afișează 13.
Complexitate
| Caz | Timp | Spațiu |
|---|---|---|
| Mediu | O(n) | O(n) |
Umplem fiecare dintre cele n+1 celule o singură dată, cu o adunare — de aici
timpul liniar. Spațiul e O(n) pentru tabel, dar îl putem reduce la O(1):
d[i] are nevoie doar de ultimele două valori, deci e suficient să ținem două
variabile și să le „rostogolim”:
long long penultim = 1, ultim = 1; // d[0], d[1]
for (int i = 2; i <= n; i++) {
long long curent = ultim + penultim;
penultim = ultim;
ultim = curent;
}
// pentru n >= 1, raspunsul este in ultim; pentru n = 6 -> 13Capcane reale la programarea dinamică 1D:
- Recursie fără memorare.
moduri(n) = moduri(n-1) + moduri(n-2)fără tabel e O(2^n):moduri(40)face miliarde de apeluri și ia TLE. Memorează — fie bottom-up cu tabel, fie top-down salvând rezultatul fiecărui apel. - Cazuri de bază greșite. Dacă pui
d[0] = 0, întreg șirul iese pe jumătate. Verifică mereu pe unnmic, calculabil de mână. - Indexare amestecată / off-by-one. Dacă numerotezi treptele de la 1, ai
nevoie de
d[1]șid[2]ca bază, iar bucla pleacă de lai = 3— altfel citeștid[-1]sau ratezi prima treaptă. Ține-te de o singură convenție (aici: index de la 0) și răspunsul ed[n], nud[n-1]. - Overflow. Numărul de moduri crește ca Fibonacci, deci depășește
intdeja în jurul luin = 47. Foloseștelong long(sau calcul modulo, dacă cerința o spune).