###### tags: `Leetcode` `medium` `dynamic programming` `heap` `sliding window` `python`

# 1696. Jump Game VI

## [題目連結]https://leetcode.com/problems/jump-game-vi/

## 題目:
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 of the array (index ```n - 1```). Your **score** is the **sum** of all ```nums[j]``` for each index ```j``` you visited in the array.

Return the **maximum score** you can get.

**Example 1:**

Input: nums = [1,-1,-2,4,-7,3], k = 2
Output: 7
Explanation: You can choose your jumps forming the subsequence [1,-1,4,3] (underlined above). The sum is 7.

**Example 2:**

Input: nums = [10,-5,-2,4,0,3], k = 3
Output: 17
Explanation: You can choose your jumps forming the subsequence [10,4,3] (underlined above). The sum is 17.

**Example 3:**

Input: nums = [1,-5,-20,4,-1,3,-6,-3], k = 2
Output: 0

## 解題想法:
* 題目為給一數組，從0-index開始走，每次可以走最多k格，求走到nums[-1]，求可獲得最大的得分
* DP動態規劃:
* 暴力法: TLE
* dp+heap: O(NlogN)
* dp+slide window: O(N)
## Python_(Sol1)暴力法: TLE
* 對於i<k:
* dp[i]=nums[i]+max(dp[0],dp[1],.....dp[i-1])
* 對於i>=k:
* dp[i]=nums[i]+max(dp[i-k],dp[i-k+1],...dp[i-1])
* 即其前面k個位置都有機會更新dp[i]

class Solution(object):
    def maxResult(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        dp=[float('-inf') for _ in range(len(nums))]
        dp[0]=nums[0]
        for i in range(len(nums)):
            #對於當前dp[i]，其前面k個位置都有機會更新dp[i]
            for j in range(max(i-k,0),i):
                dp[i]=max(dp[i],dp[j]+nums[i])
        return dp[-1]

## Python_(Sol2)dp+max_heap: O(NlogN)
* 想法: 使用heap:
* 存pair(Weight,pos)
* 將更新的權重都用heap儲存
* 對於當前位置i，找到符合能跳到的位置(i-k)中，最大的值即可
* 最大值即為heap[0][0]

from heapq import heappush,heappop
class Solution(object):
    def maxResult(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        dp=[float('-inf') for _ in range(len(nums))]
        dp[0]=nums[0]
        maxHeap=[]
        #因為heap預設為min_heap，所以加負號視為max_heap
        #即:最大加負號變成最小，優先pop出
        heappush(maxHeap,(-dp[0],0)) #(Weight,pos)
        for i in range(1,len(nums)):
            #當heap中加負號後最小值，其pos不在i-k合理範圍內時
            #pop掉
            while maxHeap[0][1]<i-k:
                heappop(maxHeap)
            dp[i]=nums[i]-maxHeap[0][0]
            heappush(maxHeap,(-dp[i],i))
        return dp[-1]

if __name__=='__main__':
    result=Solution()
    ans=result.maxResult(nums = [1,-1,-2,4,-7,3], k = 2)
    print(ans) #7

## Python_(Sol3) dp+slideWindow: O(N)
* 相同類型題目: [239. Sliding Window Maximum](/BojKaeJ1Qo2HPNnEsC-jMg)
* 設一個queue存位置
* window size(即合理範圍)為當前位置-k
* 每次先while確認que中存的位置是否超出合理範圍
* 需注意! que中的pos，對於dp[pos]，需抱持為decreasing queue: 遞減的!!
* 即ex: que=[5,3,7], dp[5]>=dp[3]>=dp[7]

from collections import deque
class Solution(object):
    def maxResult(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        dp=[float('-inf') for _ in range(len(nums))]
        dp[0]=nums[0]
        que=deque()
        que.append(0) #存pos
        #window size=pos-k
        for i in range(1,len(nums)):
            #確認que最早的位置是否已經超出合理範圍i-k
            while que and que[0]<i-k:
                que.popleft()
            #更新當前dp[i]
            dp[i]=nums[i]+dp[que[0]]
            #從尾剔除que中那些dp[que[x]]小於dp[i]的位置x
            while que and dp[que[-1]]<=dp[i]:
                que.pop()
            que.append(i)
        return dp[-1]
    
'''
" while que and que[0]<i-k: "
說明:
    * 確認que最早的位置是否已經超出合理範圍i-k
    ex: pos=4 k=2 que=[1,2] 
    則安全範圍最多可以往前探索(4-2)=2，即pos:2,3可以有機會更改當前pos4
    所以que[0]=1 超出合理範圍，需pop

" while que and dp[que[-1]]<=dp[i]: "
說明:
    從尾剔除que中那些dp[que[x]]小於dp[i]的位置x
    意義為: que中的pos需保持對於dp[pos]為decreasing queue: 遞減的!!
    因為最尾的一定是最小的dp值，要用肯定不會先用到他
    ex: 因為當前的pos(i)，最終得到dp[i]
    i對於後面i+1...而言，也有機會貢獻自己dp[i]的值
    因為每次新的位置選擇que時，一定是選que[0]，才有先前最大的dp值
    所以對於當前i插入que時，才要比對淘汰掉那些dp值小的前輩，往左邊爬
'''