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 adăugând <tex>dp[i-1][j]</tex> si o variabila $suma_de_suma$ pe care o updatăm cu $suma$, acestea vor arata aşa:

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 adăugând <tex>dp[i-1][j]</tex> şi o variabila $suma_de_suma$ pe care o updatăm cu $suma$, acestea vor arata aşa:

|_. j|_. suma|_. suma_de_suma|
|1|@1*dp[i-1][0]@

@2*dp[i-1][j-2]+1*dp[i-1][j-1]@|
|3|@1*dp[i-1][0]+1*dp[i-1][1]+1*dp[i-1][2]@
@1*dp[i-1][j-3]+1*dp[i-1][j-2]+1*dp[i-1][j-1]@|@3*dp[i-1][0]+2*dp[i-1][1]+1*dp[i-1][2]@

@3*dp[i-1][j-3]+2*dp[i-1][j-2]+1*dp[i-1][j-1]@|

@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>