Today's Challenge

https://leetcode.com/problems/jump-game-vi/

Jump Game VI - LeetCode

전형적인 DP 문제면서 내가 잘 못 푸는 유형중에 하나.
파이썬으로 작성된 솔루션은 거의 deque나 priority queue를 활용함.
priority queue로 작성된 코드는 짧으나 조금 이해가 안가서 deque로 작성된 코드 보고 제출.
결국은 이것도 난이도의(혹은 숙련도의) 문제지, 하라는 대로 코드를 짜면 되긴 함.

class Solution:
    def maxResult(self, nums: List[int], k: int) -> int:
        n = len(nums)
        q, dp = deque(), [0] * n
        
        for i, e in enumerate(nums):
            dp[i] = e + (dp[q[0]] if q else 0)
            
            while q and dp[q[-1]] <= dp[i]:
                q.pop()
            q.append(i)
            
            if i == q[0] + k:
                q.popleft()
        return dp[-1]