5631. 跳跃游戏 VI（单调队列+dp）

5631. 跳跃游戏 VI

单调队列+dp

class Solution {
public:
    int maxResult(vector<int>& nums, int k) {
        int n=nums.size();
        int f[n];
        f[0]=nums[0];
        deque<int>q;
        q.push_back(0);
        for(int i=1;i<n;i++){
            if(q.front()<i-k)q.pop_front();
            f[i]=f[q.front()]+nums[i];
            while(q.size() && f[q.back()]<=f[i])q.pop_back();
            q.push_back(i);
        }
        return f[n-1];
    }
};