1
$\begingroup$

I'm looking at the following explanation of monotonic queues and their applications in problem solving.

Monotonic Queue Summary

I have a reasonable understanding of this data structure and the problems described in the post. However, i'm struggling with the following "recurrence relation"

Any DP problem where A[i] = min(A[j:k]) + C where j < k <= i

I don't completely understand this formula. It looks like a recurrence relation but seems to to be in reference to the underlying array. I can't seem to see if the previous array range (j to k) is referring to a portion of the array or a portion of previously solved sub-problems.

I'm not sure what the base case is and it seems like the answer is the minimum value in this array range plus some constant. I don't see how this solves the problems above.

Am I looking for too much precision in this statement or am I missing something?

The following seems more intuitive

Any DP problem where DP[i] = smallest(prefix_sums[j:k]) where j < k <= i and prefix_sums[k] - prefix_sums[j] >= K
$\endgroup$

1 Answer 1

2
$\begingroup$

It is no wonder that you are confused.

One characteristic of DP problem is the recurrence relation that combines solutions to subproblems to a solution to larger subproblems. That article presents the following general "recurrence relation".

Any DP problem where A[i] = min(A[j:k]) + C where j < k <= i

However, because the same A appears on both sides of the equation, that "recurrence relation" cannot be specialized/instantiated as the recurrence relation of any problem listed in that article.

Instead of "DP problem", this kind of problem should better called "sliding window problem", or "SW problem". Basically, a first-in-first-out queue sliding over the given array are used to track the useful entries. We could argue that "SW problem" is a special kind of "DP problem", where the overlapping subproblems are to fill those sliding windows. Each sliding window will lead easily to a solution for the original problem at one end of a window. Or, if you prefer a visual identification of the "DP problem" as "table-driven bottom-up memoization", an "SW problem" is supposed to be solved by tracking useful data in a table moving across the given array.

An "SW problem" does not have the usual form of recurrence relation, as can be checked against all problems listed in that article. Instead of Any DP problem where A[i] = min(A[j:k]) + C where j < k <= i, it should have been something like Any problem to find M[i] where M[i] is defined as something like min(A[j:k]) where j < k <= i given array A.

This technique, "sliding window" is indeed very powerful and easy to use. Except the glaring lapses mentioned above, that article is pretty nice. I encourage you to read the full article, ignoring that summary statement or using my replacement above.

$\endgroup$
3
  • $\begingroup$ Thank you, that makes a lot of sense. One more quick question in regards to your replacement. Is C a general constant used to denote some arbitrary window length? IE j to K + C length, or is it the minimum value of the range + C. The former seems the case to me? $\endgroup$
    – DMW
    Apr 28, 2020 at 16:38
  • $\begingroup$ C could just be a constant. More generally, I would interpret + C to indicate M[i] might not be min(A[j:k]) exactly. Here is another version of the summary, A problem to find M[i] that is (essentially) defined as the minimum of some function on elements of A with indices that are at most i given array A. $\endgroup$
    – John L.
    Apr 28, 2020 at 16:56
  • $\begingroup$ Hmm, it is not easy to construct a summary that is suitable for all levels of understanding and the many different variations of the problems. It might be better to read the examples. Then come up with your own mental image and your own summary. Or, similar to "DP problem", this kind of problems can be called "SW problem" for "sliding window problem", where FIFO queues sliding over the given array are used to define and solve the problem. $\endgroup$
    – John L.
    Apr 28, 2020 at 17:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.