De ce contează?
Ții un jurnal de economii. Ca să decizi cât poți cheltui mâine, nu reciteşti toate paginile de la început — îți ajunge un singur număr: soldul de azi. Tot trecutul, oricât de complicat, s-a strâns în acea cifră. Soldul de azi e o stare: informația minimă care îți spune tot ce contează ca să mergi mai departe. Regula prin care soldul de azi devine soldul de mâine (adaugi venitul, scazi cheltuiala) e o tranziție. Exact așa gândești orice problemă de programare dinamică: găsești „soldul" potrivit și regula care leagă o zi de următoarea.
Ideea-cheie
În lecția despre programare dinamică ai văzut că ideea e să nu recalculezi ce ai calculat deja: rezolvi fiecare subproblemă o singură dată și o reții. Dar de unde știi care sunt subproblemele? Aici intervin două întrebări care deblochează orice DP:
- Ce informație minimă descrie o configurație parțială? Răspunsul e starea
— ce indici sau valori formează tabloul
d[...]. - Cum obțin o stare din stările anterioare? Răspunsul e tranziția — formula de recurență.
Nu trebuie să inventezi un algoritm nou de fiecare dată. Trebuie doar să răspunzi la aceste două întrebări, plus să stabilești cazurile de bază și ordinea în care calculezi. Restul vine singur.
Orice problemă de programare dinamică = stare + tranziție + caz de bază. Dacă definești corect starea (atât cât îți trebuie ca să continui, nimic în plus), recurența vine aproape de la sine: te întrebi doar „din ce stări anterioare pot ajunge aici?". Greutatea reală a DP nu e în cod — e în alegerea stării.
Cum alegi
Întâi: e chiar o problemă de DP?
Înainte să cauți starea, verifică dacă DP-ul are sens aici. Două condiții trebuie să fie adevărate amândouă:
- Substructură optimă — răspunsul optim pentru o configurație se construiește din
răspunsurile optime ale unor configurații mai mici. Pe scară: cel mai bun mod de a
ajunge la treapta
ise exprimă prin treptele de dinainte. Dacă optimul mare nu se sprijină pe optimuri mai mici, DP nu te ajută. - Subprobleme care se repetă — aceeași subproblemă apare de mai multe ori. Dacă
desenezi recursivitatea naivă, vezi că
d[i-2]e cerut și ded[i], și ded[i-1]. Tocmai pentru că se repetă merită să reții rezultatul o singură dată. Dacă fiecare subproblemă apare exact o dată (ca la o simplă parcurgere), nu ai ce memora — nu e DP.
Reflexul: „aleg dintre mai multe variante la fiecare pas, iar aceeași subîntrebare revine mereu" → miroase a DP. „Fac un singur drum, fără variante și fără repetări" → nu e.
Cum identifici starea
Pune-ți o singură întrebare: „ce ar trebui să știu ca să continui, fără să reiau trecutul?" Tot ce ai nevoie să continui intră în stare; tot ce nu-ți folosește, lasă afară. Starea trebuie să fie suficientă (conține tot ce contează) și minimă (nimic de prisos, altfel tabloul devine inutil de mare).
La urcarea scării (sari câte 1 sau 2 trepte, în câte moduri ajungi la treapta n?)
întrebarea devine: ca să știu în câte moduri ajung la o treaptă, ce-mi trebuie? Doar
numărul treptei. Nu contează cum am ajuns acolo, doar că sunt acolo. Deci
starea e d[i] = numărul de moduri de a ajunge la treapta i. Un singur indice —
asta e tot.
Uneori un singur indice nu ajunge. La „pot alege niște numere din primele i care să
dea suma exactă s?" întrebarea-test te obligă să reții două lucruri: până unde ai
ajuns în șir și cât ți-a mai rămas de format. Starea devine d[i][s] — o pereche.
Mai puțin de atât (doar i, sau doar s) ar pierde informație și ai răspunde greșit;
mai mult ar fi de prisos. Nu rezolvăm problema aici — ideea e doar cum recunoști că
starea cere două coordonate, nu una.
Cum scrii tranziția
Acum întreabă: „din ce stări anterioare pot ajunge aici?" Pe scară, la treapta
i poți ajunge fie printr-un pas de 1 (de la i-1), fie printr-un pas de 2 (de la
i-2). Adună modurile din ambele surse:
d[i] = d[i-1] + d[i-2]
Tranziția e doar oglinda tranzițiilor din enunț: fiecare „mutare permisă" devine un
termen în sumă. Dacă în enunț poți sări 1, 2 sau 3 trepte, tranziția are trei
termeni: d[i] = d[i-1] + d[i-2] + d[i-3].
Tiparul pe câteva exemple
Același tipar se aplică la probleme care par foarte diferite. Privește cum se schimbă doar starea și tranziția, dar structura rămâne aceeași:
| Problema | Starea d[...] | Tranziția | Caz de bază |
|---|---|---|---|
| Urcarea scării (1 sau 2 trepte) | d[i] = moduri de a ajunge la treapta i | d[i] = d[i-1] + d[i-2] | d[0] = 1, d[1] = 1 |
Sumă maximă până la poziția i (subsecvență ce se termină în i) | d[i] = suma maximă a unei subsecvențe care se termină exact în i | d[i] = a[i] + max(0, d[i-1]) | d[0] = a[0] |
Număr de moduri de a forma suma s (cu monede de 1, 2, 3) | d[s] = moduri de a obține suma s | d[s] = d[s-1] + d[s-2] + d[s-3] | d[0] = 1 |
Citește tabelul pe coloane, nu pe rânduri. Coloana „Starea" răspunde mereu la „ce-mi trebuie ca să continui?". Coloana „Tranziția" răspunde la „din ce vin?". Coloana „Caz de bază" prinde stările cele mai mici, pe care nu le poți deduce din nimic anterior — le scrii direct.
Ordinea de calcul
Mai e un detaliu care strică totul dacă îl ignori: ordinea. Ca să calculezi
d[i], ai nevoie ca d[i-1] și d[i-2] să fie deja gata. Pe scară, asta înseamnă
că mergi de la mic la mare: i crește de la 2 spre n. Regula generală: o stare
se calculează după toate stările de care depinde. Dacă tranziția folosește
indici mai mici, parcurgi crescător; dacă folosește indici mai mari, parcurgi
descrescător.
Urmărește urcarea scării pentru n = 5, calculată în ordine crescătoare:
i | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
d[i] | 1 | 1 | 2 | 3 | 5 | 8 |
Fiecare valoare e suma celor două dinaintea ei: d[2] = d[1] + d[0] = 2,
d[3] = d[2] + d[1] = 3, și tot așa până la d[5] = 8. Cazurile de bază d[0]
și d[1] au pornit lanțul; restul s-a calculat singur, în ordine.
Capcanele care strică un DP altfel corect:
- Stare prea mică. Dacă starea nu reține tot ce-ți trebuie ca să continui, recurența devine greșită: două configurații diferite ajung în „aceeași" stare și amesteci răspunsuri care n-au legătură. Test rapid: „dacă mi-ai da doar starea, aș putea continua fără să știu nimic despre cum am ajuns aici?" Dacă nu, mai adaugă o coordonată.
- Stare prea mare. Greșeala inversă: bagi în stare informație de care nu ai nevoie ca să decizi mutarea următoare. Tabloul se umflă inutil și depășești timpul sau memoria (TLE/MLE) deși logica era corectă. Aruncă orice coordonată fără de care recurența rămâne adevărată.
- Ordine de calcul greșită. Dacă parcurgi în ordinea nepotrivită, folosești
d[...]care încă n-a fost calculat (e zero sau gunoi) și obții valori aiurea. Calculează mereu o stare după stările de care depinde. - Uitarea cazurilor de bază. Stările cele mai mici nu pot fi deduse din nimic anterior — dacă nu le inițializezi explicit, tot lanțul pornește de la zero și rezultatul e greșit. Înainte să scrii recurența, întreabă-te de unde începe.
- DP unde nu se repetă nimic. Dacă subproblemele nu se suprapun (fiecare apare o singură dată), n-ai ce reține: tabloul nu economisește nimic, doar complică o parcurgere simplă. DP-ul ajută doar când aceeași subîntrebare revine.