Programare dinamică

De ce contează?

Urci o scară și poți face pași de 1 sau 2 trepte. În câte feluri ajungi în vârf? În loc să desenezi toate traseele, observi ceva simplu: la treapta n ajungi fie de la n−1, fie de la n−2. Dacă știi deja răspunsul pentru acele două, l-ai aflat și pe al tău. Asta e programarea dinamică.

Ce este programarea dinamică

Programarea dinamică (DP) rezolvă o problemă spărgând-o în subprobleme care se repetă și memorând rezultatul fiecăreia, ca să nu îl recalculezi. Două ingrediente obligatorii:

Starea — ce reprezintă dp[i] (răspunsul subproblemei i).
Tranziția (recurența) — cum obții dp[i] din stări mai mici, deja calculate.

Observația-cheie

Întrebarea de aur: „pe ce stări mai mici se sprijină starea curentă?”. Dacă găsești recurența și un punct de pornire (cazurile de bază), restul e doar completarea unui tabel de la mic la mare.

Algoritmul pas cu pas

Numărul de moduri de a urca n trepte cu pași de 1 sau 2:

Stare: dp[i] = în câte feluri ajungi la treapta i.
Tranziție: dp[i] = dp[i-1] + dp[i-2] (vii fie de la i−1, fie de la i−2).
Cazuri de bază: dp[0] = 1 (un singur fel: stai pe loc), dp[1] = 1.

Completăm tabelul pentru n = 6:

dp	1	1	2	3	5	8	13
treaptă	0	1	2	3	4	5	6

dp[i] = dp[i-1] + dp[i-2]. La treapta 6 sunt 13 moduri de urcare.

Fiecare celulă e suma celor două dinaintea ei: 2 = 1+1, 3 = 2+1, …, 13 = 8+5.

Implementare C++

#include <iostream>
using namespace std;

const int N = 1000;
long long dp[N];

int main() {
    int n = 6;
    dp[0] = 1;                       // caz de baza: stai pe loc
    dp[1] = 1;                       // caz de baza
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];   // tranzitia
    }
    cout << dp[n] << "\n";           // 13
    return 0;
}

Dacă ai nevoie doar de ultimul rezultat, poți ține numai două variabile (optimizare de spațiu de la O(n) la O(1)):

long long trepte(int n) {
    long long a = 1, b = 1;          // dp[0], dp[1]
    for (int i = 2; i <= n; i++) {
        long long c = a + b;         // dp[i]
        a = b; b = c;                // gliseaza fereastra
    }
    return b;
}

Complexitate

Abordare	Timp	Spațiu
Recursiv naiv (fără memorare)	O(2ⁿ)	O(n)
DP cu tabel	O(n)	O(n)
DP cu 2 variabile	O(n)	O(1)

Greșeli frecvente

Capcane reale de concurs:

Stare prost definită. Dacă nu poți spune în cuvinte ce e dp[i], recurența va fi greșită. Definește starea înainte de a scrie cod.
Cazuri de bază uitate sau greșite. dp[0] și dp[1] trebuie setate manual; altfel citești zerouri și tot tabelul iese 0.
Overflow. Valorile DP cresc exponențial (Fibonacci depășește int pe la al 47-lea termen). Folosește long long sau lucrează modulo, cum cere enunțul.
Ordine greșită de completare. Calculezi dp[i] înainte ca dp[i-1] să fie gata → citești o valoare încă neinițializată. Mergi de la mic la mare.

Vizualizare

Urmărește cum tabelul dp se completează celulă cu celulă, fiecare valoare sprijinindu-se pe cele dinaintea ei:

Indiciu

Folosește ← și → pentru a avansa pas cu pas, sau apasă Redă pentru animație automată.

Recapitulare

DP = spargi în subprobleme repetate și memorezi fiecare rezultat o singură dată.
Definește întâi starea (dp[i]), apoi tranziția și cazurile de bază; completezi de la mic la mare.
Atenție la inițializare, ordinea de completare și overflow (long long / modulo).