Dynamic Programming

Introduction

Dynamic programming is closely related to divide & conquer and has far-ranging applications. They share the same idea of dividing a bigger and complicated question into smaller and easy-to-solve sub-problems of the same type. So both of them are based on recursion.

The difference: In divide & conquer, sub-problems share the same type with the original problem, but every sub-problem is not totally the same. (For example, when doing merge sort, we split the input array into left-half and right-half and sort them individually. The subproblem, sorting the left-half and right-half array, is the same with the original problem; the only difference is that the input array’s length becomes halved. But sorting the left-half and sorting the right-half is not usually the same problem.) In dynamic programming, we will have exactly the same sub-problem occur multiple times. To avoid solving the same sub-problem more than once, we can memorize each sub-problem result, and before solving one, we check if the same problem has been solved before. Thus every distinct sub-problem will be solved at most once.

To solve a problem using a dynamic programming approach, we normally need a 1-d, 2-d, or more complex array. We also have to figure out what’s the meaning of each block in that array and how later blocks connect to the previous one.

Comparing to divide & conquer, dynamic programming might have less time complexity but usually need more additional space because of memorization.

Fibonacci numbers

Computing the Fibonacci numbers is a classic and straightforward problem, where dynamic programming can be applied.

Referring to the wiki page, the nth Fibonacci number Fib(n) is the nth number in the Fibonacci series. Its definition:

and for n > 1:

The beginning of Fibonacci series:

Our problem is to compute the nth Fibonacci number:

Computing nth Fibonacci number
input: a integer N>=0
output: the N th Fibonacci number

Imagine we’d like to compute Fib(5). By definition, Fib(5) = Fib(4) + Fib(3) and the problem becomes computing Fib(4) and Fib(3). We can continue doing this until getting Fib(0) and Fib(1):

                           fib(5)   
                     /                \
               fib(4)                  fib(3)   
             /        \              /       \ 
         fib(3)      fib(2)       fib(2)     fib(1)
       /     \       /    \        /    \
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
 /      \
fib(1) fib(0)

The native method to compute this will be computing all nodes on the above graph, a simple divide & conquer algorithm. In this case, the number of node we need to compute is O(2^logn).

However, you might notice that some sub-problem is exactly the same. For example, Fib(3) appears 2 times, Fib(2) appears 3 times and Fib(1) appears 5 times. If we can memorize distinct nodes with their result, we only need to compute O(n) nodes. Also notice that the extra space needed here is also O(n).

                           fib(5)   
                     /                \
               fib(4)                  fib(3)   
             /        \            
         fib(3)      fib(2)       
       /     \          
  fib(2)   fib(1)   
 /      \
fib(1) fib(0)

The pseudocode of Fib(n):

Algorithm computing nth Fibonacci number

int Fib(n) {
  int fibSeries[] <-- initializing an array of size n + 2 
  fibSeries[0] = 0
  fibSeries[1] = 1
  for i from 2 to n+1
    fibSeries[i] = fibSeries[i - 1] + fibSeries[i - 2]
  return fibSeries[n+1]
}

One technique often used in dynamic programming is building a 1-d, 2-d, or more complex array to store the result of every distinct sub-problem; arrange the sub-problems in order from simpler to complicated, and solve them(fill the array) in that order.

Longest Increasing Subsequence

Longest Increasing Subsequence
input: an array of integer
output: the longest increasing subsequence

Subsequences: From a sequence, any of the element but in sequence.

For example, consider sequence 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

The longest increasing subsequence is 0, 2, 6, 9, 11, 15

Usually, a useful technique to help us think about dynamic programming problems is considering the last element.

Here, we can fix the last element in the sequence, 15, and we have two choices: either 15 is in our longest increasing subsequence, or it is not. If we decide to exclude 15, the question becomes to find the longest increasing subsequence from remaining elements. If we include 15, since it is the last element, the question becomes to find the longest increasing subsequence from remaining elements with the last element less than 15. So fixing one end (the last of subsequence) seems to work.

Let P(n): the longest increasing subsequence of array arr[1...n] end with arr[n]
P(n) = max(P(1), ..., P(i-1)) + arr[n], for all  1<=i<=n-1 and arr[i] < arr[n]
LIS(arr[1...n]) = max(P(1), ..., P(n))

*LIS stands for the longest increasing subsequence

Now, it looks similar to Fibonacci number since the later value depends on previous ones: to compute P(2), we need P(1), to compute P(3), we need P(2) and P(1), to compute P(n), we need P(1), …, P(n-1). Since the same subproblem raises over and over again, memorization is a plus.

So we will have an array p[1…n] where p[i] stores the LIS end with arr[i]. Since the later value depends on earlier values, we can fill the array from the beginning.

Algorithm find LIS
int LIS(arr[1...n]) {
  p[1...n] <-- initialize empty array
  p[1] = 1 // base case
  for i from 2 to n
    p[i] = max(p[j]) + 1 for j from 1 to i-1 and arr[j] < arr[i]
  return max(p) // return the largest element in p[1...n]
}

We are using two loops here, so the time complexity will be O(n^2). Also, O(n) space is used to store array p[1…n].

Have fun!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s