Se observă că costul maxim al unui drum este $42$, minim posibil, exact ca răspunsul din exemplu.
Deci, am redus problema la construirea unui arbore binar de căutare, care are costul minim.

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 intervalul $[i,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, i + 1, ..., j)$ ştiind răspunsul pentru instanţele mai mici (subsecventele de lungime mai mică ca $j-i+1$ pe $(i, i + 1, ..., j)$) ?. Simplu, arborele de cost minim pe

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 (subsecventele 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 $i \le k \le j$, la care se pune ca fiul stang arborele optim pentru [i, k-1], si ca fiu drept arborele optim pentru [k+1, j]. Relatia de recurenta devine:
 
$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$..

h2. Programare dinamica folosind bitmask