The Problem

Some DP transitions look like this: $dp[i] = \min_{j=i-k}^{i-1}(dp[j]) + cost[i]$. You need the minimum over the last $k$ states. The naive approach checks all $k$ candidates for each $i$, giving you $O(nk)$ time.

When $n = 10^5$ and $k = 10^4$, that's a billion operations. Your code times out. You need a way to track the minimum without rechecking all candidates every time. What if you could maintain a "shortlist" of candidates that might become optimal?