Programare dinamică: memoizare și tabelare

Programarea dinamică începe cu o subproblemă bine definită, nu cu declararea unui tabel. Vom număra modurile de a urca o scară cu n trepte, folosind pași de una sau două trepte. Ordinea pașilor contează: 1,2 și 2,1 sunt două urcări diferite.

Comparăm două implementări ale aceleiași relații: memoizarea, care calculează la cerere, și tabelarea, care calculează într-o ordine stabilită. Programul citește un singur întreg, 0 <= n <= 45, și afișează numărul exact de urcări. Nu este necesar calculul modulo în aceste limite.

Cum funcționează

Definim d[i] ca numărul urcărilor care ajung exact la treapta i. Ultimul pas are lungimea unu sau doi. În primul caz, înaintea lui am ajuns la i-1; în al doilea, la i-2. Familiile sunt disjuncte, deci pentru i >= 2 avem d[i] = d[i-1] + d[i-2].

Punem d[0]=1: există un mod de a nu urca deloc, secvența vidă de pași. Punem d[1]=1: singura urcare este un pas de unu. Aceste baze nu sunt rezultate obținute prin formula generală; ele opresc dependențele înainte să apară indici negativi.

Recursia fără memorare ar calcula, de exemplu, ways(3) atât din ways(4), cât și din ways(5). Memoizarea păstrează rezultatul fiecărei stări. Valoarea -1 înseamnă „încă necalculat”; este potrivită deoarece toate răspunsurile sunt nenegative. Verificăm întâi dacă rezultatul există și îl returnăm imediat.

Tabelarea parcurge i de la 2 la n. Când calculăm o stare, ambele dependențe sunt deja cunoscute. Este aceeași matematică, dar fără apeluri recursive. Scrie întotdeauna în cuvinte ce înseamnă un element al tabelului înainte să alegi ordinea buclei.

Tabloul clasic are capacitatea 46, cu indici valizi 0..45. Folosim logic numai n+1 poziții, de la 0 la n. Variantele cu std::vector păstrează aceiași indici: în memoizare păstrăm capacitatea 46, iar în tabelare alocăm n+1 elemente. Operatorul [] rămâne același; nu apare nicio verificare automată a indicilor.

Exemplu urmărit pas cu pas

Pentru n=5, construim următoarele valori:

i       0  1  2  3  4  5
d[i]    1  1  2  3  5  8

La i=4 adunăm 3+2=5. La i=5 adunăm 5+3=8. Pentru n=3 poți verifica direct cele trei urcări: 1,1,1; 1,2; 2,1. Tabelul numără urcările, dar nu le stochează efectiv. Afișarea tuturor urcărilor ar necesita un alt algoritm și un volum de ieșire mult mai mare.

Implementare C++17

Memoizare

Varianta cu tablou clasic:

#include <iostream>
long long memo[46];
long long ways(int n) {
    if (memo[n] != -1)
        return memo[n];
    if (n <= 1)
        return memo[n] = 1;
    return memo[n] = ways(n - 1) + ways(n - 2);
}
int main() {
    int n;
    std::cin >> n;
    for (int i = 0; i <= n; ++i)
        memo[i] = -1;
    std::cout << ways(n) << '\n';
}

Varianta echivalentă cu std::vector folosește aceleași limite și aceiași indici:

#include <iostream>
#include <vector>
std::vector<long long> memo(46);
long long ways(int n) {
    if (memo[n] != -1)
        return memo[n];
    if (n <= 1)
        return memo[n] = 1;
    return memo[n] = ways(n - 1) + ways(n - 2);
}
int main() {
    int n;
    std::cin >> n;
    for (int i = 0; i <= n; ++i)
        memo[i] = -1;
    std::cout << ways(n) << '\n';
}

Tabelare

Varianta cu tablou clasic:

#include <iostream>
int main() {
    int n;
    std::cin >> n;
    long long d[46] = {};
    d[0] = 1;
    if (n >= 1)
        d[1] = 1;
    for (int i = 2; i <= n; ++i)
        d[i] = d[i - 1] + d[i - 2];
    std::cout << d[n] << '\n';
}

Varianta echivalentă cu std::vector folosește aceleași limite și aceiași indici:

#include <iostream>
#include <vector>
int main() {
    int n;
    std::cin >> n;
    std::vector<long long> d(n + 1, 0);
    d[0] = 1;
    if (n >= 1)
        d[1] = 1;
    for (int i = 2; i <= n; ++i)
        d[i] = d[i - 1] + d[i - 2];
    std::cout << d[n] << '\n';
}

De ce funcționează și cât costă

Fiecare urcare nevide are exact unul dintre cele două tipuri de ultim pas. Eliminarea acestui pas produce o urcare a unei scări mai mici, iar adăugarea lui este reversibilă. Bazele sunt corecte; prin inducție, fiecare sumă numără toate urcările fără repetări.

Ambele variante fac O(n) calcule și folosesc O(n) memorie. Memoizarea mai folosește O(n) niveluri de stivă. Tabelarea poate păstra numai ultimele două valori, dar pentru învățare întregul tabel face stările vizibile.

Greșeli frecvente

Nu confunda numărul treptelor cu numărul apelurilor recursive. Nu lăsa memo inițializat cu zero dacă verificarea caută -1. Nu aplica relația pentru i=1 și nu considera răspunsul pentru n=0 egal cu zero. Pentru limite mai mari, verifică atât depășirea tipului numeric, cât și adâncimea recursiei.

Exersează

Calculează răspunsul pentru n=6. Apoi schimbă pașii permiși în unu sau trei și scrie bazele și primele cinci valori.

Rezolvare explicată: Cu pași de unu sau doi, d[6]=8+5=13. Cu pași de unu sau trei, d[0]=d[1]=d[2]=1; pentru i>=3 adunăm d[i-1]+d[i-3]. Valorile de la zero la patru sunt 1,1,1,2,3.

Probleme de practică

Rezolvă cele trei probleme în ordinea de mai jos. Deschide fiecare problemă, scrie soluția și verific-o folosind testele locale din pagină. Respectă formatul de intrare, limitele și ieșirea cerută; acestea pot diferi de programul din lecție. Trimiterea pentru punctaj necesită autentificare și un evaluator activ.

1. Urcarea scării. Aplică aceeași recurență prin memoizare și prin tabelare. Verifică separat scara cu zero trepte; problema permite n până la 80, deci adaptează capacitatea tabloului și folosește long long.

2. Pași de una sau trei unități. Schimbă pașii permiși și justifică noile cazuri de bază. Respectă calculul modulo cerut în enunț.

3. Fără trei zerouri consecutive. Extensie: alege o stare care reține câte zerouri consecutive se află la final. Nu este suficient să memorezi doar ultima cifră.

Continuă să înveți

Înapoi la programarea dinamică. Recapitulează tablourile și recursivitatea.

Întrebări frecvente

Când merită memoizarea?

Când recursia descrie natural dependențele și poate evita stări care nu sunt cerute. În problema scării sunt accesate aproape toate stările, deci avantajul principal este claritatea relației.

De ce nu este suficientă recursia simplă?

Ea recalculează subprobleme identice. Memorarea elimină această repetare, iar timpul scade de la o creștere exponențială la una liniară.

Trebuie să folosesc mereu -1?

Nu. Marcajul trebuie să fie distinct de orice răspuns valid. Poți folosi și un tablou separat de stări calculate.

De ce contează ordinea pașilor?

Problema numără trasee prin trepte. Pașii 1,2 și 2,1 trec prin alte poziții intermediare și reprezintă urcări diferite.

Memoizarea rezolvă automat ciclurile?

Nu. Dacă o stare depinde din nou de ea înainte să fie finalizată, simpla memorare a rezultatelor nu rupe ciclul. Trebuie analizat modelul dependențelor.