Stări — ce descrie o subproblemă

Ce este o stare

O stare este setul minim de parametri care descriu complet o subproblemă. „Complet” înseamnă: dacă îți spun starea, știi exact ce subproblemă ai de rezolvat, fără nicio altă informație suplimentară.

Pe fiecare stare aplici convenția capitolului:

dp[stare] = răspunsul la subproblema descrisă de acea stare.

Dacă starea e o singură poziție, scrii dp[i]. Dacă ai nevoie de o poziție și de o sumă, scrii dp[i][s]. Dacă lucrezi pe o grilă, scrii dp[i][j]. Forma lui dp îți spune direct din câți parametri e făcută starea.

„Minim” e la fel de important ca „complet”: orice parametru în plus, de care nu ai nevoie, înmulțește inutil numărul de stări — adică memoria și timpul.

Cum o identifici

Întrebarea care îți dă starea aproape de fiecare dată este:

„De ce informație am nevoie ca să continui calculul?”

Tot ce trebuie să știi în acel punct devine parametru al stării. Tot ce nu te mai ajută să decizi pașii următori nu intră în stare.

Câteva tipare des întâlnite:

• dp[i] — „cel mai bun / numărul de moduri până la poziția i”. O singură dimensiune: doar contează unde ai ajuns.
• dp[i][s] — „folosind primele i elemente, obținând suma s”. Două dimensiuni: poziția și suma curentă contează amândouă.
• dp[i][j] — „pe o grilă, ajuns în linia i, coloana j”. Poziția în plan.

Testul rapid: imaginează-ți că cineva îți dă doar valorile din stare și nimic altceva. Poți decide ce faci în continuare? Dacă da, starea e suficientă.

Exemplu pas cu pas

Întrebare: în câte moduri poți urca n trepte, dacă la fiecare pas urci 1 sau 2 trepte odată?

Aplică întrebarea: ca să număr modurile de a continua, de ce am nevoie? Doar de treapta la care mă aflu. Nu contează ce pași am făcut ca să ajung aici — doar poziția curentă. Deci starea e o singură poziție: dp[i].

dp[i] = în câte moduri ajung la treapta i. La treapta i pot ajunge fie de la i-1 (cu un pas de 1), fie de la i-2 (cu un pas de 2):

dp[i] = dp[i-1] + dp[i-2]

cu cazurile de bază dp[0] = 1 (un singur mod să stai pe loc) și dp[1] = 1.

Pentru n = 5, completezi tabloul de la stânga la dreapta:

• dp[0] = 1
• dp[1] = 1
• dp[2] = dp[1] + dp[0] = 2
• dp[3] = dp[2] + dp[1] = 3
• dp[4] = dp[3] + dp[2] = 5
• dp[5] = dp[4] + dp[3] = 8

Răspunsul e dp[5] = 8. Fiecare căsuță a fost calculată o singură dată.

Implementare C++

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;               // citim numarul de trepte

    // dp[i] = in cate moduri ajung la treapta i
    long long dp[100];
    dp[0] = 1;              // un singur mod sa stai pe loc
    dp[1] = 1;              // o singura treapta: un singur mod

    for (int i = 2; i <= n; i++) {
        // ajung la i din i-1 (pas de 1) sau din i-2 (pas de 2)
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    cout << dp[n] << "\n";  // pentru n = 5 -> 8

    return 0;
}

Pentru n = 5, programul afișează 8. Starea e treapta i, iar dp[i] adună răspunsurile celor două subprobleme mai mici de care depinde.

Numărul de stări × cost = complexitate

Aici se vede de ce alegerea stării contează atât de mult:

numărul de stări × costul per stare = complexitatea.

La urcarea treptelor: n + 1 stări (dp[0] … dp[n]), fiecare calculată în O(1) (o adunare). Deci complexitatea e O(n) timp și O(n) memorie.

Generalizat: dacă starea e dp[i][s] cu i până la n și s până la S, ai n × S stări. Dacă fiecare se rezolvă în O(1), complexitatea e O(n × S). De aici și regula „minim”: un parametru în plus poate înmulți totul cu încă o dimensiune.

Greșeli frecvente

Recapitulare

• O stare = parametrii minimi care descriu complet o subproblemă; dp[stare] = răspunsul ei.
• O găsești întrebând „de ce informație am nevoie ca să continui?”; tipare uzuale: dp[i], dp[i][s], dp[i][j].
• Numărul de stări × costul per stare = complexitatea, deci fiecare parametru în plus costă o dimensiune.