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ă $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>

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 $dp[i-1][j]$