h1(#NucleulValoros2). 'I. NucleulValoros2':problema/NucleulValoros2

?

Se consideră: <tex> {\ S[i][j] = V[i] + V[i + 1] + ... + V[j] </tex>
 
<tex> D[i][j] = min(D[i][k] + D[k + 1][j] {\ | {\ i \leq k<j) + S[i][j] </tex>
 
Această recurenţă se poate calcula în <tex>O(N^3)</tex>, dar nu este de ajuns pentru această problemă. Se observă că <tex> S[i][j] </tex> are următoarele proprietăţi:
 
<tex> 1. {\ S[a][c] + S[b][d] \leq S[a][d] + S[b][c] {\ | {\ (a \leq b \leq c \leq d) </tex>
<tex> 2. {\ S[b][c] \leq S[a][d] {\ | {\ (a \leq b \leq c \leq d) </tex>
 
Aceste proprietăţi sunt necesare, dar şi suficiente pentru a aplica optimizarea "Knuth-Yao":http://codeforces.com/blog/entry/8219, care reduce complexitatea la <tex>O(N^2)</tex>