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

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 reducere a complexităţii datorită faptului că <tex>$ r[i][j-1] \le r[i][j] \le r[i+1][j] $</tex> pentru a reduce complexitatea la $O(N^2)$. Această proprietate nu se poate aplica din păcate şi în cazul problemei noastre.

Până acum avem următorul pseudocod pentru calculul recurenţei:

@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. Alternativ, se poate căuta binar $inter[i][j]$ pentru orice $[i,j]$.

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:

Diferenţa faţă de prima recurentă este evidentă: acum trebuie să aflăm minimul pe un interval de linii, în cazul $to_left$, şi minimul pe un interval de coloane, în cazul $to_right$. Atât aflarea mnimului pe un interval, cât şi update-ul acestei valori se poate face în $O(logN)$, folosind 'arbori de intervale':http://infoarena.ro/arbori-de-intervale.

Astfel, am redus complexitatea loopului interior de la $O(N)$ la $O(logN)$.
 

h3(#problema-2). Problema 2: 'Ugly numbers':http://code.google.com/codejam/contest/dashboard?c=32015#s=p1&a=1 (Google Code Jam 2008, Round 1C)
bq. Un număr se numeşte *urât* dacă este divizibil prin oricare dintre numerele prime de o singură cifră, mai exact $2, 3, 5, 7$. Se dă un şir de $N$ cifre. Între fiecare 2 cifre consecutive se poate insera unul dintre semnele + sau -. Dacă nu se inserează un semn, cele 2 cifre sunt concatentate astfel încât să se obţină un număr. Pentru un şir dat de cifre si o variantă de a adăuga semne, prin evaluarea expresiei matematice obţinute prin inserarea semnelor se obţine un număr, numit numărul generat. Să se calculeze câte dintre cele $3^N-1^$ variante de a insera semnele generează numere urâte.