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 <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:

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>

@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>

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

Să ne uităm mai atent la acest loop.
Fie un interval $[i,j]$ fixat. Acum, $opt[i][j] < opt[i][j']$, pentru orice $j < j'$. Similar, $opt[i][j] < opt[i'][j]$, pentru orice $i' < i$.

Atunci, există un indice $k$, <tex>$i \le k \le j$</tex> astfel încât $max(opt[i][o-1], opt[o+1][j]) = opt[o+1][j]$, pentru orice <tex>$i \le o \le k$</tex>, şi $max(opt[i][o-1], opt[o+1][j]) = opt[i][o-1]$ pentru orice <tex>$k \le o \le j$</tex>. După cum ştim, trebuie să aflăm <tex>\displaystyle\min_{i \le k \le j} \{a_{k} + \max( opt[i][k-1], opt[k+1][j] )\} </tex>. Să definim acum 3 matrici auxiliare:

Atunci, există un indice $k$, $i \le k \le j$ astfel încât $max(opt[i][o-1], opt[o+1][j]) = opt[o+1][j]$, pentru orice $i \le o \le k$, şi $max(opt[i][o-1], opt[o+1][j]) = opt[i][o-1]$ pentru orice <tex>$k < o \le j$</tex>. După cum ştim, trebuie să aflăm <tex>\displaystyle\min_{i \le k \le j} \{a_{k} + \max( opt[i][k-1], opt[k+1][j] )\} </tex>. Să definim acum 3 matrici auxiliare:

@to_left[ i ][ j ]@ = $a{~i~} + opt[ i + 1 ][ j ]$
@to_right[ i ][ j ]@ = $a{~j~} + opt[ i ][ j - 1 ]$

@to_left[ i ][ j ]@ = $a_i + opt[ i + 1 ][ j ]$
@to_right[ i ][ j ]@ = $a_j + opt[ i ][ j - 1 ]$

@inter[ i ][ j ]@ = <tex>\displaystyle\arg \max_{i \le k \le j}\{opt[i][k-1] \le opt[k+1][j]\} </tex>
Se observă că $inter[i][j]$ nu reprezintă altceva decât indicele $k$ tratat in paragraful precedent.

De asemenea, $inter$ poate fi calculată în $O(N^2)$ observând o proprietate simplă: <tex>$ inter[i][j-1] \le inter[i][j] \le inter[i+1][j] $</tex>. Aceasta reiese imediat din monotonia lui $opt$ discutată mai sus.

De asemenea, $inter$ poate fi calculată în $O(N^2)$ observând o proprietate simplă: <tex>$inter[i][j-1] \le inter[i][j] \le inter[i+1][j] $</tex>. Aceasta reiese imediat din monotonia lui $opt$ discutată mai sus.

Acum vine ideea decisivă pentru a reduce complexitatea loop-ului: pentru a afla $opt[i][j]$, este suficient să aflăm minimul dintre 2 valori: