$opt[ i ][ j ]$ = <tex> \displaystyle\min_{i \le k \le j}\{opt[i][k-1] + a_{k} + opt[k+1][j]\} </tex>
$r[ i ][ j ]$ = <tex> \displaystyle\min_{i \le k \le j}\{k, $\; cu\;$ opt[i][j] = opt[i][k-1] + a_{k} + opt[k+1][j] \} </tex>

Avem $opt[i][j] = 0$, pentru $j < i$,
Cazurile de baza sunt $opt[i][i] = a_i$ si $r[i][i] = i$..

Avem $opt[i][j] = 0$, pentru $j < i$.
Cazurile de baza sunt $opt[i][i] = a_i$ si $r[i][i] = i$.
 
Se observa ca raspunsul problemei se afla in $opt[1][N]$
Astfel, am obtinut o solutie in timp $O(N^3)$.
Aici trebuie remarcata asemenarea acestei probleme cu cea determinarii arborelui de cautare optim, atunci cand se dau probabilitatile relative de cautare a cheilor. Aceasta problema se numeste 'Optimal Binary Search Tree' in literatura de specialitate si poate fi gasita si in _Introduction to Algorithms_. In aceasta problema, se poate aplica o proprietate speciala, numita _convexitate_, pentru a reduce complexitatea la $O(N^2)$. Aceasta proprietate reprezinta un concept avansat, care nu se poate aplica in cazul problemei noastre, si nu va fi discutat in continuare.

h2. Programare dinamica folosind bitmask