De ce contează?
Pleci la drum și ai voie să scrii pe un singur bilet ce să nu uiți. Notezi prea puțin — te rătăcești, nu mai știi pe unde să o iei. Notezi prea mult — te îneci în detalii care nu te ajută cu nimic. Biletul perfect are exact ce-ți trebuie ca să decizi următorul pas, nici un cuvânt în plus. Starea unui DP e fix acest bilet: informația minimă din care poți merge mai departe.
De ce alegerea stării e partea grea
În tot capitolul ai văzut tranziții, inițializări, tablouri completate. Dar fiecare dintre ele s-a sprijinit pe o decizie luată înainte: ce este o subproblemă. Aceasta e alegerea stării, și e partea cea mai grea fiindcă nu e mecanică — nu există o formulă care să-ți dea starea.
Odată ce ai starea corectă, restul aproape se scrie singur: tranziția devine „cum leg o stare de stările mai mici”, iar complexitatea iese direct din numărul de stări. Dacă starea e greșită, nimic din ce urmează nu se mai închide.
Întrebări-ghid pentru a găsi starea
Două întrebări te duc, aproape de fiecare dată, la starea potrivită:
- „De ce informație am nevoie ca să iau următoarea decizie?” Tot ce-ți trebuie în acel punct devine parametru al stării. Restul nu intră.
- „Ce se schimbă de la o subproblemă la alta?” Lucrurile care variază sunt candidate de parametri; ce rămâne fix peste tot e parte din enunț, nu din stare.
Pune-ți și testul invers: dacă cineva îți dă doar valorile din stare și nimic altceva, poți decide ce faci în continuare? Dacă da, starea e suficientă. Dacă îți mai trebuie un detaliu, exact acela lipsește din stare.
Procesul în 4 pași
Orice DP din capitol se rezolvă cu același tipar. Le-ai întâlnit separat; aici e ordinea în care le folosești împreună:
- Starea — definește ce descrie
dp[...]. „Ce subproblemă rezolv?” Aceasta e decizia grea; restul depinde de ea. - Tranziția — leagă o stare de stările mai mici. „Cum obțin
dp[stare]din subprobleme deja rezolvate?” - Inițializarea — cazurile de bază, cele mai mici stări, pe care le știi direct, fără tranziție.
- Răspunsul — unde, în tabloul
dp, se află rezultatul cerut. Uneori e o singură căsuță, alteori un maxim peste un rând întreg.
Observă dependența: pasul 2 nu se poate scrie fără pasul 1. De asta gândești întotdeauna starea prima, nu invers.
Tabel: problemă → starea potrivită
| Problema | Întrebarea-cheie | Starea aleasă |
|---|---|---|
| Cea mai lungă subsecvență crescătoare | cu ce element se termină? | dp[i] = lungimea care se termină la i |
| Urcare de trepte (1 sau 2 odată) | la ce treaptă sunt? | dp[i] = moduri de a ajunge la i |
| Rucsac (greutate maximă) | ce obiecte am văzut și ce greutate am? | dp[i][w] cu primele i obiecte, capacitate w |
| Sumă posibilă din submulțime | ce sumă pot atinge? | dp[i][s] = pot obține suma s din primele i |
| Drumuri pe o grilă | pe ce celulă sunt? | dp[i][j] = răspuns la linia i, coloana j |
| Cel mai lung subșir comun | unde sunt în fiecare șir? | dp[i][j] = pe prefixele de lungimi i și j |
Observă tiparul: numărul de dimensiuni ale stării e numărul de lucruri care variază independent între subprobleme.
O stare bună are două calități deodată. E suficientă: descrie complet subproblema, astfel încât din ea singură poți decide tranzițiile. Și e minimă: nu conține niciun parametru care nu schimbă deciziile viitoare. Suficientă fără minimă = corect dar risipitor. Minimă fără suficientă = greșit. Ai nevoie de amândouă.
Greșeli de decizie
Greșeli reale când alegi starea:
- Stare insuficientă: lași afară un parametru de care depinde tranziția (ex.
doar
dp[i]când răspunsul depinde și de suma curentă). Recurența nu se mai închide: ca să calculezidp[i]ai nevoie de informație care nu e în stare. - Prea mulți parametri: adaugi dimensiuni care nu schimbă nicio decizie. Răspunsul rămâne corect, dar numărul de stări explodează — memorie și timp peste limită, deși „pe hârtie” pare doar mai detaliat.
- Alegi starea după tranziție: încerci să scrii formula întâi și speri să reiasă starea. Lucrezi invers: fără să știi ce e o subproblemă, tranziția n-are pe ce să se sprijine.
- Uiți unde e răspunsul: definești corect starea și tranziția, dar la final nu știi din ce căsuță să citești rezultatul (o singură stare? un maxim peste un rând?). Pasul 4 e parte din rezolvare, nu o formalitate.
Recapitulare
- Starea = informația minimă și suficientă din care poți decide pasul următor; o găsești întrebând „ce-mi trebuie ca să continui?” și „ce variază între subprobleme?”.
- Rezolvi orice DP în 4 pași — stare, tranziție, inițializare, răspuns — și gândești starea prima, fiindcă tranziția se sprijină pe ea.
- Numărul de dimensiuni ale stării = câte lucruri variază independent; un parametru insuficient strică răspunsul, unul în plus arde memorie și timp.