Pagini recente » Diferente pentru algoritmiada-2019/runda-preoji/probleme intre reviziile 3 si 2 | Diferente pentru notiuni-de-geometrie-si-aplicatii intre reviziile 9 si 8 | Diferente pentru warm-up-2019/solutii/shoturi intre reviziile 52 si 53 | Istoria paginii runda/urmasii_lui_taraban | Diferente pentru warm-up-2019/solutii/shoturi intre reviziile 92 si 91
Nu exista diferente intre titluri.
Diferente intre continut:
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. 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>.
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>.
**Cod c++**
==code(cpp)|
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.
