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:

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 $s$, acestea vor arata aşa:

*$j=1 =>
<tex>suma = dp[i-1][0]</tex> = 1

         <tex>@suma_de_suma@ = dp[i-1][0]</tex> = 1$

         <tex>suma@_de_@suma = dp[i-1][0]</tex> = 1$

care devin după update
        $<tex>suma = dp[i-1][0]+dp[i-1][j]</tex>$

        $<tex>@suma_de_suma@=2*dp[i-1][0]+dp[i-1][1]</tex>$

        $<tex>suma@_de_@suma=2*dp[i-1][0]+dp[i-1][1]</tex>$

*$j=2 =>
<tex>suma = dp[i-1][0] + dp[i-1][1]</tex>

         <tex>@suma_de_suma@ = 2*dp[i-1][0] + dp[i-1][1]</tex>$

         <tex>suma@_de_@suma = 2*dp[i-1][0] + dp[i-1][1]</tex>$

care devin după update
         $<tex>suma = dp[i-1][0] + dp[i-1][1]</tex>$

         $<tex>@suma_de_suma@=2*dp[i-1][0]+dp[i-1][1]</tex>$

         $<tex>suma@_de_@suma=2*dp[i-1][0]+dp[i-1][1]</tex>$