9 Dynamic Programming
“Either mathematics is too big for the human mind or the human mind is more than a machine.”
– Kurt Godël
In this chapter, we cover dynamic programming, an important technique typically applied to optimization problems that exhibit a special property, known as optimal substructure. The key idea behind this property is: the optimal solution to the original problem contains in it the optimal solutions to some of the subproblems. The optimal substructure is a good clue that dynamic programming might apply. Then, the solutions to subproblems are tabulated in order to reconstruct the solution to the original problem.
In summary, dynamic programming is a combination of the following two components:
Optimal Substructure: The optimal solution to the original problem can be expressed in terms of the optimal solutions to some of the subproblems. The structure is usually embodied in a mathematical formula, which is usually used during implementation.
Ground-up Implementation: Starting from the smallest subproblem, we gradually solve (and record the solutions of) subproblems larger in size—eventually solving the original problem.
9.1 Motivating Examples
Let us take a few examples where dynamic programming can shine, reducing the time complexity substantially as compared to the brute-force alternatives.
Maximum Sum Subarray (MSS)
For an array A[0:n-1] of length n, a subarray A[i:j] (where 0\leq i\leq j\leq n-1) is a non-empty, contiguous portion of A—completely determined by the start index i and (inclusive) end index j.
The Maximum Sum Subarray (MSS) problem finds the largest sum across all subarrays of a numeric array A.
Example: If A=[-2, 3, 1, -1, 1, 4, -5], then {\tt MSS}(A)=5 obtained from the subarray A[4:5].
Exercise 9.1 For an array A of length n, how many distinct subarrays can be formed? Also, present your answer in big-O notation.
The Brute-force Cubic
There are \Theta(n^2) subarrays of A[1:n]. For each subarray, computing the sum takes O(n) time. So, the brute-force algorithm must find the sums of the subarrays in other to compare them, giving an O(n^3)-time algorithm.
We improve the running time by using dynamic programming.
The Clever Quadratic
As we stressed already, dynamic programming is a euphemism for organized tabulation. We modify the above code to achieve O(n^2) complexity using dynamic programming, but quite naively.
In Algorithm 1, we store the value of sum, instead of recomputing it for each j. For any given i (the outer for-loop), we note that
sum(A[i:j]) = sum(A[i:j-1]) + A[j].
\tag{9.1} For a fixed i, we could compute sum(A[i:j]) in constant time using (Equation 9.1), instead of recomputing it using the inner-most for-loop line #6-9. This observation saves us a for-loop, hence providing a O(n^2) algorithm:
The Best Linear
What’s next? We now wonder if dynamic programming can give rise to a linear-time algorithm. Well, the answer is yes!
Note that MSS is a maximization problem: {\tt MSS}(A) = \max\limits_{0\leq i\leq j\leq n-1}{\tt SUM}(A[i:j]). In order to find the global maximum, our algorithm exhaustively sifts through all subarrays of the input array. We first fix the start index i, then repositioned the endpoint j from i to n-1. When done exploring all subarrays with start index i, we then fix the start index at i+1 and so on.
Our first step is to rewrite the optimization problem as: {\tt MSS}(A) = \max\limits_{0\leq j\leq n-1}\left(\max\limits_{0\leq i\leq j}{\tt SUM}(A[i:j])\right). \tag{9.2} To see the new perspective, we first the fix end index 0\leq j\leq n-1 and consider all subarrays A[i:j] (for 0\leq i\leq j) that end at j. We then find the maximum sum across these j’s many subarrays that end at j; this is the term in the brackets in Equation 9.2. Call the solution {\tt MSS\_LOC}(j). This can be thought of as a local maximum for j. Since the global maximum is the maximum of all these local maxima, we can now rewrite the MSS problem as: {\tt MSS}(A) = \max\limits_{0\leq j\leq n-1}{\tt MSS\_LOC}(j).
Note that the brute-force time-complexity of {\tt MSS\_LOC}(j) (finding each local max) is O(j). As a result, finding the maximum of {\tt MSS\_LOC}(j) over all 0\leq j\leq n-1 still becomes O(n^2)—unless we do something ingenious. Tabulation would do the trick!
The idea is to use dynamic programming to compute {\tt MSS\_LOC}(j). Instead of recomputing {\tt MSS\_LOC}(j) for each j, we rather infer {\tt MSS\_LOC}(j) (in constant time) from the already stored value of {\tt MSS\_LOC}(j-1). In other words, we try to find an optimal substructure for the problem.
Keep in mind that finding an optimal substructure is not always easy. It takes a bit of practice and mathematical reasoning. The trick is to start with an optimal solution of the main problem, then use mathematical reasoning to see how the solution can be expressed in terms of the solutions of subproblems. The process usually gives rise to a mathematical formula.
We make the following observation: {\tt MSS\_LOC}(j) = \max\left\{ A[j], {\tt MSS\_LOC}(j-1) + A[j]\right\}. Hence, listing all the local max {\tt MSS\_LOC}(j) takes O(n)-time, so does finding the maximum of them. Here is a pseudocode:
Exercise 9.2 Describe the time and (extra) space complexities Algorithm 3.
Exercise 9.3 Design an algorithm for Algorithm 3 to reduce the extra-space complexity to O(1). Implement it in Python.
Rod-cutting Problem
Given a rod of length n, and a table of prices p_i for i=1, 2, \ldots, n, determine the maximum revenue r_n obtainable by cutting up the rod and selling the pieces. If the price p_n for a rod of length n is large enough, an optimal solution might require no cutting at all. An example price table is shown below:
| length i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| price p_i | 1 | 5 | 8 | 9 | 10 | 17 | 17 | 20 |
Example: Let us take a 4-inch rod, ie., n=4. We show the possible cuts and the corresponding revenues:
4=4 (no cut): revenue 9
4=1+3: revenue 1+8=9
4=2+2: revenue 5+5=\textcolor{red}{10}
4=3+1: revenue 8+1=9
4=1+1+2: revenue 1+1+5=7
4=1+2+1: revenue 1+5+1=7
4=2+1+1: revenue 5+1+1=7
4=1+1+1+1: revenue 1+1+1+1=4
So, the optimal revenue is 10, obtained from cutting the rod in half.
Exercise 9.4 How many ways an n-inch rod can be cut? This must give you the time complexity of a brute-force approach.
We use dynamic programming to reduce the time complexity significantly. Without any coding, we can very easily tabulate the optimal revenues r_n for small enough rod length n.
r_1=1 from solution 1=1 (no cut)
r_2=5 from solution 2=2 (no cut)
r_3=8 from solution 3=3 (no cut)
r_4=10 from solution 4=2+2
r_5=13 from solution 5=2+3
More generally, the optimal substructure is r_n = \max\{p_n, r_1 + r_{n-1}, r_2 + r_{n-2}, \ldots, r_{n-1} + r_1\}. A simpler way to write the optimal revenue is: r_n = \max_{1\leq i \leq n}(p_i + r_{n-i}).
Exercise 9.5 Design an algorithm to implement the dynamic programming approach to the rod-cutting problem.
Exercise 9.6 What is the time and (extra) space complexities of your algorithm?
9.2 Exercises
It’s All About Profit
Exercise 9.7 Let the array A[1:n] store the stock returns; the ith element is the return on day i. Design an algorithm to find the maximum profit by buying and selling stocks. Here are the requirements:
Time: O(n)
Extra-space: O(1)
You cannot make more than one transaction
Let {\tt BUY}(j) return the most profitable buying price when sold on day j. {\tt BUY}(j) = \min\left\{ A[j], {\tt BUY}(j-1)\right\}.
Abbreviation
Given two strings s_1 and s_2, with s_1 containing uppercase and lowercase letters and s_2 containing only uppercase letters. Check if s_1 can be converted to s_2 by applying only the following operations:
uppercase any number of letters in s_1.
delete any number of lowercase letters from s_1.
Example 1: Let s_1=AbcDE and s_2=ABDE. It is possible to convert: uppercase the letter ‘b’ and delete the letter ‘c’.
Example 2: Let s_1=AbcDE and s_2=AFDE. It is not possible to convert since adding a letter (‘F’ in this case) to s_1 is not allowed.
Exercise 9.8 Design an algorithm to return a boolean indicating whether s_1 can be converted to s_2.
Change-Making Problem
Given a set of n distinct denominations D=[w_1,w_2,\ldots,w_n] of coins, arranged in increasing order. Given an amount W (a positive integer), find the minimum number of coins to produce change. You may assume that you have an infinite supply of coins.
Example 1: Take A=[1, 2, 5] and W=10. Here are some possible choices for X:
10=10\times1 (10 coins)
10=1\times1+2\times2+1\times5 (4 coins)
10=2\times5 (2 coins)
…
The optimal solution is option 3 above using only 2 coins.
Exercise 9.9 Given denominations D and amount W, design an algorithm to return the minimum number of coins to make the change, or ‘\infty’ if there is no way to make a change.
Candies
Your niece is going to visit the houses on your street on Halloween night. Given the number of candies each house has, your goal is to help your niece get the maximum number of candies. The only constraint here is your niece cannot visit two consecutive houses.
Exercise 9.10 Given the number of candies each house has, design an algorithm to return the maximum number of candies your niece can get.
