LeetCode 1696 Jump Game VI - Walkthrough

$dp[i]$ = max score to reach index $i$. From $i$, can jump to $[i+1, i+k]$. Transition: $dp[i] = nums[i] + \max_{j \in [i-k, i-1]} dp[j]$. Array $[1, -1, -2, 4, -7, 3]$, $k = 2$. $dp[0] = 1$. $dp[1] = -1 + dp[0] = 0$. $dp[2] = -2 + \max(dp[0], dp[1]) = -1$. $dp[3] = 4 + \max(dp[1], dp[2]) = 4 + 0 = 4$. $dp[4] = -7 + \max(dp[2], dp[3]) = -7 + 4 = -3$. $dp[5] = 3 + \max(dp[3], dp[4]) = 3 + 4 = 7$.

Answer: 7. Monotonic queue gives $O(n)$ instead of $O(nk)$.