Se variaza valoarea lui $i$ de la $1$ la $N$ si pentru fiecare valoare incercam sa calculam $cmin[i]$. Pentru aceasta, incercam toate valorile $j ≤ i$ care pot reprezenta luna in care sunt produse kilogramele de cascaval necesare in luna $i$. Apoi calculam costul total pentru cazul in care luna $j$ produce cantitatea de cascaval necesara pentru a satisface cererile din lunile $j, j+1, .., i$. In cele din urma vom avea in $cmin[i]$ minimul dintre costurile corespunzatoare fiecarei variante de alegere a lunii $j$. Costul total minim pentru toate cele $N$ luni il avem in $cmin[N]$. Bineinteles, aceasta solutie nu se incadreaza in limita de timp.

he. Programare dinamica cu complexitatea $O(N^2^)$

h3. Programare dinamica cu complexitatea $O(N^2^)$

Algoritmul descris anterior are complexitatea $O(N^3^). El se poate optimiza, insa, usor la complexitatea $O(N^2^)$.

*** cost_total = cmin[j-1] + cost_productie + cost_stocare
*** daca cost_total < cmin[i] atunci
**** cmin[i]=cost_total

Optimizarea adusa este minora, dar importanta. In algoritmul anterior, cel de-al treilea ciclu era folosit pentru a aduna la costul total costul stocarii cantitatilor de cascaval. In varianta optimizata, am schimbat sensul de parcurgere al variabilei $j$ si, in felul acesta, putem calcula pe parcurs o parte din costul de stocare. Practic, la inceputul fiecarei iteratii din cel de-al doilea ciclu, $cost_stocare$ retine costul stocarii cantitatiior de cascaval din lunile $j+1, .., i$, el trebuind actualizat doar cu costul de stocare din luna $j$.
h3. Programare dinamica cu complexitatea $O(N*log^2^N)$

Pseudocodul pentru calculul capatului stanga al intervalului in care functia fi este minima este urmatorul:

*left=i
*right=N
*li=N+1
*cat timp left <= right
**	mid = (left+right)/2
**	fi_mid_1 = finit[i]+(DP[mid]-DP[i-1])*P[i] // valoarea in punctul DP[mid+1]
**	fi_mid_2 = finit[i]+(DP[mid + 1]-DP[i-1])*P[i] // valoarea in punctul DP[mid]
**	fmin1=get_min(mid+1) // valoarea minima in punctul DP[mid+1]
**	fmin2=get_min(mid) // valoarea minima in punctul DP[mid]
**	df1 = fi_mid_1 - fmin1;
**	df2 = fi_mid_2 - fmin2;
**	daca (df1 &lt; 0)
***		li = mid;
***		right = mid - 1;
**	altfel
**	daca (df1 - df2 &gt; 0)
***		left = mid + 1;
**	altfel
***		right = mid - 1;
* ; la sfarsit, in li se afla capatul stanga al intervalului in care fi este minima (sau N+1 daca nu exista un astfel de interval)

* $left=i$
* $right=N$
* $li=N+1$
* $cat timp left <= right$
** $mid = (left+right)/2$
** $fi_mid_1 = finit[i]+(DP[mid]-DP[i-1])*P[i] // valoarea in punctul DP[mid+1]$
** $fi_mid_2 = finit[i]+(DP[mid + 1]-DP[i-1])*P[i] // valoarea in punctul DP[mid]$
** $fmin1=get_min(mid+1) // valoarea minima in punctul DP[mid+1]$
** $fmin2=get_min(mid) // valoarea minima in punctul DP[mid]$
** $df1 = fi_mid_1 - fmin1;$
** $df2 = fi_mid_2 - fmin2;$
** $daca (df1 &lt; 0)$
*** $li = mid;$
*** $right = mid - 1;$
** $altfel$
** $daca (df1 - df2 &gt; 0)$
*** $left = mid + 1;$
** $altfel$
*** $right = mid - 1;$
* $; la sfarsit, in li se afla capatul stanga al intervalului in care fi este minima (sau N+1 daca nu exista un astfel de interval)$

Functiile $update$ si $get_min$ se aplica arborelui de intervale si au complexitate $O(logN)$. Complexitatea functiei $find_interval$ este $O(log^2^N)$.

* $intoarce val_min$
h3. Link-uri utile

* Un 'articol':http://dspace.mit.edu/bitstream/1721.1/5146/1/OR-238-90.pdf care prezinta o solutie a acestei probleme avand complexitate optima $O(N*logN)$
h3. Probleme asemanatoare