Leetcode 1696. Jump Game VI (python)

题目

解法1:暴力dp（TLE）

class Solution:def maxResult(self, nums: List[int], k: int) -> int:if not nums:return 0dp = [float(-inf)]*len(nums)dp[0] = nums[0]for i in range(len(nums)):for j in range(max(i-k,0),i):dp[i] = max(dp[j]+nums[i],dp[i])#print(dp)return dp[-1]

c++版本

class Solution {
    
public:int maxResult(vector<int>& nums, int k) {
    int n = nums.size();vector<int> dp(n,-INT_MAX);dp[0] = nums[0];priority_queue<vector<int>> pq;pq.push({
    dp[0],0});for(int i=1;i<n;i++){
    while(pq.top()[1] < i-k) pq.pop();dp[i] = nums[i] + pq.top()[0];pq.push({
    dp[i],i});}// for(auto& num : dp) cout << num << endl;return dp.back();}
};

解法2：dp+heap

可以发现这边dp的时候，只需要找到之前能够跳到当前这步中的最大值即可，那么可以用heap来维护，把index也放入dp来帮助判断是否能从这个状态转移。复杂度n(logn)

class Solution:def maxResult(self, nums: List[int], k: int) -> int:if not nums:return 0dp = [float(-inf)]*len(nums)dp[0] = nums[0]max_heap = []heapq.heappush(max_heap,(-nums[0],0))for i in range(1,len(nums)):while max_heap[0][1]<i-k:heapq.heappop(max_heap)dp[i] = nums[i] - max_heap[0][0]heapq.heappush(max_heap,(-dp[i],i))#print(dp)return dp[-1]

c++版本

class Solution {
    
public:int maxResult(vector<int>& nums, int k) {
    int n = nums.size();vector<int> dp(n,0);dp[0] = nums[0];priority_queue<vector<int>> pq;pq.push({
    dp[0],0});for(int i=1;i<n;i++){
    while(pq.top()[1] < i-k) pq.pop();dp[i] = nums[i] + pq.top()[0];pq.push({
    dp[i],i});}// for(auto& num : dp) cout << num << endl;return dp.back();}
};

解法3：dp+sliding window

仔细观察可以发现这边的步数k实际就像是一个窗口，从这个角度出发就可以结合sliding window maximum的解法，因为sliding window的解法，每个元素只会入队列一次和出队列一次，所以总体解法就是O(n)的。关于sliding window maximum可以看这边

class Solution:def maxResult(self, nums: List[int], k: int) -> int:if not nums:return 0dp = [float(-inf)]*len(nums)dp[0] = nums[0]dq = collections.deque()dq.append(0)for i in range(1,len(nums)):# similar to liding window maximumwhile dq and dq[0]<i-k:dq.popleft()dp[i] = nums[i] + dp[dq[0]]while dq and dp[dq[-1]]<=dp[i]:dq.pop()dq.append(i)#print(dp)return dp[-1]

c++版本

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