Monotonic queues recurrence relation

Question

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

Answer 1

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.