Memoizare — recursie cu memorie (top-down)

Memoizarea: recursie + cache

Știi deja că programarea dinamică înseamnă recursie + memorie: rezolvi subproblemele o singură dată și reții rezultatele. Memoizarea este forma cea mai directă a acestei idei. Pleci de la recursia naturală scrisă după recurență și îi adaugi un singur lucru: un cache, un tablou memo[] în care ții rezultatele deja calculate.

Tiparul are mereu aceiași trei pași la intrarea în funcție:

1. Verifici cache-ul. Dacă memo[stare] e deja calculat, îl returnezi pe loc.
2. Calculezi recursiv, ca într-o recursie obișnuită, dacă nu era în cache.
3. Salvezi în cache rezultatul în memo[stare] înainte să îl returnezi.

Cheia este marca de „necalculat”. La început umpli tot memo[] cu o valoare care nu poate fi un răspuns real — convenția capitolului este -1. Astfel, când vezi -1, știi sigur că starea n-a fost încă rezolvată; orice altă valoare e un rezultat deja gata, pe care îl citești în O(1).

Fără acest cache, recursia ar reface aceleași subprobleme la nesfârșit (exponențial). Cu el, fiecare stare se calculează o singură dată, exact ca la tabloul dp[], doar că aici ordinea o stabilește recursia, nu tu.

Top-down (recursiv, lazy) vs bottom-up (iterativ, tablou)

Aceeași recurență poate fi implementată în două stiluri. Ambele dau același rezultat și aceeași complexitate, dar lucrează diferit.

• Top-down (memoizare) — pornești de la starea mare cerută și cobori recursiv spre cazurile de bază. Calculezi lazy: doar stările de care chiar ai nevoie ajung să fie calculate. Codul seamănă izbitor cu recurența scrisă pe hârtie, plus cache-ul.
• Bottom-up (tabulare) — completezi tabloul iterativ, de la stările mici spre cele mari, într-o ordine pe care o fixezi tu. Nu există stivă de apeluri: totul e o buclă.

Avantaje și dezavantaje, pe scurt:

Regula practică: când recurența e ușor de scris dar ordinea de completare e greu de văzut, memoizarea e mai comodă. Când adâncimea recursiei ar fi enormă sau vrei să strângi memoria, tabularea e mai sigură.

Exemplu pas cu pas: Fibonacci memoizat

Recurența o știi: F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2). Pornim cu memo[] plin de -1 și cerem F(5).

• F(5): memo[5] e -1 → trebuie calculat. Cere F(4) și F(3).
• F(4): -1 → calculează. Cere F(3) și F(2).
• F(3): -1 → calculează. Cere F(2) și F(1) → coboară la cazurile de bază, urcă și salvează memo[2]=1, apoi memo[3]=2.
• Înapoi în F(4): acum cere iar F(2). De data asta memo[2] e 1, nu -1 → îl citește instant din cache, fără să mai recalculeze nimic. Salvează memo[4]=3.
• Înapoi în F(5): cere F(3). memo[3] e 2 → instant din cache. Salvează memo[5]=5.

Observă pasul cheie: al doilea apel pentru F(2) și pentru F(3) nu mai declanșează nicio recursie — răspunsul e deja pe „bilețel”. Exact asta taie costul de la exponențial la liniar.

Implementare C++

Memoizare top-down pentru Fibonacci, cu memo[] inițializat la -1:

#include <iostream>
using namespace std;

long long memo[100];      // cache; -1 inseamna necalculat

long long fib(int n) {
    if (n <= 1) {
        return n;                 // cazuri de baza: F(0)=0, F(1)=1
    }
    if (memo[n] != -1) {
        return memo[n];           // deja in cache: il citim instant
    }
    memo[n] = fib(n - 1) + fib(n - 2);   // calculam recursiv SI salvam
    return memo[n];
}

int main() {
    for (int i = 0; i < 100; i++) {
        memo[i] = -1;             // marcam tot ca necalculat
    }
    cout << fib(10) << "\n";      // F(10)=55
    return 0;
}

Cele trei linii din inima funcției sunt întreg tiparul: verifici cache-ul, calculezi dacă lipsește, salvezi înainte de return. Atât desparte o recursie exponențială de una liniară.

Complexitate

La Fibonacci, ambele variante DP sunt O(n) ca timp. Diferența e practică: top-down ține și stiva de apeluri (deci risc de stack overflow la n uriaș și un cost mic per apel), pe când bottom-up nu folosește stivă deloc și se optimizează ușor la O(1) memorie ținând doar ultimele două valori.

Cache-ul după calcul

După ce fib(10) se termină, memo[] păstrează toate stările atinse — fiecare calculată o singură dată. La un nou apel pentru orice F(i) deja prezent, răspunsul vine instant din cache:

Recapitulare

• Memoizarea = recursie + cache: la intrarea în funcție verifici memo[], calculezi doar dacă lipsește (marcat -1) ȘI salvezi rezultatul înainte de return, ca să nu refaci niciodată aceeași subproblemă.
• Top-down (recursiv, lazy) e aproape de recurență și calculează doar stările folosite, dar ține stiva de apeluri; bottom-up (iterativ, tablou) controlează ordinea și nu folosește stiva — ambele O(n) la Fibonacci.
• Marca „necalculat” trebuie să fie o valoare imposibilă ca răspuns real; altfel confunzi „gol” cu un rezultat valid și cache-ul te induce în eroare.