Solutia optima are, insa, complexitatea $O(N*K)$ si se bazeaza pe urmatoarele concepte: pentru fiecare $i$ de la $1$ la $K$ si fiecare pozitie $j$ de la $1$ la $N$ vom defini doua functii $f{~i,j~}$ si $g{~i,j~}$, pe care le vom folosi in calculul valorilor $cmin[ i ][ j ][ 0 ]$ si $cmin[ i ][ j ][ 1 ]$.
h3. Calculul valorilor cmin[ i ][ j ][ 0 ]
h3. Calculul valorilor $cmin[ i ][ j ][ 0 ]$
Pentru fiecare pozitie j, vom defini functia f{~i,j~}:[d[j],d[N]] -> int. O valoare a acestei functii intr-un punct d[p], corespunzator benzinariei p, f{~i,j~}(d[p]), reprezinta costul minim pentru a amplasa i depozite in benzinariile 1,2,..,p, in conditiile in care al i-lea depozit este in benzinaria p, iar benzinariile j, j+1, .., p sunt alimentate cu combustibil de la depozitul din benzinaria p. Cu aceste definitii, valoarea lui cmin[ i ][ j ][ 0 ] este minimul dintre valorile functiilor f{~i,j{~1~}~}, in punctul d[j], cu 0<=j{~1~}<j, la care se adauga valoarea a[j]. Problema importanta este cum aflam minimul dintre aceste functii, fara a calcula valoarea fiecarei functii in punctul d[j] (care ar conduce la o complexitate O(N^2^*K)).
Pentru fiecare pozitie $j$, vom defini functia $f{~i,j~}:[d[j],d[N]] -> int.$ O valoare a acestei functii intr-un punct $d[p]$, corespunzator benzinariei $p, f{~i,j~}(d[p])$, reprezinta costul minim pentru a amplasa $i$ depozite in benzinariile $1,2,..,p,$ in conditiile in care al $i$-lea depozit este in benzinaria $p$, iar benzinariile $j, j+1, .., p$ sunt alimentate cu combustibil de la depozitul din benzinaria $p$. Cu aceste definitii, valoarea lui $cmin[ i ][ j ][ 0 ]$ este minimul dintre valorile functiilor $f{~i,j{~1~}~}$, in punctul $d[j]$, cu $0<=j{~1~}<j$, la care se adauga valoarea $a[j]$. Problema importanta este cum aflam minimul dintre aceste functii, fara a calcula valoarea fiecarei functii in punctul $d[j]$ (care ar conduce la o complexitate $O(N^2^*K)$).
Formula unei functii f{~i,j~}(d[p]) este: <tex> \displaystyle cmin[ i-1 ][ j-1 ][ 1 ] + \sum_{q = j}^p c_{q} * (d_{p} - d_{q}) </tex> . Diferenta dintre 2 valori consecutive ale functiei, df{~i,j~}(d[p+1]) = f{~i,j~}(d[p+1]) - f{~i,j~}(d[p]), este egala cu (c[j]+c[j+1] + .. + c[p]) * (d[p+1] - d[p]). Asadar, de la un pas la altul, functiile f{~i,j~} care au un j mai mic cresc mai mult decat cele care corespund unei pozitii j mai mari (altfel spus, functiile care au aparut mai recent cresc mai incet decat functiile care au aparut de mai mult timp) : df{~i,j~}(d[p+1]) < df{~i,j{~1~}~}(d[p+1]), daca j{~1~} < j. De aici tragem urmatoarele concluzii:
