Nu aveti permisiuni pentru a descarca fisierul grader_test12.ok
Diferente pentru warm-up-2019/solutii/shoturi intre reviziile #68 si #69
Nu exista diferente intre titluri.
Diferente intre continut:
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:
* j=1 => <tex> suma = dp[i-1][0]</tex> = 1 suma_de_suma =<tex> dp[i-1][0] = 1</tex> 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> * 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> 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>
|_. j|_. suma|_. suma_de_suma| |1|dp[i-1][0]|dp[i-1][0]| |2|dp[i-1][0]+dp[i-1][1]|2*dp[i-1][0]+dp[i-1][1]|