h2. $Soluţie backtracking - 10 puncte$

Generăm toate variantele posibile ale vectorului <tex>x</tex> pentru care <tex>x[1] + x[2] + ... + x[N] = K</tex>. Această soluţie obţine 0 sau 10 puncte în funcţie de implementarea backtrackingului, care ar avea complexitatea <tex> O(K^N) </tex> amortizat.

Generăm toate variantele posibile ale vectorului <tex>x</tex> pentru care <tex>x[1] + x[2] + ... + x[N] = K</tex>. Această soluţie obţine 0 sau 10 puncte în funcţie de implementarea backtrackingului, care ar avea complexitatea <tex> O(K^N) </tex> amortizat

h2. $Soluţie N*K^2^ - 50 puncte$
Această soluţie presupune tehnica programării dinamice. Vom folosi matricea $dp[n][k]$, pentru care:

* $dp[i][j]$ = suma potenţelor tuturor amestecurilor posibile ingerând j -shoturi- păhărele din primele i -substanţe interzise- sucuri.

* $dp[i][j]$ = suma potenţelor tuturor amestecurilor posibile ingerând j -shoturi- păhărele din primele i -substanţe interzise- sucuri

De aici deducem recurenţa: <tex>\displaystyle \ dp[i][j]=\sum_{x=0}^{j-1} dp[i-1][x]*(j-x)*hazard[i] + dp[i-1][j]</tex>

    }
==

Obs: MOD=269696969 {**Nice**};

Obs: MOD=269696969 {**Nice**}

h2. $Solutie N*K, memorie N*K - 80 puncte$

@3*dp[i-1][j-3]+2*dp[i-1][j-2]+1*dp[i-1][j-1]@|
Se observă că, inmulţind $suma_de_suma$ cu <tex>hazard[i]</tex>, obţinem rezlultatul pentru $dp[i][j]$.

Cum $suma$ şi $suma_de_suma$ sunt calculate in timpul parcurgerii cu $j$, complexitatea este <tex>O(N*K)</tex>.

Cum $suma$ şi $suma_de_suma$ sunt calculate in timpul parcurgerii cu $j$, complexitatea este <tex>O(N*K)</tex>

**Cod c++**
==code(cpp)|