Dynamic Programming

Summary

How can we store previous subproblems and use that to quickly solve larger problems? This is particularly useful when naive solutions include recomputing some problems. This technique typically involves defining the subproblem in words, then defining a recurrenc relation.

Contents

• Fibonacci Numbers
  • Recursive Algorithm
  • Dynamic Algorithm
• Steps to Solve DP problems
• Largest Increasing Subsequence (LIS)
  • DP Solution
• Longest Common Subsequence (LCS)
  • Attempt 1
  • Attempt 2

Fibonacci Numbers

$$F_n = \begin{cases} 0 & n = 0 \1 & n = 1 \F_{n-1} + F_{n-2} & n > 1\end{cases}$$

Recursive Algorithm

Fib1(n):
  if n == 0:
    return 0
  if n == 1:
    return 1
  return Fib1(n-1) + Fib1(n-2)

Runtime:

$T(n) \le O(1) + T(n-1) + T(n-2)$

Runtime scales with the Fib numbers ($T(n) \ge F_n$) which is exponential.

This is becase we are computing some solutions multiple times:

Dynamic Algorithm

Fib2(n):
  F[0] = 0
  F[1] = 1
  for i in range(2,n):
    F[i] = F[i-1] + F[i-2]
  return F[n]

Runtime is O(n)

Steps to Solve DP problems

• Define subproblem in words
  • F[i] = ith Fibonacci number
• State a recursive relation
  • express F[i] in terms of F[1],…,F[i-1]
  • F[i] = F[i-1] + F[i-2]

If the definition is not possible, you can strengthen it and prove the stronger version.

Largest Increasing Subsequence (LIS)

Input: $n \text{ numbers } a_1, a_2, \ldots, a_n$

Goal: find length of LIS

substring
Set of consecutive elements

subsequence
Subset of elements in order (can skip)

Longest Increasing Subsequences is:

DP Solution

Let $L(i) = \text{ length of LIS on } a_1, a_2, \ldots, a_i \text{ and includes } a_i$

$L(i) = 1 + \max_j \lbrace L(j) : a_j < a_i &amp; j < i \rbrace$

LIS(A):
  for i in range(0,n):
    L[i] = 1
    for j in range(0,i):
      if A[j] < A[i] & L[i] < 1 + L[j]:
        L[i] = L[j] + 1

  max = 0
  for i in range(1,n):
    if L[i] > L[max]:
      max = i

  return L[max]

Running time is $O\left(n^2\right)$

Longest Common Subsequence (LCS)

Input: 2 Strings

Goal: Find the length of the longest string which is a subsequence of both X and Y

Attempt 1

$\text{For } i \text{ where } 0 \le i \le n$

$\text{let } L(i) = \text{ length of LCS in } x_1, \ldots, x_i \text{ and } y_1, \ldots, y_i$

When $x_i = y_i, L(i) = 1 + L(i-1)$

When $x_i \neq y_i$, we can’t know what previous sequence it was matched on becuase X and Y have different lengths.

We need to store two parameters, one for the length in X, and another for Y

Attempt 2

$\text{For } i &amp; j \text{ where } 0 \le i \le n &amp; 0 \le j \le n$

$\text{let } L(i,j) = \text{ length of LCS in } x_1, \ldots, x_i \text{ and } y_1, \ldots, y_j$

Recurrence

$L(i,j) = \begin{cases} 0 & \text{if } i = 0 \ 0 & \text{if } j = 0 \ \max\lbrace L(i-1,j),L(i,j-1) \rbrace & \text{if } i &amp; j > 0 , &amp; x_i \neq y_j \ 1 + L(i-1,j-1) & \text{if } i &amp; j > 0 , &amp; x_i = y_j \end{cases}$

Or more simply, for $i, j > 0$

$L(i,j) = \begin{cases} \max\lbrace L(i-1,j),L(i,j-1) \rbrace & \text{if } x_i \neq y_j \ 1 + L(i-1,j-1) & \text{if } x_i = y_j \end{cases}$

LCS(X,Y):
  for i in range(0,n):
    L[i][0] = 0
  for j in range(0,n):
    L[0][j] = 0

  for i in range(1,n):
    for j in range(1,n):
      if X[i] == Y[j]:
        L[i][j] = 1 + L[i-1][j-1]
      else:
        L[i][j] = max(L[i][j-1], L[i-1][j])

  return L[n][n]