DP: LIS, LCS

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: $n$ numbers $a_1, \ldots, a_n$ .

Output: The length of the LIS.

Example: If the input is $7,11,-5,-2,15,1,16,6,7,11,8,9,0$ , then the longest increasing subsequence is $-5,-2,1,6,7,8,9$ .

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 $T(i)=$ length of LIS in $a_1, \ldots, a_i$ .

Recursive step: We want to express $T(i)$ in terms of $T(1),\dots,T(i-1)$ . But given $T(i-1)$ how do we know if we can append $a_i$ onto the optimal subsequence for $a_1,\dots,a_{i-1}$ ? We need to know what is the last number in the solution for $T(i-1)$ . And if $a_i$ cannot be added on we may want to extend a suboptimal solution as this suboptimal solution may eventually surpass $T(i)$ . Thus we modify the subproblem definition to keep track of the last number in the subsequence.

Attempt 2:

Subproblem definition: Let $T(i)=$ length of LIS in $a_1, \ldots, a_i$ which includes $a_i$ .

Recursive step: $T(i) = 1 + \max_{j} \{ T(j) : 1 \le j < i \text{ and } a_j < a_i\}$ .

Output: Return $\max_i T(i)$ .

Pseudocode:

$LIS(a_1, \ldots, a_n)$

for
- $T(i) = 1$
- for
  - if $a_j < a_i$ then $T(i) = \max\{T(i),1+T(j)\}$
$max = 1$
for
- if $T(i) > T(max)$ then $max = i$
Return $T(max)$ .

Running time: $O(n^2)$ . We have $n$ 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 $T(i)$ to include element $a_i$ ; this allows us to know when we can “extend” this subproblem. Since we know the last element of the subsequence is $a_i$ , we can add any element with value $>a_i$ .

Problem 2: Longest Common Subsequence

Given two strings $X = x_1 x_2 \dots x_n$ and $Y = y_1 y_2 \dots y_m$ , find the length of the longest string that is a subsequence of both $X$ and $Y$ .

Example

$X = BCDBCDA$
$Y = ABECBA$

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

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 $0 \le i \le n$ , $0 \le j \le m$ , let:
$L(i,j)$ denote length of the longest common subsequence for the strings $x_1, \dots, x_i$ and $y_1, \dots, y_j$ .

Next, let us proceed with the base cases:

$L(i,0) = 0, 0 \le i \le n$
$L(0,j) = 0, 0 \le j \le m$

Now, let us figure out the recurrence:

If characters $x_i$ and $y_j$ are different, then we may choose to exclude $x_i$ or $y_j$ . If we exclude $x_i$ , we would be left with the strings $x_1 x_2 \dots x_{i-1}$ and $y_1 y_2 \dots y_j$ . What would be the length of the LCS for the strings $x_1 x_2 \dots x_{i-1}$ and $y_1 y_2 \dots y_j$ ? This is precisely the definition of $L(i-1, j)$ . Similarly, if we leave out $y_j$ , the length LCS of the strings $x_1 x_2 \dots x_i$ and $y_1 y_2 \dots y_{j-1}$ will be $L(i,j-1)$ . So the length of the LCS of the strings $x_1 x_2 \dots x_i$ and $y_1 y_2 \dots y_j$ will be the larger of the two options. Therefore we have the following recurrence in the case that the last characters are different.

If $x_i \ne y_j$ then:
$L(i,j) = max \{L(i-1,j), L(i,j-1)\}$

If characters $x_i$ and $y_j$ match, then we may choose to match $x_i$ with $y_j$ , and would be left with the strings $x_1 x_2 \dots x_{i-1}$ and $y_1 y_2 \dots y_{j-1}$ . In this case, the length of the LCS will be $1 + L(i-1,j-1)$ . We may also choose to exclude $x_i$ or $y_j$ as before. So the length of the LCS of the strings $x_1 x_2 \dots x_i$ and $y_1 y_2 \dots y_j$ will be the larger of the three options.

If $x_i = y_j$ then:
$L(i,j) = max\{1 + L(i-1,j-1), L(i-1,j), L(i, j-1)\}$
(In fact one can argue that in this case, $L(i,j) = 1 +L(i-1,j-1)$ since we might as well match $x_i$ and $y_j$ .)

Let us summarize the algorithm in the form of pseudocode:

$LCS(X,Y)$

for $i=0$ to $n: L(i,0) = 0$
for $j=0$ to $m: L(0,j) = 0$
for to
- for to
  - if $x_i = y_j$ : $L(i,j) = max\{1 + L(i-1, j-1), L(i-1,j), L(i,j-1)\}$
  - if $x_i \ne y_j$ : $L(i,j) = max \{L(i-1,j), L(i,j-1)\}$
return $L(n,m)$