Să observăm că dacă considerăm costul unui drum în arbore de la rădăcină la o frunză ca suma valorilor auxiliare din drumul (unic) respectiv, atunci se observă că costul strategiei bazate pe acest arbore este chiar costul maxim al unui drum ! De acum încolo, vom defini costul unui arbore ca costul maxim al unui drum din el. Să exemplificăm pe şirul din exemplu:
p=. !pd?Diagram1.png!

p=. _Fig. 1: În paranteză sunt valorile auxiliare ataşate cheilor

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.

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: