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 $[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 $i \le k \le j$, 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:

Acum devine clară o primă soluţie folosind programarea dinamică. Astfel, să presupunem că notăm cu <tex>$opt[ i ][ j ]$</tex> costul minim al unui arbore construit pe cheile din [i, j] (prin asta notăm (i, i + 1, ..., j). Fie <tex>$r[ i ][ j ]$</tex> 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 <tex>$j-i+1$</tex> 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 <tex>$k$</tex>, 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\min_{i \le k \le j}\{k, $\; cu\;$ opt[i][j] = opt[i][k-1] + a_{k} + 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$.

Avem <tex> $opt[i][j] = 0$ </tex> , pentru j < i.
Cazurile de bază sunt <tex>$opt[i][i] = a_i$</tex> si <tex>$r[i][i] = i$</tex>.

Se observă că răspunsul problemei se află în $opt[1][N]$.
Astfel, am obţinut o soluţie în timp $O(N^3)$.

Se observă că răspunsul problemei se află în <tex>$opt[1][N]$</tex>.
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.
[]