力扣1696.跳跃游戏 VI
递推
-
class Solution {public:int maxResult(vector<int>& nums, int k) {int n = nums.size();vector<int> f(n);f[0] = nums[0];for(int i=1;i<n;i++)f[i] = *max_element(f.begin() + max(i-k,0),f.begin() + i) + nums[i];return f[n-1];}};
单调队列优化
-
保证队首就是转移来源最大值的下标
-
class Solution {public:int maxResult(vector<int>& nums, int k) {int n = nums.size();vector<int> f(n);f[0] = nums[0];deque<int> q = {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.empty() && f[i] >= f[q.back()])q.pop_back();q.push_back(i);}return f[n-1];}};
