Monotonic Queue in DP

Summary

In this post, I will introduce some DP problems involving the Monotonic Queue.

Details

LC 1425. Constrained Subset Sum

It is not difficult to get the following O(n^2) solution.

alg[i] = nums[i] + max {alg[i+j] for j=[1, k]}

However, the complexity is not good. What we need for {alg[i+j] for j=[1, k]} is only the maximum. So we need to keep tracking the sliding window maximum. An O(nlogn) solution is intuitive.

alg[i] = nums[i] + pq.max
// note that we need to invalidate pq when the index_of_max > i + k

It is still not enough. Monotonic Queue works perfect for Sliding Window Maximum.

alg[i] = nums[i] + max(0, alg[mq.sliding_window_max()])

LC 1340. Jump Game V

It is not difficult to get the following O(n^2) solution.

alg[i] = max {
  1 + alg[k] for k in [i - d, i + d]
}

However, the time complexity could be reduced to O(n). We think backwards. For each index i, it could be reached by indexes that values are larger. We greedily choose the nearest higher since it leaves more indexes for the rest jumps. Monotonic Queues work perfectly for Sliding Window Nearest Higher Number.

alg[i] = 1 + max{
   alg[left_nearest_higher[i]],
   alg[right_nearest_higher[i]]
}