Dynamic Programming21 sections · 915 units
Open in Course

The Iteration Order

Processing by length

To use the bound opt[i][j−1]≤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][j−1]opt[i][j-1] and opt[i+1][j]opt[i+1][j] computed before opt[i][j]opt[i][j]. Interval [i,j−1][i, j-1] has length (j−1)−i+1=j−i(j-1) - i + 1 = j - i. Interval [i+1,j][i+1, j] has length j−(i+1)+1=j−ij - (i+1) + 1 = j - i. Both are one shorter than [i,j][i, j]'s length of j−i+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.