h1. 'Soluţia':warm-up-2019/solutii/shoturi problemei 'Shoturi':problema/shoturi

h1. 'Soluţia':warm-up-2019/solutii/shoturi problemei 'Căzan':problema/shoturi

h2. $Soluţie backtracking - 10 puncte$

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ă $s$ = <tex> \displaystyle \ \sum_{x=0}^{j-1} dp[i-1][x]</tex> pe care o updatăm adaugând $dp[i-1][j]$

Trecerea de la $O(N*K^2^)$ la $O(N*K)$ se face cu ajutorul sumelor partiale.