DP with Monotonic queue: 1696 Jump Game VI

This is the third problem of the weekly contest from Leetcode of Dec 19, 2020.

1696. Jump Game VI

DP look forward TLE (O(n*k))

Since both n and k can be 10⁵, it is not surprising that the following code will get TLE.

class Solution {
public:
    int maxResult(vector<int>& nums, int k) {
        const int n = nums.size();
        int ret = 0;
        vector<int> dp(n, INT_MIN);
        dp[0] = nums[0];
        for (int i = 0; i < n; ++i) {
            for (int j = 1; j <= k; ++j) {
                if (i+j < n) {
                    dp[i+j] = max(dp[i+j], dp[i] + nums[i+j]);
                }
            }
        }
        return dp[n-1];     
    }
};

DP look backward TLE (O(n*k))

class Solution {
public:
    int maxResult(vector<int>& nums, int k) {
        const int n = nums.size();
        int dp[n];
        dp[0] = nums[0];
        for (int i = 1; i < n; ++i) {
            int thisMax = dp[i-1];
            for (int j = k; j > 1; --j) {
                if (i - j >= 0) thisMax = max(thisMax, dp[i-j]);
            }
            dp[i] = thisMax + nums[i];
        }
        return dp[n-1];
    }
};

When changing the problem to look backward, we can realize this is actually can be improved through the tricks used for the classical maximum sliding window problem. For the maximum sliding window problem, see my previous post.

Look backward DP with multiple set solution (O(n log k))

Code is adjusted from hank
https://leetcode.com/hank55663/

class Solution {
public:
    int maxResult(vector<int>& nums, int k) {
        const int n = nums.size();
        int dp[n];
        dp[0] = nums[0];
        multiset<int> ms;
        ms.insert(dp[0]);
        for (int i = 1; i < n; ++i) {
            // remove outdated one
            if (i - k -1 >= 0) ms.erase(dp[i-k - 1]);
            dp[i] = *ms.rbegin() + nums[i];
            // add new one
            ms.insert(dp[i]);
        }
        return dp[n-1];
    }
};

Look backward DP with Monotonic queue O(n) solution

The code is from [zerotrac](https://leetcode-cn.com/u/zerotrac2/)

decreasing monotonic queue

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) {
            while (i - q.front() > 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];
    }
};

increasing monotonic queue

class Solution {
public:
    int maxResult(vector<int>& nums, int k) {
        const int n = nums.size();
        int dp[n];
        dp[0] = nums[0];
        // Elements in the DQ is in increadig order.
        deque<int> DQ{0};
        for (int i = 1; i < n; ++i) {
            // pop the invalid elements from back, 
            // then the last element will be the largest one in the sliding window.
            while(!DQ.empty() && DQ.back() < i - k) DQ.pop_back();
            // the following step is unnecessary (add it will also be fine), 
            // as the above step can garuantee that the used one is valid.
            // while(!DQ.empty() && DQ.front() < i - k) DQ.pop_front();
            // harvest the largest one
            dp[i] = dp[DQ.back()] + nums[i];
            // push the current one into the DQ.
            // if the current one is larger than any old value, pop the old one,
            // use this fresh one as the fresh one can only be better than old one (unless old one is larger than the current one).
            while (!DQ.empty() && dp[i] >= dp[DQ.front()]) DQ.pop_front();
            DQ.push_front(i);
        }
        return dp[n-1];
    }
};