h1. 'Soluţia':warm-up-2019/solutii/shoturi problemei 'Shoturi':problema/shoturi
 

h1. 'Soluţia':warm-up-2019/solutii/shoturi problemei 'Shoturi':virustotal.com

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.

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 parţiale.

Observăm că, dacă atunci când parcurgem cu $j$-ul ţinem o variabilă $suma$ = <tex> \displaystyle \ \sum_{x=0}^{j-1} dp[i-1][x]</tex> pe care o updatăm adaugând <tex>dp[i-1][j]</tex> si o variabila $suma_de_suma$ pe care o updatăm cu $s$, acestea vor arata aşa:
 
*$j=1 => suma = <tex>dp[i-1][0]</tex> = 1 şi suma_de_suma = <tex>dp[i-1][0]</tex> = 1$, care devin după update $suma = <tex>dp[i-1][0]+dp[i-1][j]</tex>$, respectiv $suma_de_suma=<tex>2*dp[i-1][0]+dp[i-1][1]</tex>$
*$j=2 => suma = <tex>dp[i-1][0] + dp[i-1][1]</tex> şi suma_de_suma = <tex>2*dp[i-1][0] + dp[i-1][1]<>/tex$, care devin după update $suma =<tex> dp[i-1][0] + dp[i-1][1]</tex>$, respectiv $suma_de_suma=2*dp[i-1][0]+dp[i-1][1]$

Observăm că, dacă atunci când parcurgem cu $j$-ul ţinem o variabilă $sum$ = <tex> \displaystyle \ \sum_{x=0}^{j-1} dp[i-1][x]</tex> pe care o updatăm adaugând <tex>dp[i-1][j]</tex>