Acum devine clară o primă soluţie folosind programarea dinamică. Astfel, să presupunem că notăm cu @opt[ i ][ j ]@ costul minim al unui arbore construit pe cheile din $[i,j]$ (prin asta notăm (i, i + 1, ..., j). Fie $r[ i ][ j ]$ poziţia rădăcinii arborelui cu costul minim. În cazul existenţei mai multor rădăcini posibile, se alege cea mai din stânga. Cum am putea construi arborele de cost minim pe cheile $[i,j]$ ştiind răspunsul pentru instanţele mai mici (subsecvenţele de lungime mai mică ca $j-i+1$ pe $[i,j]$)? (!) Simplu, arborele de cost minim pe $[i,j]$ se obţine alegând drept rădăcină în mod optim o poziţie $k$, cu <tex>$i \le k \le j$</tex>, la care se pune ca fiul stâng arborele optim pentru $[i, k-1]$, şi ca fiu drept arborele optim pentru $[k+1, j]$. Relaţia de recurenţă devine:

@opt[ i ][ j ]@ = <tex>\displaystyle\min_{i \le k \le j} \{a_{k} + \max( opt[i][k-1], opt[k+1][j] )\} </tex>
@r[ i ][ j ]@ = <tex>\displaystyle\arg \min_{i \le k \le j}\{a_{k} + \max (opt[i][k-1], opt[k+1][j] )\} </tex>

<tex>opt[ i ][ j ] = \displaystyle\min_{i \le k \le j} \{a_{k} + \max( opt[i][k-1], opt[k+1][j] )\} </tex>
<tex>r[ i ][ j ] = \displaystyle\arg \min_{i \le k \le j}\{a_{k} + \max (opt[i][k-1], opt[k+1][j] )\} </tex>

Avem @opt[i][j] = 0@, pentru $j < i$.
Cazurile de bază sunt @opt[i][i]@ = a{~i~} si @r[i][i] = i@.

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.

 
Până acum avem următorul pseudocod pentru calculul recurenţei:
 
== code(cpp) |
Algoritmul este:
    iniţializează opt şi r
    pentru len = 1, N execută
        pentru i = 1, N - len + 1 execută
            j = i + len - 1;
            opt[i][j] = inf;
            pentru k = i, j execută
                dacă opt[i][j] < a[k] + max(opt[i][k-1], opt[k+1][j]) atunci
                    opt[i][j] = a[k] + max(opt[i][k-1], opt[k+1][j]);
                    r[i][j] = k;
            sfârşit_pentru;
       sfârşit_pentru;
    sfârşit_pentru;
 
    return opt[1][N];
Sfârşit.
==

[]

h2. Programare dinamica folosind bitmask