PDF of Eric’s handwritten notes are here.

**Dynamic Programming**

Here we study dynamic programming. We’ll discuss a few examples so you see the methodology for designing a dynamic programming algorithm.

**Problem 1: Longest Increasing Subsequence (LIS)**

Input: numbers .

Output: The length of the LIS.

Example: If the input is , then the longest increasing subsequence is .

The first step in designing a dynamic programming algorithm is to define the subproblem. We then attempt to define a recursive solution to the subproblem in terms of smaller subproblems. If we are unable to do so then we go back and modify our definition of the subproblems, hopefully armed with some greater insight into the recursive nature of the problem.

Our first attempt at defining a subproblem is typically to consider exactly the same problem formulation on a prefix of the input. Thus we consider the following.

**Attempt 1:**

**Subproblem definition**: Let length of LIS in .

**Recursive step**: We want to express in terms of . But given how do we know if we can append onto the optimal subsequence for ? We need to know what is the last number in the solution for . And if cannot be added on we may want to extend a suboptimal solution as this suboptimal solution may eventually surpass . Thus we modify the subproblem definition to keep track of the last number in the subsequence.

**Attempt 2:**

**Subproblem definition**: Let length of LIS in which includes .

**Recursive step**: .

**Output**: Return .

**Pseudocode**:

- for
- for
- if then

- for
- for
- if then

- Return .

**Running time**: . We have subproblems, and each subproblem depends on all the subproblems before it.

Note: Consider the definition of the subproblem. There is a crucial property here that we are enforcing to include element ; this allows us to know when we can “extend” this subproblem. Since we know the last element of the subsequence is , we can add any element with value .

**Problem 2: Longest Common Subsequence**

Given two strings and , find the length of the longest string that is a subsequence of both and .

**Example**

It is easy to verify that the length of the longest common subsequence is 4 and the string is .

**Dynamic Programming Solution**

As in the previous example, we will be using dynamic programming to solve this problem.

The first step is to define the subproblem. As before, let us attempt to use prefixes.

For , , let:

denote length of the longest common subsequence for the strings and .

Next, let us proceed with the base cases:

Now, let us figure out the recurrence:

If characters and are different, then we may choose to exclude or . If we exclude , we would be left with the strings and . What would be the length of the LCS for the strings and ? This is precisely the definition of . Similarly, if we leave out , the length LCS of the strings and will be . So the length of the LCS of the strings and will be the larger of the two options. Therefore we have the following recurrence in the case that the last characters are different.

If then:

If characters and match, then we may choose to match with , and would be left with the strings and . In this case, the length of the LCS will be . We may also choose to exclude or as before. So the length of the LCS of the strings and will be the larger of the three options.

If then:

(In fact one can argue that in this case, since we might as well match and .)

Let us summarize the algorithm in the form of pseudocode:

- for to
- for to
- for to
- for to
- if :
- if :

- for to
- return

Clearly, the running time of the algorithm is .

Practice exercise: How do you find the LCS (not just the length, but output a string)?

Practice exercise: Longest common substring (instead of subsequence).