De ce contează?
Imaginează-ți un oraș cu străzile așezate ca o tablă de șah. Pornești din colțul de nord-vest și vrei să ajungi la prietenul tău din colțul de sud-est, dar ai o regulă: mergi numai spre est sau numai spre sud, niciodată înapoi. Întrebarea nu este „cât de repede ajungi”, ci „în câte feluri diferite poți ajunge”. Fiecare intersecție se poate atinge venind ori de la vest, ori de la nord — așa că numărul de drumuri până la ea este suma drumurilor din cele două intersecții vecine. Exact acest mod de gândire, repetat sistematic, este programarea dinamică de numărare.
Numărarea cu DP: tranziția adună drumurile
La lecțiile dinainte ai folosit DP pentru optimizări — căutai un maxim sau un
minim. La problemele de numărare întrebarea este altă: „în câte moduri”
se poate ajunge într-o stare. Stările și recurența se gândesc la fel, dar
tranziția se schimbă esențial: în loc să iei max sau min, aduni
contribuțiile tuturor stărilor din care puteai veni.
Forma generală arată așa:
dp[stare] = dp[stare_anterioara_1] + dp[stare_anterioara_2] + ...
Ideea e simplă: dacă într-o stare ajungi venind din mai multe stări anterioare, numărul total de moduri de a o atinge este suma modurilor de a atinge fiecare stare anterioară. Nu pierzi nicio variantă și nu numeri de două ori, fiindcă fiecare drum trece printr-un singur pas final.
Convenția capitolului pentru numărare:
- Init: celulele „imposibile” pornesc de la 0, iar baza (de unde se pleacă, sau marginea cu un singur drum) primește 1.
- Tranziție: SUMĂ, nu max/min.
- Numere mari: rezultatul crește exploziv, deci aplici modulo
1000000007după fiecare adunare. (Vezi lecția de aritmetică modulară pentru de ce%se comportă frumos cu adunarea.)
Exemplu pas cu pas: drumuri pe o grilă
Problema clasică: pe o grilă cu m linii și n coloane, pornești din colțul
stânga-sus (0,0) și vrei să ajungi în dreapta-jos (m-1, n-1), mergând doar
dreapta sau jos. În câte moduri?
Starea: dp[i][j] = câte drumuri duc din (0,0) până în celula (i,j).
Tranziția: în celula (i,j) poți intra fie de sus (i-1,j), fie din stânga
(i,j-1). Deci aduni cele două:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
Init: pe prima linie te poți mișca doar spre dreapta → un singur drum, deci
dp[0][j] = 1. Pe prima coloană doar în jos → tot un singur drum, dp[i][0] = 1.
Hai să completăm o grilă 3×3. Marginile sunt 1, apoi fiecare celulă interioară este suma vecinului de sus și a celui din stânga:
j=0 j=1 j=2
i=0 1 1 1
i=1 1 2 3
i=2 1 3 6dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3dp[2][2] = dp[1][2] + dp[2][1] = 3 + 3 = 6
Răspunsul este dp[2][2] = 6: există 6 drumuri distincte de la colțul
stânga-sus la cel dreapta-jos pe o grilă 3×3.
| dp[1] | 1 | 2 | 3 |
0 | 1 | 2 | |
dp[1][1]=2 | dp[1][2]=3 |
Implementare C++
Completăm tabelul bottom-up, linie cu linie, de la stânga la dreapta. Așa,
când calculezi dp[i][j], celulele de sus și din stânga sunt deja gata. Aplici
modulo după fiecare adunare ca să nu depășești tipul întreg.
#include <iostream>
using namespace std;
const int MOD = 1000000007; // numerele de drumuri cresc exploziv
int main() {
int m = 3, n = 3; // grila m linii x n coloane
long long dp[100][100];
// init margini: un singur drum pe prima linie si prima coloana
for (int j = 0; j < n; j++) {
dp[0][j] = 1;
}
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
// tranzitie: numarare => SUMA contributiilor de sus si din stanga
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD;
}
}
cout << dp[m - 1][n - 1] << "\n"; // 6
return 0;
}Buclele merg crescător pe i și j, deci dp[i-1][j] (rândul de deasupra) și
dp[i][j-1] (vecinul din stânga) sunt mereu deja completate. Marginile pun baza
cu 1, iar interiorul adună. Pentru o grilă 3×3 obții exact 6.
Complexitate
| Mărime | Valoare | De ce |
|---|---|---|
| timp | O(m · n) | completezi fiecare celulă a tabelului o singură dată |
| memorie | O(m · n) | tabelul dp[][] are m · n celule |
| pe celulă | O(1) | o singură adunare și un modulo |
Pentru o grilă m × n, atingi fiecare dintre cele m · n celule exact o dată,
făcând o adunare cu modulo. De aceea soluția DP este eficientă chiar și pentru
griduri mari, acolo unde numărarea „de mână” a drumurilor ar fi imposibilă.
Reține diferența-cheie a capitolului: la optimizare tranziția ia max sau
min; la numărare tranziția adună. Aceeași structură de stări, alt
operator. Dacă te trezești scriind max la o problemă cu „în câte moduri”,
aproape sigur greșești — numeri variantele, deci le însumezi.
- Uiți să inițializezi marginile cu 1: dacă lași
dp[0][j]șidp[i][0]pe 0, toate sumele de mai jos rămân 0 și obții răspuns nul. Marginile sunt baza. - Folosești max/min în loc de sumă: la numărare aduni contribuțiile.
max/minrezolvă optimizări, nu numărări — confuzia dă rezultate complet greșite. - Uiți modulo → overflow: numărul de drumuri depășește rapid
long long. Aplică% 1000000007după fiecare adunare, nu doar la final. - Ordinea greșită a buclelor: dacă parcurgi celulele într-o ordine în care
dp[i-1][j]saudp[i][j-1]nu sunt încă gata, citești valori necalculate. Mergi mereu de sus în jos și de la stânga la dreapta.
Vizualizare
Urmărește cum se umple tabelul 2D celulă cu celulă. La fiecare pas, observă că
valoarea curentă este suma vecinului de sus și a celui din stânga, iar
marginile rămân 1.
Avansează cu săgețile ← și → și urmărește săgețile de la celula de sus și de la cea din stânga spre celula curentă: ele arată exact cele două valori care se adună.
Recapitulare
- La problemele de numărare („în câte moduri”), tranziția DP adună
contribuțiile stărilor anterioare:
dp[i][j] = dp[i-1][j] + dp[i][j-1]. - Pentru drumuri pe grilă, inițializezi marginile cu 1 (un singur drum) și completezi interiorul prin sumă; o grilă 3×3 are 6 drumuri.
- Numărul de moduri crește exploziv, așa că aplici modulo
1000000007după fiecare adunare; complexitatea rămâne O(m · n).