Dynamic Programming21 sections · 916 units
Open in Course

The Iteration Order

Processing by length

To use the bound opt[i][j1]opt[i][j]opt[i+1][j]opt[i][j-1] \leq opt[i][j] \leq opt[i+1][j], you need both opt[i][j1]opt[i][j-1] and opt[i+1][j]opt[i+1][j] computed before opt[i][j]opt[i][j]. Interval [i,j1][i, j-1] has length (j1)i+1=ji(j-1) - i + 1 = j - i. Interval [i+1,j][i+1, j] has length j(i+1)+1=jij - (i+1) + 1 = j - i. Both are one shorter than [i,j][i, j]'s length of ji+1j - i + 1.

So process intervals by increasing length: first all length-11 (base cases), then length-22, up to length-nn. Each cell's bounds come from the previous length level, which you've already computed.