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>

De ce? Pentru că, din cum am definit dinamica, $dp[i-1][x]$ = suma potenţelor tuturor amestecurilor posibile ingerând x păhărele din primele i-1 sucuri. Cum $dp[i][j]$ presupune ingerarea a j pahare $=>$ se vor ingera j-x pahare de tipul i, care vor inmulţi fiecare potenţă cu <tex>(j-x)*hazard[i]</tex>. Adunăm $dp[i-1][j]$ la dp[i][j] deoarece tinerii pot alege sa nu bea niciun shot de tipul i.

De ce? Pentru că, din cum am definit dinamica de cazan, $dp[i-1][x]$ = suma potenţelor tuturor amestecurilor posibile ingerând x păhărele din primele i-1 sucuri. Cum $dp[i][j]$ presupune ingerarea a j pahare $=>$ se vor ingera j-x pahare de tipul i, care vor inmulţi fiecare potenţă cu <tex>(j-x)*hazard[i]</tex>. Adunăm $dp[i-1][j]$ la dp[i][j] deoarece tinerii pot alege sa nu bea niciun shot de tipul i.

Observatie: <tex>$dp[i][0]=1$</tex>,  <tex>1<=i<=n</tex>, ca să ne iasă calculele :)

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

Trecerea de la $O(N*K^2^)$ la $O(N*K)$ se face cu ajutorul sumelor partiale

Trecerea de la $O(N*K^2^)$ la $O(N*K)$ se face cu ajutorul sumelor partiale
 
OBSERVATIE: MLC