Dynamic Programming amazing tricks! — Part III.a — All you need about DP optimizations — Knuth Magic!
--
In Part III, I will present some popular DP optimizations. I will explain them with a story as they are hard-to-understand topics. And give an intuition to recognize scenarios where it might be applicable.
Part III will consist of three sub-articles: (a) Knuth optimization (this one), (b) Knapsack on trees, and (c) D&C optimization.
Motivation
This series of guides will be helpful for you if you are:
- preparing coding interviews.
- training for competitive programming.
- just want to learn how to come up with ideas to solve dynamic programming problems.
I will assume that you read the last parts.
My goal in this article is to explain popular “DP optimizations tricks”: advanced artifices that reduce time complexity. I will focus on providing insights so you to recognize DP’s formulas that can be optimized with them.
As I said in past articles, you will only truly understand it once you practice the ideas. So again, I put a homework section with exercises.
Finally, remember the content of this article is more advanced compared to the previous ones, so don’t demotivate if you don’t understand the concepts on the first read.
Knuth’s optimization
Motivational problem: Having N different integers Vᵢ with their frequencies Fᵢ, calculate the cost of the binary search tree with the minimum cost where the cost of a binary tree is calculated by the frequencies with the formula:
For example, if Vᵢ = [2, 1, 3] and the respective Fᵢ = [1, 100, 1] the answer is 105. The best solution will use 1 as the root, even when the resulting trees are imbalanced because it has a huge frequency compared with the others.
Observe that for any solution (any search tree) the Inorder traversal of the Vᵢ will be always the same: the Vᵢ sorted. We can construct the tree from the Inorder of the nodes: as all the solutions have the same in-order we are considering all of them. So we will sort the input by Vᵢ.
The first step then is to choose which node will be the root. Notice that once we sort, if Vᵣ is the root, then Vᵢ < Vᵣ < Vⱼ for all i < r < j so the Vᵢ ‘s will be placed on the left subtree and the Vⱼ ‘s will be placed on the right subtree. Then we can apply the algorithm recursively to both remaining subsets of nodes obtaining respective costs C₀ and C₁. The optimal tree that has Vᵣ as the root will have these optimal subtrees as respective left and right subtrees. For calculating the cost of this optimal tree we have to take into account the cost added by the root (Fᵣ) and the fact that the nodes from the subtrees will have in the resulting tree +1 of depth (so will have to add the sum of Fᵢ and Fⱼ to the cost). In conclusion, the cost will be:
We can notice that the successive recursive calls can be computed by following the same logic of iterating through all the possible choices of the root, recursively calculating the cost of the left and right tree costs, using them to calculate the cost of the optimal subtree that use the chosen root and minimizing the cost for all the choices of the root. Essentially:
As we explained in the DP Part I the total complexity is the product of the number of states and the complexity of the function (assuming the recursive calls are already calculated). Here we have O(N²) states and f does a loop of O(N). So the total complexity of the DP is O(N³).
We will see an optimization that easily converts it to O(N²). First, let’s do some observations. Let’s define K(i,j) as the minimum position k for which the minimization from f(i,j) finds an optimal value. Notice that if we magically know K(i,j) in O(1), we could reduce the complexity to O(N²) so it’s a pretty interesting function. It can be proven that for this particular problem the following condition holds:
- K(i,j) is monotonic in both parameters.
- In terms of our range DP, this means that if we observe the optimal root k for a subrange (i,j) and compare it with the optimal choice for a subrange (i-1, j) -the one that includes an element more to the left- the optimal root in this last subrange is the same or it’s on the left of optimal root from the (i,j) case: if we add elements to the left, the optimal “break” choice for the DP doesn’t move to the right (move left or stays equal).
- Similarly, the first inequality expresses that if we add an element to the right the optimal choice doesn’t move to the left (move right or stay equal).
Even when we can’t calculate magically K in O(1), if we delimit A ≤ K(i,j) ≤ B we can loop k from A to B (instead that doing it from i to j-1). Notice that we delimited K(i,j) by K(i, j-1) and K(i+1, j). Also notice that [i, j-1) and [i+1, j) are smaller subranges (in length) than (i, j]. So we can compute K(i,j) while calculating f and be sure that K(i, j-1) and K(i+1, j) are calculated (for example in a bottom-up implementation) when we calculate K(i,j). So we can use these bounds to delimit the iteration.
Cost Analysis
This magically reduces the complexity to O(N²). Wow! Why? You can find a formal demonstration here (see “Proof of correctness” subsection). But let’s explain with images:
- The iteration cost of f is now: K(i+1, j) — K(i, j-1) + 1. We represent it in a grid and painted K(i+1, j), and K(i, j-1) in green and red respectively (for some arbitrary choice of i,j):
- Painting similarly for every (i,j):
- Notice that all the internal costs get canceled contributing (each) with only a cost of 1. In total, here we get O(N²).
- The costs from the right border didn’t cancel with anything, contributing (each) with O(N). In total, we get O(N²) from there.
So, the total cost is O(N²). This is an example of amortized cost analysis.
General Case
Notice that the exposed argument applied for any DP of the form:
If the optimal position K(i,j) of the minimization for a range (i,j) satisfy:
For deciding if it holds is good to think: How do behave the optimal “break” of a range (i,j) if we add an element to the right or left? Remember that the monotonic condition is the same as the optimal stay equal or moves left when we add elements to the left (and respectively the same for the right).
Sometimes is easier to check that the cost function C(i,j) satisfies the conditions (for a ≤ b ≤ c ≤ d):
These conditions guarantee that Knuth’s condition holds.
Recognizing when it might apply
Always we get a DP on the range with minimization (or maximization) in O(N³) but we need a better complexity of O(N²) we must consider an instance of the problem for the subrange (i,j) and ask ourselves how the optimal “break” behaves regarding we add an element to the left or right. Does it always stay or move accordingly? If our intuition says “Yes” maybe it deserves to add the optimization and send it to the judge! (you don’t need to demonstrate the correctness for competitive programming!).
Generic implementation
Implementing it is an easy and tiny modification to the DP.
If we want, we can easily implement Knuth Optimization also for a Top-Down range DP:
Homework
- Optimal Binary Search Tree (UVa 10304).
- Cutting Sticks (UVa 10003).
- CP Algorithms (see “Practice Problems” subsection).
About Me
If you liked this post / my style follow me.
I will try to keep on posting regularly about SE, Web, and ML always with these objectives in mind:
- keep it short
- being meaningful
- explain with examples
