Leetcode Problem 1696. Jump Game VI

1696. Jump Game VI

Leetcode Solutions

Approach: Dynamic Programming + Deque

  1. Initialize a deque dq to store pairs of indices and their corresponding scores.
  2. Initialize score with the value of nums[0] since that's the starting point.
  3. Iterate over the array nums starting from index 1.
    • For each index i, first remove indices from the front of dq that are out of the current window (i.e., smaller than i-k).
    • Update score to the sum of nums[i] and the score of the front element of dq.
    • While the deque is not empty and the last element's score is less than the current score, pop elements from the back of the deque.
    • Add the current index and score as a pair to the back of the deque.
  4. Return the score of the last element.
UML Thumbnail

Approach: Dynamic Programming + Priority Queue

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...