Vom calcula costurile $cmin[i]$, reprezentand costul total minim pentru a satisface cererile din lunile $1, 2, .., i$. Algoritmul este descris in continuare in pseudocod:
==code(c) |

* $cmin[ 0 ] = 0$
* $pentru i de la 1 la N$
** $cmin[i]=infinit$
** $pentru j de la 1 la i$
*** $cost_total = cmin[j-1] + F[j] + C[j] * D[j]$
*** $cost_stocare=S[j]$
*** $pentru k de la j+1 la i$
**** $cost_total = cost_total + (C[j]+cost_stocare) * D[k]$
**** $cost_stocare = cost_stocare + S[k]$
*** $daca cost_total < cmin[i] atunci$
**** $cmin[i]=cost_total$

cmin[ 0 ] = 0
pentru i de la 1 la N
cmin[i]=infinit
pentru j de la 1 la i
  cost_total = cmin[j-1] + F[j] + C[j] * D[j]
  cost_stocare=S[j]
  pentru k de la j+1 la i
    cost_total = cost_total + (C[j]+cost_stocare) * D[k]
    cost_stocare = cost_stocare + S[k]
  daca cost_total < cmin[i] atunci
    cmin[i]=cost_total

==
	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.

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

* $cmin[ 0 ] = 0$
* $pentru i de la 1 la N$
** $cmin[i] = infinit$
** $dtotal = 0$
** $cost_stocare = 0$
** $pentru j de la i la 1$
*** $cost_stocare = cost_stocare + S[j] * dtotal$
*** dtotal = dtotal + D[j]
*** cost_productie = F[j] + C[j] * dtotal
*** cost_total = cmin[j-1] + cost_productie + cost_stocare
*** daca cost_total < cmin[i] atunci
**** cmin[i]=cost_total

==code(c) |
cmin[ 0 ] = 0
pentru i de la 1 la N
  cmin[i] = infinit
  dtotal = 0
  cost_stocare = 0
  pentru j de la i la 1
    cost_stocare = cost_stocare + S[j]    dtotal
    dtotal = dtotal + D[j]
    cost_productie = F[j] + C[j]    dtotal
    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$.

Folosind observatia ca fiecare functie este minima pe cel mult un interval, putem folosi un arbore de intervale pentru a stoca in el semidrepte. Aceasta este o utilizare oarecum neobisnuita a unui arbore de intervale, dar vom vedea ca este foarte utila in cazul acestei probleme. Pseudocodul solutiei este urmatorul:

* $; calculeaza vectorii SP si DP$
* $SP[ 0 ] = 0$
* $DP[ 0 ] = 0$
* $pentru i de la 1 la N$
** $SP[i] = SP[i-1] + S[i]$
** $DP[i] = DP[i-1] + D[i]$
* $; calculeaza vectorul cmin$
* $cmin[ 0 ] = 0$
* $pentru i de la 1 la N$
** $finit[i] = cmin[i-1] + F[i]$
** $P[i] = C[i] - SP[i-1]$
** $[li,ri] = find_interval(i) ; gaseste intervalul [li,ri] pe care functia fi este minima$
** $daca intervalul [li, ri] nu este vid$
*** $update(li, ri, i, radacina_arborelui_de_intervale)$
** $cmin[i] = get_min(i) ; determina valoarea minima in punctul i dintre toate functiile existente$
* $suma = 0$
* $pentru i de la 1 la N$
** $suma = suma + SP[i-1] * D[i]$
* $afisaza cmin[N] + suma$

==code(c) |
; calculeaza vectorii SP si DP
SP[ 0 ] = 0
DP[ 0 ] = 0
pentru i de la 1 la N
  SP[i] = SP[i-1] + S[i]
  DP[i] = DP[i-1] + D[i]
; calculeaza vectorul cmin
cmin[ 0 ] = 0
pentru i de la 1 la N
  finit[i] = cmin[i-1] + F[i]
  P[i] = C[i] - SP[i-1]
  [li,ri] = find_interval(i) ; gaseste intervalul [li,ri] pe care functia fi este minima
  daca intervalul [li, ri] nu este vid
    update(li, ri, i, radacina_arborelui_de_intervale)
  cmin[i] = get_min(i) ; determina valoarea minima in punctul i dintre toate functiile existente
suma = 0
pentru i de la 1 la N
  suma = suma + SP[i-1] * D[i]
afisaza cmin[N] + suma
==

Cele $3$ functii a caror implementare mai trebuie descrisa in detaliu sunt: $find_interval$, $update$ si $get_min$.

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

* $*find_interval(i)*$
* $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)$

==code(c) |
find_interval(i)
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)$.