h2. $Soluţie N*K, memorie N - 100 puncte$

Deoarece pentru a calcula <tex>dp[i][ceva]</tex> avem nevoie doar de <tex>dp[i-1][altceva]</tex>, folosim doar 2 linii din matrice, de aceea putem să scăpăm de ea şi să păstrăm doar 2 vectori reprezentând ultimele 2 linii in ordinea parcurgerii. De aceea, memoria folosită este <tex>N</tex> în loc de <tex>N*K</tex>.

Deoarece pentru a calcula <tex>dp[i][ceva]</tex> avem nevoie doar de <tex>dp[i-1][altceva]</tex>, folosim doar 2 linii din matrice, de aceea putem să scăpăm de ea şi să păstrăm doar 2 vectori reprezentând ultimele 2 linii in ordinea parcurgerii. Astfel, <tex>dp[j]</tex> va fi fostul <tex>dp[i][j]</tex>, iar <tex>aux[j]<\tex> va fi fostul <tex>dp[i-1][j]</tex>. De aceea, memoria folosită este <tex>N</tex> în loc de <tex>N*K</tex>.

**Cod c++**
==code(cpp)|