LeetCode 1696 Jump Game VI - DP Formulation

Let $dp[i]$ = maximum score to reach index $i$. The base case is $dp[0] = nums[0]$. The transition: $dp[i] = nums[i] + \max_{j=\max(0, i-k)}^{i-1}(dp[j])$.

You take the best score from any reachable previous position and add the current element. Naive implementation: for each $i$, loop through the last $k$ positions. That's $O(nk)$ time. With $n = 10^5$ and $k = 10^5$, you're looking at $10^{10}$ operations. Time to improve.