When Naive DP Fails

Consider $dp[i] = \min_{j < i}(dp[j] + cost(j, i))$. For each of $n$ states, you check $O(n)$ previous states. That's $O(n^2)$. For interval DP like $dp[i][j] = \min_k(dp[i][k] + dp[k+1][j]) + cost(i,j)$, you have $O(n^2)$ states and $O(n)$ choices per state. That's $O(n^3)$.

With $n = 10^5$ or even $n = 4000$, these are too slow. But what if you didn't need to check every $j$ or every $k$?