The Double Bound

Knuth's improvement uses: $opt[i][j-1] \leq opt[i][j] \leq opt[i+1][j]$. The left bound says: if $k$ was optimal for $[i, j-1]$, then for $[i, j]$ you won't do better with any $k' < k$.

Expanding the interval rightward makes later splits more attractive, not earlier ones. The right bound says: if $k$ was optimal for $[i+1, j]$, then for $[i, j]$ you won't do better with any $k' > k$. Adding an element on the left makes earlier splits more attractive. Both follow from QI by the same logic as the monotonicity proof. The bounds shrink your search range dramatically.