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.
\Theta(n^2).
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 order 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 reposition 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 fix the 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.
Time: O(n)
Extra-space: O(n)
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 can an n-inch rod be cut? This must give you the time complexity of a brute-force approach.
O(2^n)
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 are the time and (extra) space complexities of your algorithm?
time: O(2^n)
extra-space: O(n)
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.
The brute-force approach would be to try out all possible options for conversion: for each letter in s_1 decide whether to uppercase it or delete it. Therefore, it gives rise to an exponential-time algorithm. Indeed, the running-time is \Theta(2^n) where n is the maximum length of s_1 and s_2. Since this is a non-polynomial algorithm, we would not code it!
In order to apply the dynamic programming technique, we first solve the smaller subproblems to eventually solve the original problem in a ground-up manner.
For 0\leq i<{\tt len}(s_1) and 0\leq j<{\tt len}(s_2), we define the subproblem as the task of checking if the substring s_1[0:i] can be converted to the substring s_2[0:j]. In the substring notation above, the end indices are inclusive. The solution (True or False) to the subproblem is denoted as {\tt abbvr}(i, j). The idea is to compute and store {\tt abbvr}(i, j) for smaller values of i,j in a matrix. As we increment i and j, the new solutions can then be inferred from the already computed solutions in the matrix. Finally, our solution will be given by {\tt abbvr}({\tt len}(s_1)-1, {\tt len}(s_2)-1), which is the bottom right entry in our solution matrix.
Optimal Substructure: Given that the solution matrix is computed for (i,j) and the entry is True. We use the following observations to fill the entries of the next row and column:
If s_1[i+1] is uppercase and equal to s_2[j+1], then the entry (i+1, j+1) becomes
TrueIf s_1[i+1] is a lowercase letter
equivalent to s_2[j+1] then the entry (i+1, j+1) becomes
TrueOtherwise it can be deleted, then the entry (i+1, j) becomes
True
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.
Longest Common Subsequence
