Jump Game Vi - Leetcode Solution

Problem Statement:

You are given a 0-indexed integer array nums and an integer k.

You are initially standing at index 0. In one move, you can jump at most k steps forward without going outside the boundaries of the array. That is, you can jump from index i to any index in the range [i + 1, min(n - 1, i + k)] inclusive.

You want to reach the last index (index n - 1). Your score is the sum of all nums[i] for each index i you visited in the array.

Return the maximum score you can get.

Solution:

Approach:

This problem can be solved using dynamic programming. We can maintain an array dp where dp[i] represents the maximum score we can get if we reach index i. To calculate dp[i], we need to consider all the indices from i-k to i-1 that can reach i, and choose the one that gives the maximum score.

We can use a deque to maintain the indices that can reach i. We start by adding index 0 to the deque. We then iterate from index 1 to index n-1, and for each index i, we check the indices in the deque from front to back, and remove the indices that can't reach i. We then add i to the back of the deque. We then calculate dp[i] using the front of the deque. We then remove the indices from the back of the deque that can't reach i-k. Finally, we return dp[n-1].

Algorithm:

1. Initialize a deque dq.
2. Initialize an array dp of size n with all elements as 0.
3. Add index 0 to dq.
4. For i = 1 to n-1, do: a. While dq is not empty and dq front is less than i-k, remove the front element from dq. b. Calculate dp[i] as dp[dq front] + nums[i]. c. While dq is not empty and dp[dq back] <= dp[i], remove the back element from dq. d. Add i to dq.
5. Return dp[n-1].

Code:

Here's the Python implementation of the above algorithm:

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]
        dq = deque([0])

        for i in range(1, n):
            while dq and dq[0] < i - k:
                dq.popleft()
            dp[i] = dp[dq[0]] + nums[i]
            while dq and dp[dq[-1]] <= dp[i]:
                dq.pop()
            dq.append(i)

        return dp[n-1]

Complexity Analysis:

The time complexity of the above algorithm is O(n) because we process each index only once. The space complexity is O(n) because we use an array dp of size n and a deque that can have at most k elements.

1