Ideea programării dinamice — nu recalcula niciodată

De ce contează?

Imaginează-ți că rezolvi la mate o problemă lungă și, pe parcurs, ai nevoie de același calcul intermediar de zeci de ori. Ai două variante: îl refaci de fiecare dată pe ciornă, pierzând minute prețioase, sau îl scrii o singură dată într-un colț al foii și pur și simplu îl citești când îți mai trebuie. Programarea dinamică este exact al doilea obicei, transformat în algoritm: notezi un rezultat o dată și nu îl mai recalculezi niciodată.

Ce este programarea dinamică

Programarea dinamică (DP) este o tehnică prin care rezolvi o problemă spărgând-o în subprobleme mai mici și reținând rezultatul fiecăreia, ca să nu îl recalculezi atunci când reapare. În capitolul acesta vei ține aceste rezultate într-un tablou numit dp[], pe care îl completezi pas cu pas, de la cazurile de bază spre răspunsul final.

Nu orice problemă merită rezolvată cu DP. Sunt necesare două condiții:

Subprobleme care se suprapun (overlapping subproblems) — aceleași subprobleme reapar de multe ori în timpul rezolvării. Dacă fiecare subproblemă ar apărea o singură dată, nu ai ce reține și DP nu ajută cu nimic.
Substructură optimă (optimal substructure) — răspunsul problemei mari se poate construi din răspunsurile subproblemelor ei. Dacă știi soluțiile mici corecte, le combini într-o soluție mare corectă.

Când ambele condiții sunt îndeplinite, DP transformă o muncă exponențială într-una liniară (sau aproape), pentru că fiecare subproblemă se rezolvă o singură dată.

Exemplu pas cu pas: Fibonacci

Cel mai limpede exemplu este șirul lui Fibonacci, cu cazurile de bază F(0) = 0, F(1) = 1 și pasul F(n) = F(n-1) + F(n-2).

Versiunea recursivă naivă copiază formula direct, dar recalculează la nesfârșit aceleași valori. Ca să calculezi F(5) îți trebuie F(4) și F(3); dar F(4) cere din nou F(3) și F(2), iar F(3) se ramifică iarăși. Pe arborele de recursie vezi cum F(2) este recalculat de mai multe ori, F(1) și mai des:

F(5)
              /      \
          F(4)        F(3)
         /    \       /   \
      F(3)   F(2)   F(2)  F(1)
      /  \    ...    ...
   F(2)  F(1)

Observă: F(2) apare de trei ori, F(3) de două ori — și asta doar pentru n = 5. Pentru n mare, numărul de apeluri explodează exponențial. Aceasta este suprapunerea subproblemelor: aceeași subproblemă, refăcută mereu.

Soluția DP: ții un tablou dp[] unde dp[i] este F(i). Îl completezi o singură dată, de la cazurile de bază spre răspuns:

dp[0] = 0 (caz de bază)
dp[1] = 1 (caz de bază)
dp[2] = dp[1] + dp[0] = 1
dp[3] = dp[2] + dp[1] = 2
dp[4] = dp[3] + dp[2] = 3
dp[5] = dp[4] + dp[3] = 5

Fiecare poziție se calculează o dată, apoi se citește în O(1). Substructura optimă se vede direct: dp[i] se construiește din valori deja gata, mai mici.

dp	0	1	1	2	3	5	8	13	21	34	55
	0	1	2	3	4	5	6	7	8	9	10
										dp(9)=34	dp(10)=55

Tabloul dp[] completat de la cazurile de bază (dp(0), dp(1)) până la dp(10) = 55. Fiecare celulă = suma celor două dinainte.

Implementare C++

Traducerea în cod completează dp[] de la mic la mare (bottom-up): pui întâi cazurile de bază, apoi parcurgi crescător și aplici recurența folosind doar valori deja calculate.

#include <iostream>
using namespace std;

int main() {
    int n = 10;
    long long dp[100];        // tablou destul de mare; F creste repede

    dp[0] = 0;                // caz de baza F(0)
    dp[1] = 1;                // caz de baza F(1)

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];   // foloseste doar valori deja calculate
    }

    cout << dp[n] << "\n";    // F(10)=55
    return 0;
}

Codul rulează o singură buclă: de la 2 la n. La fiecare pas, ambele valori de care are nevoie (dp[i-1] și dp[i-2]) sunt deja completate, fiindcă mergi în ordine crescătoare. Asta e cheia: ordinea de completare garantează că nu citești niciodată o poziție goală.

Complexitate

Abordare	Timp	De ce
recursiv naiv	O(2^n)	se ramifică în doi apeli și recalculează aceleași subprobleme
DP cu `dp[]`	O(n)	fiecare poziție se calculează exact o dată, apoi doar se citește

Diferența este uriașă: pentru n = 50, varianta naivă face miliarde de apeluri și ai aștepta mult, în timp ce varianta DP răspunde instant cu cei n pași ai buclei. Exact aceeași recurență, dar fără risipa recalculării.

Observația-cheie

Reține esența: DP = recursie + memorie. Iei ideea recurenței (un rezultat depinde de rezultate mai mici) și adaugi un loc unde reții ce ai calculat deja. Atât. Acest mic adaos transformă un timp exponențial într-unul liniar, pentru că nicio subproblemă nu mai este rezolvată de două ori.

Greșeli frecvente

Aplici DP unde nu există suprapunere: dacă subproblemele nu reapar (de pildă o simplă parcurgere care atinge fiecare element o dată), tabloul dp[] nu aduce niciun câștig — adaugi complexitate degeaba.
Tablou nedimensionat corect: dacă declari dp[] mai mic decât n, scrii în afara lui — comportament nedefinit. Dimensionează-l după valoarea maximă cerută.
Ordinea greșită a completării: dacă folosești dp[i+1] înainte să-l fi calculat, citești o valoare necalculată (gunoi). Bottom-up cere ordine crescătoare, de la cazurile de bază spre răspuns.
Overflow fără long long: valorile cresc repede (Fibonacci depășește int pe la F(47)). Folosește long long sau lucru modulo, dacă cere problema.

Vizualizare

Urmărește cum se umple tabloul dp[] celulă cu celulă, de la cazurile de bază spre răspunsul final. Vezi limpede că fiecare poziție folosește doar valori deja calculate la stânga ei.

Indiciu

Folosește săgețile ← și → ca să avansezi pas cu pas. La fiecare pas, observă din ce două celule anterioare se formează celula curentă.

Recapitulare

Programarea dinamică rezolvă o problemă reținând rezultatele subproblemelor într-un tablou dp[], completat de la cazurile de bază spre răspuns, ca să nu recalculezi niciodată același lucru.
Merită aplicată doar când există subprobleme care se suprapun ȘI substructură optimă — ambele condiții, simultan.
La Fibonacci, DP transformă O(2^n) (recursiv naiv, care recalculează) în O(n) (fiecare dp[i] calculat o singură dată). Pe scurt: DP = recursie + memorie.