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 $

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 2 matrici auxiliare:
 
@to_left[ i ][ j ] = a_i + opt[ i + 1 ][ j ]@
@to_right[ i ][ j ] = a_j + opt[ i ][ j - 1 ]@
 
 

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)