670. Minimum Cost Jump Game (Monotonic Queue DP)

Starting at index 0, from index i you may jump to any index in [i+1, i+k]. Landing on index i adds nums[i] to your cost. Return the minimum total cost to reach the last index. The input is JSON {nums, k}.

Input: JSON {nums, k}.

Output: Integer — the minimum cost to reach the last index.

Examples

Input: {"nums":[1,-1,-2,4,-7,3],"k":2}
Output: -6
Explanation: An optimal path minimizes cost.

Input: {"nums":[5],"k":1}
Output: 5
Explanation: Already at the end.

Input: {"nums":[3,2,1],"k":1}
Output: 6
Explanation: Must land on every index.

Constraints

• 1<=k<=n<=10^5

Asked by