Inițializare — cazurile de bază ale tabelului

De ce contează inițializarea

Știi deja ce e o stare, cum scrii tranziția și că dp se construiește din valori mai mici spre valori mai mari. Dar tranziția nu produce numere din nimic: ea combină valori deja existente în tabel. Asta înseamnă că primele celule — cele pe care nicio tranziție nu le calculează — trebuie să le pui tu, manual. Acestea sunt cazurile de bază.

Pe lângă ele, mai ai un strat ascuns: celulele pe care le citești înainte să le fi umplut, sau stările imposibile (combinații care nu pot fi atinse). Toate aceste celule au o valoare de pornire. Dacă acea valoare „minte” despre realitate, tranziția o crede pe cuvânt și o propagă mai departe.

Regula de aur: valoarea de init nu e arbitrară — depinde de tipul problemei. O celulă neatinsă trebuie să fie un element neutru pentru operația pe care o faci în tranziție (min, max sau adunare de moduri).

Valori de init după tipul problemei

Există trei tipare mari, fiecare cu init-ul lui.

• Numărare (în câte moduri?): tranziția adună moduri. Elementul neutru la adunare e 0, deci tot tabelul pornește cu 0. Excepția e cazul de bază, care e „sămânța”: de obicei dp[0] = 1 (există exact un mod de a nu alege nimic).
• Minimizare (costul minim?): tranziția ia min. O stare neatinsă nu trebuie să poată câștiga niciodată un min, deci pornește de la INF (un număr foarte mare). Cazul de bază real (ex. dp[0] = 0) e singura excepție.
• Maximizare (câștigul maxim?): tranziția ia max. Aici o stare neatinsă pornește de la 0 dacă valorile sunt nenegative, sau de la -INF dacă vrei să marchezi clar că starea e imposibilă (și nu doar „de valoare zero”).

Marcarea stărilor imposibile e partea pe care o uită toți. La minimizare, INF spune „aici nu se poate ajunge”. La maximizare strictă, -INF spune același lucru. Dacă în loc de marcaj pui 0, pierzi diferența dintre „costă 0” și „nu există” — iar la concurs asta înseamnă răspuns greșit.

Exemplu pas cu pas: număr minim de monede

Ai monede de valori {1, 3, 4} și vrei să formezi suma 6 cu cât mai puține monede. dp[s] = numărul minim de monede pentru suma s.

• Caz de bază: dp[0] = 0 — pentru suma 0 îți trebuie zero monede.
• Init pentru rest: dp[s] = INF — încă nu știm dacă s se poate forma.
• Tranziție: pentru fiecare sumă s și fiecare monedă c <= s, dp[s] = min(dp[s], dp[s - c] + 1).

De ce e INF obligatoriu? Imaginează-ți că ai fi pornit cu dp[s] = 0 peste tot. La calcularea lui dp[1] cu monedă 1 ai face min(0, dp[0] + 1) = min(0, 1) = 0. Răspuns: zero monede pentru suma 1?! Absurd. Acel 0 de init a câștigat min-ul și a stricat totul. Cu INF, min(INF, dp[0] + 1) = min(INF, 1) = 1 — corect.

La final, dacă dp[6] a rămas INF, înseamnă că suma 6 nu se putea forma (aici se poate: 3 + 3 → 2 monede).

Implementare în C++

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

// INF mare, dar cu loc de adunat peste el fara overflow de int.
// Aprox un miliard; INF + cost mic ramane in limita int (~2.1 miliarde).
const int INF = 1e9;

int main() {
    int monede[] = {1, 3, 4};
    int nrMonede = 3;
    int suma = 6;

    // init: dp[0] = 0 (caz de baza), restul INF (stare imposibila pana o atingem)
    vector<int> dp(suma + 1, INF);
    dp[0] = 0;

    for (int s = 1; s <= suma; s++) {
        for (int k = 0; k < nrMonede; k++) {
            int c = monede[k];
            // folosim moneda c doar daca starea anterioara e accesibila
            if (c <= s && dp[s - c] != INF) {
                dp[s] = min(dp[s], dp[s - c] + 1);
            }
        }
    }

    if (dp[suma] == INF) {
        cout << "Suma nu se poate forma\n";   // stare ramasa imposibila
    } else {
        cout << "Minim monede: " << dp[suma] << "\n";   // 2 (3 + 3)
    }

    return 0;
}

Verificarea dp[s - c] != INF nu e doar pentru curățenie: te ferește exact de adunarea INF + 1, care e sursa cea mai frecventă de overflow în acest tip de problemă.

Greșeli frecvente

Recapitulare

• Cazurile de bază și valorile de init sunt temelia tabelului dp: tranziția doar combină ce există deja, nu creează valorile de pornire.
• Valoarea de init depinde de tip: numărare → 0 peste tot, dar bază dp[0] = 1; minimizare → INF; maximizare → 0 sau -INF.
• Alege INF mare, dar fără overflow la adunare, și marchează stările imposibile (INF / -1) ca să nu le confunzi cu răspunsuri valide.