Tranziții — cum legi o stare de cele dinainte

De ce contează?

Gândește-te la un zid de cărămidă. Fiecare cărămidă nouă nu plutește în aer — se sprijină pe cele așezate deja sub ea. Dacă încerci să pui o cărămidă înainte să existe rândul de dedesubt, totul se prăbușește. Programarea dinamică ridică răspunsul exact așa: fiecare stare se sprijină pe stările mai mici, deja rezolvate. Tranziția este rețeta care spune „pe care cărămizi mă sprijin”.

Ce este tranziția

Știi deja că starea este informația pe care o memorezi (de exemplu dp[i] = răspunsul pentru primele i elemente). Tranziția este pasul următor: relația de recurență care calculează valoarea unei stări din stări mai mici, deja rezolvate. Forma generală este mereu aceeași:

dp[stare] = combini(dp[stari anterioare]) + cost

„Combini” poate fi o sumă, un max, un min — depinde de problemă. „Cost” e ceea ce adaugi tu la pasul curent (o valoare, un 1, sau nimic).

Important: o tranziție are sens doar dacă ordinea de completare garantează că stările folosite sunt deja calculate. Dacă dp[i] se sprijină pe dp[i-1] și dp[i-2], atunci trebuie să le completezi pe acelea înainte. Cu indici de la mic la mare, asta înseamnă o simplă buclă crescătoare. Ordinea nu e un detaliu de implementare — face parte din corectitudine.

Tipare de tranziție: sumă vs max/min

Aproape toate tranzițiile pe care le vei întâlni la concurs intră într-unul din două tipare, după întrebarea problemei:

Sumă (numărare) — „în câte moduri pot face X?”. Aduni căile din toate stările anterioare. Exemplu clasic, urcarea unei scări cu pași de 1 sau 2 trepte: dp[i] = dp[i-1] + dp[i-2] (același tipar ca Fibonacci).
Max / min (optimizare) — „care e cel mai bun / mai ieftin rezultat?”. Alegi cea mai bună variantă dintre stările anterioare. Exemplu: la fiecare pas decizi dacă iei elementul curent sau nu: dp[i] = max(dp[i-1], dp[i-2] + v[i]).

Observă structura comună: ambele privesc înapoi spre stări deja rezolvate și le combină. Schimbi doar operatorul (+ pentru numărare, max/min pentru optimizare) și ce cost adaugi.

Exemplu pas cu pas

Vrem cea mai mare sumă de elemente dintr-un vector, fără să alegem două elemente vecine. Stare: dp[i] = suma maximă folosind primele i+1 elemente (adică pozițiile 0..i). Tranziția, la fiecare poziție, are exact două opțiuni:

nu iei v[i] → rămâi cu cel mai bun rezultat de până la i-1: dp[i-1];
iei v[i] → atunci nu poți folosi vecinul i-1, deci pleci de la dp[i-2] și adaugi v[i]: dp[i-2] + v[i].

Tranziția: dp[i] = max(dp[i-1], dp[i-2] + v[i]). Cazurile de bază pornesc manual, fiindcă i-1 și i-2 ar ieși din vector. Luăm v = [3, 2, 7, 10]:

dp[0] = v[0] = 3 (singur element, îl iei)
dp[1] = max(v[0], v[1]) = max(3, 2) = 3 (iei doar pe cel mai mare)
dp[2] = max(dp[1], dp[0] + v[2]) = max(3, 3 + 7) = 10
dp[3] = max(dp[2], dp[1] + v[3]) = max(10, 3 + 10) = 13

Răspunsul e dp[3] = 13 (alegi 3 și 10). Fiecare valoare s-a sprijinit pe două deja calculate — exact rândul de cărămizi de dedesubt.

Implementare C++

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int v[] = {3, 2, 7, 10};
    int n = 4;
    int dp[4];

    // cazuri de baza: i-1 si i-2 ar iesi din vector
    dp[0] = v[0];                       // iei singurul element
    dp[1] = max(v[0], v[1]);            // iei cel mai mare dintre primele doua

    // completare in ordine crescatoare:
    // cand ajung la i, dp[i-1] si dp[i-2] sunt deja gata
    for (int i = 2; i < n; i++) {
        dp[i] = max(dp[i - 1], dp[i - 2] + v[i]);
    }

    cout << dp[n - 1] << "\n";          // 13 (alegi 3 si 10)
    return 0;
}

Observația-cheie

Bucla pleacă de la i = 2 tocmai pentru că tranziția cere dp[i-1] și dp[i-2]. Ordinea crescătoare garantează regula de aur: când folosești o stare, ea trebuie să fie deja calculată. Schimbi sensul buclei și te sprijini pe cărămizi care încă nu există.

Greșeli frecvente

Folosești o stare necalculată încă: dacă parcurgi descrescător (i de la mare la mic) dar tranziția privește înapoi spre i-1, citești valori vechi, nesetate. Ordinea buclei trebuie să urmeze direcția dependențelor.
Tranziție incompletă (uiți un caz): la „suma fără vecini”, dacă scrii doar dp[i] = dp[i-2] + v[i] și uiți varianta „nu iei” (dp[i-1]), pierzi soluții întregi. Acoperă TOATE opțiunile în max/min.
Cazuri de bază lipsă → indici out of range: dacă pleci direct cu i = 0 într-o tranziție ce cere dp[i-2], accesezi dp[-2] — comportament nedefinit. Setează manual dp[0] și dp[1] înainte de buclă.
Confunzi sumă cu max: la o problemă de numărare folosești max în loc de + (sau invers la optimizare). Operatorul tranziției urmează tipul întrebării.

dp	3	3	10	13
	0	1	2	3

Tabloul dp completat de la stânga la dreapta pe v = [3, 2, 7, 10]. Fiecare celulă se sprijină pe cele două dinaintea ei; dp[3] = 13 este răspunsul.

Recapitulare

Tranziția e relația de recurență: dp[stare] = combini(dp[stari anterioare]) + cost, din stări mai mici deja rezolvate.
Tipar după întrebare: sumă (+) pentru numărare, max/min pentru optimizare.
Ordinea de completare e parte din corectitudine: o stare folosită trebuie să fie deja calculată, iar cazurile de bază te feresc de indici în afara vectorului.