Jump Game VI

You can solve this problem using a dynamic programming approach combined with a deque (a double-ended queue). Here’s how you can approach this:

  1. Initialize a list dp of length n (where n is the length of nums) to keep track of the maximum score at each index. Set dp[0] = nums[0].
  2. Use a deque to keep track of the indexes of the k most recent elements that can affect the current state.
  3. Iterate through the array starting from index 1, and for each index i:
    • 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 the dp value at the current index i.
    • Append the current index i to the deque.
  4. Return dp[n - 1], where n is the length of the array.

Here’s the code for this approach:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

from collections import deque

class Solution:
    def maxResult(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp = [0] * n
        dp[0] = nums[0]
        deque = collections.deque([0])

        for i in range(1, n):
            # Remove indexes from the front of the deque that are out of range
            while deque and deque[0] < i - k:
                deque.popleft()

            # Calculate the maximum score for the current index
            dp[i] = nums[i] + dp[deque[0]]

            # Remove indexes from the back of the deque if the dp value is less
            while deque and dp[i] >= dp[deque[-1]]:
                deque.pop()

            # Append the current index to the deque
            deque.append(i)

        return dp[n - 1]

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 their dp 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 is 7.