Cazurile de bază sunt @opt[i][i]@ = a{~i~} si @r[i][i] = i@.
Se observă că răspunsul problemei se află în @opt[1][N]@.

Astfel, am obţinut o soluţie în timp O(N^3).

Astfel, am obţinut o soluţie în timp $O(N^3)$.

Aici trebuie remarcată asemănarea acestei probleme cu cea a determinării arborelui de căutare optim, atunci cand se dau probabilităţile relative de căutare a cheilor. Această problemă se numeşte 'Optimal Binary Search Tree' în literatura de specialitate şi poate fi găsită şi în _Introduction to Algorithms_. În aceasta problemă, se poate aplica o proprietate specială, numită _convexitate_, pentru a reduce complexitatea la $O(N^2)$. Această proprietate reprezintă un concept avansat, care nu se poate aplica în cazul problemei noastre, şi nu va fi discutat în continuare.

Sfârşit.
==

Acum ca să obţinem o complexitate mai bună, ţinând cont şi de numele capitolului, vom încerca să reducem complexitatea loop-ului interior (cel după $k$).
 
 

h2. Programare dinamica folosind bitmask