h2(#negustori). 'Negustori':problema/negustori

Vom rezolva problema folosind metoda programării dinamice. Iară. :)

Vom rezolva problema folosind metoda programării dinamice. Iară. :)
 
Pornim de la reprezentarea unei modalităţi de repartizare a tuturor celor $n$ negustori la cele $n$ locaţii de pe aleea comercială. O repartizare presupune să avem $0$ sau mai mulţi negustori repartizaţi la locaţia $1$, $0$ sau mai mulţi la locaţia $2$, etc. Ulterior, negustorii se vor deplasa spre următoarele poziţii spre finalul aleii pentru a găsi un loc liber. Astfel, o stare constă în completarea locurilor $k, .., n$ cu negustori rămânând $m$ locuri libere.
 
Fie $dp[k][m]$ numărul de repartizări ale negustorilor pe locurile $k, .., n$, rămânând $m$ locuri libere. Vom face următoarele notaţii: $l[i]$ numărul de negustori locali care preferă locaţia $i$, $cl[i]$ numărul de negustori locali care preferă una din locaţiile între 1 şi $i (cl[i] = l[&#49;] + .. + l[i])$. Pentru a calcula $dp[k][m]$, ne rămâne să repartizăm negustori străini pe locul $k$ pe lângă cei $l[k]$ negustori locali. Această repartizare se realizează în limita locurilor disponibile. Numărul locurilor disponibile este egal cu $ld[k][m] = m+1-l[k]$ (cele $m$ locuri libere la care adăugăm locul $k$ şi scădem pe cele ocupate de negustorii locali). Numărul total de negustori străini rămaşi se obţine scăzând din numărul total de negustori pe cei repartizaţi pe locaţiile $k+1, .., n$ şi pe cei locali repartizaţi pe locaţiile $1, .., k$, adică $ns[k][m] = n-(n-k-m)-cl[k]$. Astfel, numărul total de negustori străini este $ns[k][m] = m+k-cl[k]$. Rezultă că vom alege $i$ negustori străini din cei $ns[k][m]$ pe care îi vom repartiza pe poziţia $k$. Astfel, recurenţa este: <tex> dp[k][m] = \displaystyle\sum_{i=0}^{ld[k][m]} \dbinom{ns[k][m]}{ld[k][m]-i} * dp[k-1][i] </tex>. Avem $dp[&#49;][i] = 1$, oricare $i &ge; 0$. Rezultatul se găseşte în $dp[n][&#48;]$.
 
Complexitatea soluţiei: $O(n^3^)$. Voi îmbunătăţi claritatea soluţiei curând. :)