Partiții — sume fără să conteze ordinea

De ce contează?

Ai n bomboane identice și vrei să le împarți în grămăjoare. O grămadă de 4, sau una de 3 plus una de 1, sau două de câte 2... Conteză doar CÂTE bomboane are fiecare grămadă, nu în ce ordine le așezi pe masă. „3 plus 1” și „1 plus 3” înseamnă aceeași împărțire. În câte feluri diferite poți forma grămăjoarele? Numărul acela se numește partiția lui n.

Ce este o partiție

O partiție a unui număr natural n este un mod de a-l scrie ca sumă de numere naturale pozitive, fără să conteze ordinea termenilor. Notăm cu p(n) numărul de partiții.

De exemplu, pentru n = 3:

3
2 + 1
1 + 1 + 1

Deci p(3) = 3. Observă că 2 + 1 și 1 + 2 sunt aceeași partiție — ordinea termenilor e irelevantă.

Partiție vs. compunere

Aici stă capcana cea mai mare. O compunere a lui n e tot o scriere ca sumă de termeni pozitivi, dar la compunere ordinea contează. Pentru n = 3 compunerile sunt 3, 2+1, 1+2, 1+1+1 (adică 4), iar în general n are 2^(n-1) compuneri. Partițiile sunt mai puține fiindcă strângem la un loc toate scrierile care diferă doar prin ordine.

`n`	compuneri (ordine contează)	partiții `p(n)`
3	4	3
4	8	5

Exemplu pas cu pas: p(4) = 5

Enumerăm partițiile lui 4, ținând termenii în ordine nedescrescătoare (de la mare la mic) ca să nu numărăm de două ori aceeași grupare:

4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1

Cinci grupări, deci p(4) = 5.

Ideea de DP

Definim dp[s][k] = numărul de partiții ale sumei s folosind doar termeni ≤ k. Privim termenul k și avem două variante disjuncte:

nu folosim deloc termenul k → ne rămâne dp[s][k-1];
folosim termenul k măcar o dată → scădem un k, dar avem voie să mai punem k-uri, deci dp[s-k][k].

Recurența: dp[s][k] = dp[s][k-1] + dp[s-k][k] (al doilea termen doar dacă s >= k). Răspunsul e dp[n][n]; cazul de bază dp[0][k] = 1 (suma 0 are partiția goală).

Implementare C++

#include <iostream>
using namespace std;

const long long MOD = 1000000007;
const int N = 1005;

long long dp[N][N];     // dp[s][k] = partitii ale lui s cu termeni <= k

int main() {
    int n;
    cin >> n;

    // caz de baza: suma 0 are o singura partitie (cea goala)
    for (int k = 0; k <= n; k++) {
        dp[0][k] = 1;
    }

    for (int s = 1; s <= n; s++) {
        for (int k = 1; k <= n; k++) {
            // varianta 1: nu folosim termenul k
            dp[s][k] = dp[s][k - 1];
            // varianta 2: folosim k macar o data (daca incape)
            if (s >= k) {
                dp[s][k] = (dp[s][k] + dp[s - k][k]) % MOD;
            }
        }
    }

    cout << dp[n][n] << "\n";    // p(n); pentru n=4 -> p(4)=5
    return 0;
}

Varianta optimizată 1D (pe termeni)

Comprimăm tabloul la un singur rând dp[s]: parcurgem termenii k la exterior și sumele crescător la interior (ca la rucsacul cu obiecte nelimitate):

#include <iostream>
using namespace std;

const long long MOD = 1000000007;

int main() {
    int n;
    cin >> n;

    long long dp[1005] = {0};
    dp[0] = 1;                      // suma 0: o partitie

    for (int k = 1; k <= n; k++) {          // termenul curent
        for (int s = k; s <= n; s++) {      // crescator -> reutilizam k
            dp[s] = (dp[s] + dp[s - k]) % MOD;
        }
    }

    cout << dp[n] << "\n";          // pentru n=4 -> 5
    return 0;
}

Complexitate

Variantă	Timp	Spațiu
DP 2D `dp[s][k]`	O(n²)	O(n²)
DP 1D pe termeni	O(n²)	O(n)

Pentru valori mari ale lui n (mii), varianta 1D e cea preferată: același timp, dar memorie liniară.

Observația-cheie

Cheia care transformă numărarea într-un DP corect: fiindcă ordinea nu contează, impui termeni nedescrescători (sau, echivalent, limitezi fiecare termen la ≤ k). Astfel fiecare partiție e generată o singură dată, în forma ei canonică, și nu rămâne nicio dublură de tipul 2+1 față de 1+2.

Greșeli frecvente

Numeri compuneri în loc de partiții: dacă lași ordinea liberă (dp[s] += dp[s-k] cu k la interiorul buclei de sume), obții 2^(n-1), nu p(n). Ordinea termenilor trebuie fixată prin limita ≤ k.
Inițializezi greșit cazul de bază: trebuie dp[0] = 1 (suma 0 are partiția goală). Dacă pui 0, tot DP-ul iese 0.
Dublezi partiții permutând termenii: a permite k mai mare decât termenii deja puși readuce ordinea în joc. De aceea în 2D folosești dp[s-k][k], nu dp[s-k][n].
Overflow: p(n) crește exploziv (p(100) are 9 cifre, p(1000) e uriaș). Lucrează cu long long și aplică % MOD la fiecare adunare, nu doar la final.

p(n)	1	1	2	3	5	7
n	0	1	2	3	4	5

Primele valori p(0..5). Evidențiat: p(4) = 5, partiția pe care am enumerat-o.

Recapitulare

O partiție a lui n îl scrie ca sumă de termeni pozitivi fără să conteze ordinea; compunerea numără și ordinea (2^(n-1)).
DP: dp[s][k] = dp[s][k-1] + dp[s-k][k] (folosești sau nu termenul k), cu dp[0][*] = 1; varianta 1D rulează termenii la exterior.
La numere mari ține totul în long long și aplică % MOD = 1000000007 la fiecare adunare ca să eviți overflow.