I'm looking at the following explanation of monotonic queues and their applications in problem solving.
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