Jump Game VI
You can solve this problem using a dynamic programming approach combined with a deque (a doubleended queue). Here’s how you can approach this:
 Initialize a list
dp
of lengthn
(wheren
is the length ofnums
) to keep track of the maximum score at each index. Setdp[0] = nums[0]
.  Use a deque to keep track of the indexes of the
k
most recent elements that can affect the current state.  Iterate through the array starting from index
1
, and for each indexi
: Remove the indexes from the front of the deque that are outside the range
[i  k, i  1]
.  Calculate the maximum score for the current index as
dp[i] = nums[i] + dp[deque[0]]
.  Remove indexes from the back of the deque if the
dp
value at those indexes is less than thedp
value at the current indexi
.  Append the current index
i
to the deque.
 Remove the indexes from the front of the deque that are outside the range
 Return
dp[n  1]
, wheren
is the length of the array.
Here’s the code for this approach:


Explanation:
 The
dp
array keeps track of the maximum score at each index.  The deque stores the indexes that are within the
k
steps and are in decreasing order of theirdp
values.  The final result is the value of
dp
at the last index.
Example:
 For the input
nums = [1,1,2,4,7,3], k = 2
, the output is7
.