Why O(n²) Total

For fixed length $len$, you compute $dp[i][j]$ for all $i$ where $j = i + len - 1$. Each cell searches $k$ from $opt[i][j-1]$ to $opt[i+1][j]$. As $i$ increases, these ranges chain together: the right endpoint of one is the left endpoint of the next.

Example with $n=5$, $len=3$: cell $(1,3)$ searches $[opt[1][2], opt[2][3]]$. Cell $(2,4)$ searches $[opt[2][3], opt[3][4]]$. Cell $(3,5)$ searches $[opt[3][4], opt[4][5]]$. The ranges tile $[1, n]$ without overlap. Total $k$ checks per length: $O(n)$. Summing over $n$ lengths: $O(n^2)$.