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 $(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, 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)$).

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

h2. Programare dinamica folosind bitmask