Jump Game VI — DP + Monotonic Deque

Problem 274 · Jump Game VI

Difficulty: Medium · Pattern: DP + Monotonic Deque

Maximize score jumping at most k steps, scoring nums[i] at each position.

Intuition

dp[i] = nums[i] + max(dp[i-k..i-1]). Use deque to get window max in O(1).

Solutions

# Python
from collections import deque
def maxResult(nums, k):
    n = len(nums)
    dp = [0]*n; dp[0] = nums[0]
    dq = deque([0])  # indices, front = max dp
    for i in range(1, n):
        # Remove out of window
        while dq and dq[0] < i-k: dq.popleft()
        dp[i] = nums[i] + dp[dq[0]]
        # Maintain decreasing
        while dq and dp[dq[-1]] <= dp[i]: dq.pop()
        dq.append(i)
    return dp[-1]

// Java
public int maxResult(int[] nums, int k) {
    int n=nums.length; int[] dp=new int[n]; dp[0]=nums[0];
    Deque<Integer> dq=new ArrayDeque<>(); dq.offer(0);
    for (int i=1;i<n;i++) {
        while (!dq.isEmpty()&&dq.peekFirst()<i-k) dq.pollFirst();
        dp[i]=nums[i]+dp[dq.peekFirst()];
        while (!dq.isEmpty()&&dp[dq.peekLast()]<=dp[i]) dq.pollLast();
        dq.offerLast(i);
    }
    return dp[n-1];
}

Complexity

Time: O(n)
Space: O(n)