Visualizing Knuth

Imagine a $2$D (two-dimensional) grid where $(i, j)$ is a cell. You fill the grid diagonal by diagonal (by length). For cell $(i, j)$, you look at $(i, j-1)$ (one left) and $(i+1, j)$ (one down).

Their $opt$ values bound where to search. The search range for each cell is small. Across a diagonal, ranges tile the space without much overlap. That's why the total is $O(n)$ per diagonal, $O(n^2)$ overall.