18  DP Idea and Example

Dynamic programming (DP) is a general technique where we define the solution to a problem in terms of smaller subproblems. We’ll start with an example, then describe the general approach.

Objectives: After learning this material, you should be able to:

• Name and explain the components of a dynamic programming (DP) algorithm.
• Solve the longest increasing subsequence problem using DP.

18.1 Longest increasing subsequence

This is the first problem we will solve with dynamic programming. Before defining it, some terminology: Given a list of numbers, also called a sequence, a subsequence is any result of deleting some elements of the list. For example, given the list \((1, 2, 3, 4, 5)\), the list \((1, 3, 5)\) is a subsequence but \((1, 5, 2)\) is not. A list of numbers is (weakly) increasing if each number is at least as large as the previous one.

The longest increasing subsequence (LIS) problem is:

• Input: a nonempty list of integers.
• Output: the length of its longest subsequence that is weakly increasing.

For the previous example, the longest increasing subsequence is the entire thing, \((1,2,3,4,5)\). If the input is \((1,6,5,3,4,8)\), then the longest increasing subsequence is \((1,3,4,8)\) with a length of \(4\) elements.

First, let’s look at the brute-force algorithm. It considers each possible subsequence of the list. Among all the subsequences that are increasing, it takes the longest one.

Exercise 18.1 What is the time complexity of this algorithm? Suppose the input list has length \(n\).

Solution.

We can bound it by \(O(n 2^n)\). To get a subsequence, we pick a subset of the items \(1,\dots,n\). There are \(2^n\) subsets. For each subset, we check whether it’s increasing and how long it is, which takes linear time in the size of the subset. In the worst case, the length of the subset is \(n\), so we get \(O(n 2^n)\).

Brute force is much too slow, so now we’ll solve this problem using dynamic programming. The idea behind the algorithm is to consider all the prefixes of the input list. First, we solve a variant of the LIS problem for the prefix of length one; this is easy. Then we use this to solve it for the prefix of length two. And so on up to the end.

Consider the above example, input \((1,5,6,3,4,8)\). Suppose we’re trying to solve the LIS problem for the prefix \((1,5,6,3,4)\), with the requirement that we must include the final element, \(4\). Well, an increasing subsequence that includes \(4\) can only be one of the following options:

• No prior element – the subsequence starts with \(4\), so its length is just one.
• \(1\) as the prior element. We would take the LIS ending with \(1\), and append \(4\), making it one longer.
• \(3\) as the prior element. We would take the LIS ending with \(3\), and append \(4\), again making it one longer.

The solution for the prefix ending at \(4\) is whichever of these options is the longest, which is of course the last one, giving a LIS of \((1,3,4)\). Now, we’ll use this idea to go through the list and solve the problem up to each element so far, assuming we’ll include that element.

Algorithm 18.1  

longest_increasing_subsequence(A):
   # A is a list of integers of length n
   let L[1] = 1
   for j = 2 to n:
      let L[j] = 1
      for i = 1 to j-1:
         if A[i] <= A[j]:
            set L[j] = max(L[j], L[i] + 1)
   return max(L)

The inner for loop on lines 6-8 implements the logic discussed above: it sets \(L[j]\) to be \(1\) if there are no prior elements weakly smaller, and otherwise \(1\) plus the best of the previous eligible subsequences.

Proposition 18.1 Algorithm 1 correctly solves the Longest Increasing Subsequence problem.

Proof. We prove by induction the following statement: \(L[j]\) is the length of the LIS of the input up to index \(j\) that includes the element at index \(j\). This will prove correctness because we return \(\max_j L[j]\), i.e. the longest increasing subsequence that ends at any location.

Base case: \(L[1] = 1\) is correct, because we can take the first element to be a subsequence of itself, with length one.

Inductive case: Suppose \(L[1], \dots, L[j-1]\) are all correct. Now at index \(j\), one possible subsequence is just the element \(A[j]\) itself, which has length \(1\). The other kind of possibility is a subsequence that starts earlier and ends at \(j\), with the prior index included being \(i\). This can only occur if \(A[i] \leq A[j]\), and if so, its maximum length is \(L[i] + 1\) because we appended the element at index \(j\). The algorithm takes the maximum over these possibilities, so \(L[j]\) is correct.

Now if each \(L[j]\) is correct, then the algorithm is correct because it returns the maximum of \(L[j]\) for all \(j\), one of which must be the LIS of the input.

Proposition 18.2 The running time of Algorithm 1 is \(O(n^2)\) and space use is \(O(n)\).

Proof. Initialization runs in constant time and returning the answer runs in \(O(n)\), finding the maximum element of \(L\).

The outer for loop runs \(n-1\) times, and each iteration, the inner for loop runs at most \(n-1\) times, with constant-time operations. So the running time is \(O(n^2)\).

The space usage is dominated by the array \(L\), which is \(O(n)\).

Exercise 18.2 In Algorithm 1, why would it be wrong to return \(L[n]\), the last entry of our answer array? Give an example input where returning \(L[n]\) would be incorrect and explain how it fails.

Example solution.

\(L[n]\) is the length of the LIS that ends exactly at location \(n\), but the LIS of the entire sequence may end earlier. An example is the input \((1,9,10,5)\). Here the LIS has length \(3\) and is \((1,9,10)\), but \(L[n] = 2\) because the LIS ending at the last element is \((1,2)\).

Exercise 18.3 Simulate Algorithm 1 on input \((5,1,3,2,4,0)\). What is \(L\) and what is the final solution?

Solution

Index	1	2	3	4	5	6
Input	5	1	3	2	4	0
\(L\)	1	1	2	2	3	1

The final solution is \(\max_j L[j] = 3\).

18.1.1 Reconstructing the subsequence itself

Algorithm 1 returns the length of the LIS, but not the subsequence itself. Luckily, we can modify it quite easily to do this as well. The approach is similar to the modification of breadth-first-search and Dijkstra’s algorithm to return the shortest path itself (not just its length). We have to keep track, for each result we got, “how we got there”. The result is Algorithm 2.

Algorithm 18.2  

lis_2(A):
   # A is a list of integers of length n
   let L[1] = 1
   let prev[j] = null for all j   
   for j = 2 to n:
      let L[j] = 1
      for i = 1 to j-1:
         if A[i] <= A[j]:
            set L[j] = max(L[j], L[i] + 1)
            if L[j] == L[i] + 1:  
               set prev[j] = i    
   let j = argmax(L)
   return L[j] and lis_reconstruct(prev, j)  

lis_reconstruct(prev, j):  
   let S = empty list      
   while j is not null:    
      add j to front of S  
      j = prev[j]          
   return S                

Exercise 18.4 Revisiting our example, simulate Algorithm 2 on input \((5,1,3,2,4,0)\). Give \(L\), \(prev\), and the final output.

Solution.

Index	1	2	3	4	5	6
Input	5	1	3	2	4	0
\(L\)	1	1	2	2	3	1
prev	null	null	2	2	3	null

The final solution is \(\max_j L[j] = 3\) and the subsequence \((1,3,4)\). (Another answer is \((1,2,4)\).

18.2 Components of dynamic programming

Now that we’ve seen a dynamic programming algorithm, let’s lay out the components that all DP algorithms have.

Dynamic programming algorithms always can be broken down into these components:

1. Subproblem definition. For example with LIS, subproblem \(j\) was “compute the length of the LIS of the prefix of the input up to \(j\), requiring it to include the final element.” We stored the solutions in an array \(L\).
2. Computing the final answer from the subproblem answers. For LIS, we took the maximum solution to any subproblem, i.e. \(\max_j L[j]\).
3. Recurrence. The recurrence states how to solve any given subproblem. It always has two parts:

• Base case / initialization. The base cases are the ones that don’t rely on other subproblems. For LIS, the base case was a prefix of length \(1\), and we initialized \(L[1] = 1\).
• Inductive case: how to solve a generic subproblem given the solution to “earlier” subproblems. For LIS, we said \(L[j]\) was the maximum of \(1\) and \(1 + L[i]\) over any \(i < j\) where \(A[i] \leq A[j]\).

4. (Optional) reconstructing the object that witnesses the solution. DP algorithms usually return the size or value of some object, for example, the length of the LIS. Then, they can usually be modified in a straightforward, formulaic way to construct that actual object itself, for example, the actual subsequence as we did above. This modification usually proceeds by remembering which choices we made when solving a subproblem, e.g. when setting \(L[j] = L[i] + 1\), remembering which index \(i\) was used.

Every dynamic programming solution (at least in this class) is made up of the above components.

The key question you usually need to answer is: What are the subproblems, and what is the recurrence? Usually, the subproblems can be arranged in an array, since they must be solved in order. Often this array is multidimensional, as we will see. Sometimes the subproblem is essentially the same as the original problem, just on a prefix or subset of the input. But often the subproblem is slightly different, as in the LIS example where the subproblem required the subsequence to include the final element.

Once you define the above elements, the DP algorithm has essentially been defined:

• Create an array to store the subproblem solutions. (Later, this may be a 2d array or more.)
• Initialize the base case(s) of the recurrence.
• Iterate through the subproblems in dependency order and solve using the inductive case of the recurrence.
• Compute the final answer using the subproblem answers.

To reconstruct the witnessing object as well, it can generally be modified by creating a data structure that remembers the choices made, at each subproblem, when solving the recurrence; then backtracking through these choices.

Proofs of correctness. Every DP algorithm is proven correct with the following inductive proof:

1. (Base case) We prove the algorithm initializes the base cases or initial subproblems correctly.
2. (Inductive case) At each step, assuming the previous subproblems were solved correctly, we prove that the next subproblem is solved correctly.
3. By induction, steps (1) and (2) prove that all subproblems are solved correctly.
4. (Returning the final answer) We prove that, if all the subproblems were solved correctly, we return the final answer correctly.

For example, with the Longest Increasing Subsequence problem, the base case was that a prefix of length \(1\) has a LIS of length \(1\). Then, the inductive case was that for each subproblem \(j=2,\dots,n\), assuming that \(L[1],\dots,L[j-1]\) were all correct, the algorithm computes \(L[j]\) correctly (inductive step). Finallly, we argued that if \(L[j]\) is correct for each \(j\), then it is correct to return \(\max_j L[j]\).

Because the proof always follows this template, we will always prove correctness by filling in the above parts: correctness of the recurrence – base case and inductive case – and of returning the final answer. We also need to make sure that we solve the subproblems in dependency order.