Last updated on: 10 November 2008 06:01:26 PM

1. Introduction to Dynamic Programming
2. Matrix Chain Multiplication (MCM)
3. Longest Common Subsequence (LCS)
4. Edit Distance
5. Longest Inc/Dec-reasing Subsequence (LIS/LDS)
6. Zero-One Knapsack
7. Counting Change
8. Maximum Interval Sum
9. Other Dynamic Programming Algorithms

1. Introduction to Dynamic Programming

Dynamic Programming (shortened as DP) is a programming technique that can dramatically reduces the runtime of some algorithms (but not all problem has DP characteristics) from exponential to polynomial. Many (and still increasing) real world problems only solvable within reasonable time using DP.

To be able to use DP, the original problem must have:
1. Optimal sub-structure property:
    optimal solution to the problem contains within it optimal solutions to sub-problems
2. Overlapping sub-problems property
    we accidentally recalculate the same problem twice or more.

There are 2 types of DP: We can either build up solutions of sub-problems from small to large (bottom up) or we can save results of solutions of sub-problems in a table (top down + memoization).

Let's start with a sample of Dynamic Programming (DP) technique. We will examine the simplest form of overlapping sub-problems. Remember Fibonacci? A popular problem which creates a lot of redundancy if you use standard recursion f_n = f_n-1 + f_n-2.

Top-down Fibonacci DP solution will record the each Fibonacci calculation in a table so it won't have to re-compute the value again when you need it, a simple table-lookup is enough (memoization), whereas Bottom-up DP solution will build the solution from smaller numbers.

Now let's see the comparison between Non-DP solution versus DP solution (both bottom-up and top-down), given in the C source code below, along with the appropriate comments.

2. Matrix Chain Multiplication (MCM)

Let's start by analyzing the cost of multiplying 2 matrices:

Matrix-Multiply(A,B):
  if columns[A] != columns[B] then
    error "incompatible dimensions"
  else
    for i = 1 to rows[A] do
      for j = 1 to columns[B] do
        C[i,j]=0
        for k = 1 to columns[A] do
          C[i,j] = C[i,j] + A[i,k] * B[k,j]
  return C

Time complexity = O(pqr) where |A|=p x q and |B| = q x r

a1,1 a1,2 a1,3   *   b1,1  =  c1,1
a2,1 a2,2 a2,3       b2,1     c2,1
                     b3,1

|A| = 2 * 3, |B| = 3 * 1, therefore to multiply these 2 matrices, we need O(2*3*1)=O(6) scalar multiplication. The result is matrix C with |C| = 2 * 1

Matrix Chain Multiplication Problem

Input: Matrices A₁,A₂,...A_n, each A_i of size P_i-1 x P_i
Output: Fully parenthesized product A₁A₂...A_n that minimizes the number of scalar multiplications

A product of matrices is fully parenthesized if it is either
1. a single matrix
2. the product of 2 fully parenthesized matrix products surrounded by parentheses

Example of MCM problem:
We have 3 matrices and the size of each matrix:
A₁ (10 x 100), A₂ (100 x 5), A₃ (5 x 50)

We can fully parenthesized them in two ways:
1. (A₁ (A₂ A₃)) = 100 x 5 x 50 + 10 * 100 * 50 = 75000
2. ((A₁ A₂) A₃) = 10 x 100 x 5 + 10 x 5 x 50 = 7500 (10 times better)

See how the cost of multiplying these 3 matrices differ significantly. The cost truly depend on the choice of the fully parenthesization of the matrices. However, exhaustively checking all possible parenthesizations take exponential time. (Proof: see CLR chapter 16)

Now let's see how MCM problem can be solved using DP.

Step 1: characterize the optimal sub-structure of this problem.

Let A_i..j (i < j) denote the result of multiplying A_iA_i+1..A_j.
A_i..j can be obtained by splitting it into A_i..k and A_k+1..j and then multiplying the sub-products. There are j-i possible splits (i.e. k=i,...,j-1)

Within the optimal parenthesization of A_i..j :
(a) the parenthesization of A_i..k must be optimal
(b) the parenthesization of A_k+1..j must be optimal

Because if they are not optimal, then there exist other split which is better, and we should choose that split and not this split.

Step 2: Recursive formulation

Need to find A_1..n
Let m[i,j] = minimum number of scalar multiplications needed to compute A_i..j

Since A_i..j can be obtained by breaking it into A_i..k A_k+1..j, we have
m[i,j] = 0, if i=j
        = min i<=k<j { m[i,k]+m[k+1,j]+p_i-1p_kp_j }, if i<j

let s[i,j] be the value k where the optimal split occurs.

Step 3 Computing the Optimal Costs

Matric-Chain-Order(p)
  n = length[p]-1
  for i = 1 to n do
    m[i,i] = 0
  for l = 2 to n do
    for i = 1 to n-l+1 do
      j = i+l-1
      m[i,j] = infinity
      for k = i to j-1 do
        q = m[i,k] + m[k+1,j] + pi-1*pk*pj
        if q < m[i,j] then
          m[i,j] = q
          s[i,j] = k
  return m and s

Step 4: Constructing an Optimal Solution

Print-MCM(s,i,j)
  if i=j then
    print Ai
  else
    print "(" + Print-MCM(s,i,s[i,j]) + "*" + Print-MCM(s,s[i,j]+1,j) + ")"

Note: As any other DP solution, MCM also can be solved using Top Down recursive algorithm using memoization. Sometimes, if you cannot visualize the Bottom Up, approach, just modify your original Top Down recursive solution by including memoization. You'll save a lot of time by avoiding repetitive calculation of sub-problems. Details of MCM problem can be found in CLR chapter 16.

3. Longest Common Subsequence (LCS)

Longest Common Subsequence Problem:

Input: Two sequence
Output: A longest common subsequence of those two sequences, see details below.

A sequence Z  is a subsequence of X <x₁,x₂,...,x_m>, if there exists a strictly increasing sequence <i₁,i₂,...,i_k> of indices of X such that for all j=1,2,..,k, we have x_i=z_j. example: X=<B,C,A,D> and Z=<C,A>.

A sequence Z is called common subsequence of sequence X and Y if Z is subsequence of both X and Y.

longest common subsequence (LCS) is just the longest "common subsequence" of two sequences.

A brute force approach of finding LCS such as enumerating all subsequences and finding the longest common one takes too much time. However, Computer Scientist has found a Dynamic Programming solution for LCS problem. For details, you can refer to Introduction to Algorithm chapter 16 (Dynamic Programming), I will only write the final code here, written in C, ready to use. Note that this code is slightly modified and I use global variables (yes this is not Object Oriented)...

// just copy & paste this code and test it yourself

#include <stdio.h>
#include <string.h>

// change this constant if you want a longer subsequence
#define MAX 100

char X[MAX],Y[MAX];
int i,j,m,n,c[MAX][MAX],b[MAX][MAX];

int LCSlength() {
  m=strlen(X);
  n=strlen(Y);

  for (i=1;i<=m;i++) c[i][0]=0;
  for (j=0;j<=n;j++) c[0][j]=0;

  for (i=1;i<=m;i++)
    for (j=1;j<=n;j++) {
      if (X[i-1]==Y[j-1]) {
        c[i][j]=c[i-1][j-1]+1;
        b[i][j]=1; /* from north west */
      }
      else if (c[i-1][j]>=c[i][j-1]) {
        c[i][j]=c[i-1][j];
        b[i][j]=2; /* from north */
      }
      else {
        c[i][j]=c[i][j-1];
        b[i][j]=3; /* from west */
      }
    }

  return c[m][n];
}

void printLCS(int i,int j) {
  if (i==0 || j==0) return;

  if (b[i][j]==1) {
    printLCS(i-1,j-1);
    printf("%c",X[i-1]);
  }
  else if (b[i][j]==2)
    printLCS(i-1,j);
  else
    printLCS(i,j-1);
}

void main() {
  while (1) {
    gets(X);
    if (feof(stdin)) break; /* press ctrl+z to terminate */
    gets(Y);
    printf("LCS length -> %d\n",LCSlength()); /* count length */
    printLCS(m,n); /* reconstruct LCS */
    printf("\n");
  }
}

Question: Can you list out ALL possible LCS?
Answer: Modify printLCS(), details will be available later.

4. Edit Distance

Edit Distance Problem:

Input: Given two string, Cost for deletion, insertion, and replace
Output: Give the minimum actions needed to transform first string into the second one.

Edit Distance problem is a bit similar to LCS. DP Solution for this problem is very useful in Computational Biology such as for comparing DNA.

Let d(string1,string2) be the distance between these 2 strings.

Recurrence Relation:

d("","") = 0
d(s ,"") = d("", s) = |s| ;; i.e. length of s
d(s1+ch1, s2+ch2)
  = min( d(s1, s2) + if (ch1==ch2) then 0 else 1,
         d(s1+ch1, s2) + 1,
         d(s1, s2+ch2) + 1 )

Follow this link for more details. There is an applet there, you can try the algorithm directly.

DP pseudo code:

A two-dimensional matrix, m[0..|s1|,0..|s2|] is used to hold the edit distance values, such that m[i,j] = d(s1[1..i], s2[1..j]).

m[0][0] = 0;
for (i=1; i<length(s1); i++) m[i][0] = i;
for (j=1; j<length(s2); j++) m[0][j] = j;

for (i=0; i<length(s1); i++)
  for (j=0; j<length(s2); j++) {
    val = (s1[i] == s2[j]) ? 0 : 1;
    m[i][j] = min( m[i-1][j-1] + val,
                   min(m[i-1][j]+1 , m[i][j-1]+1));
  }

To output the trace, use another array to store our action along the way. Trace back these values later.

5. Longest Inc/Dec-reasing Subsequence (LIS/LDS)

Input: Given a sequence
Output: The longest subsequence of the given sequence such that all values in this longest  subsequence is strictly increasing/decreasing.

O(N^2) DP solution for LIS problem (this code check for increasing values):

for i = 1 to total-1
  for j = i+1 to total
    if height[j] > height[i] then
      if length[i] + 1 > length[j] then
        length[j] = length[i] + 1
        predecessor[j] = i

Example:
height sequence: 1,6,2,3,5
length initially: [1,1,1,1,1] - because max length is at least 1 rite...
predecessor initially: [nil,nil,nil,nil,nil] - assume no predecessor so far

After first loop of j:
  length: [1,2,2,2,2], because 6,2,3,5 are all > 1
  predecessor: [nil,1,1,1,1]
After second loop of j: (No change)
  length: [1,2,2,2,2], because 2,3,5 are all < 6
  predecessor: [nil,1,1,1,1]
After third loop:
  length: [1,2,2,3,3], because 3,5 are all > 2
  predecessor: [nil,1,1,3,3]
After fourth loop:
  length: [1,2,2,3,4], because 5 > 3
  predecessor: [nil,1,1,3,4]

We can reconstruct the solution using recursion and predecessor array. =)

However, is O(n^2) is the best algorithm to solve LIS/LDS ?

Fortunately, the answer is no. There exist an O(n log k) algorithm to compute LIS (for LDS, this is just a reversed-LIS), where k is the size of the actual LIS.

This algorithm use some invariant, where for each longest subsequence with length l, it will terminate with value A[l]. (Notice that by maintaining this invariant, array A will be naturally sorted...) Subsequent insertion (you will only do n insertions, one number at one time) will use binary search to find the appropriate position in this sorted array A (guess... only log k right?).

   0  1  2  3  4  5  6  7  8
a    -7,10, 9, 2, 3, 8, 8, 1

A -i  i, i, i, i, i, i, i, i (iteration number, i = infinity)
A -i -7, i, i, i, i, i, i, i (1)
A -i -7,10, i, i, i, i, i, i (2)
A -i -7, 9, i, i, i, i, i, i (3)
A -i -7, 2, i, i, i, i, i, i (4)
A -i -7, 2, 3, i, i, i, i, i (5)
A -i -7, 2, 3, 8, i, i, i, i (6)
A -i -7, 2, 3, 8, i, i, i, i (7)
A -i -7, 1, 3, 8, i, i, i, i (8)

You can see that the length of LIS is 4, which is correct. To reconstruct the LIS, at each step, store the predecessor array as in standard LIS + this time remember the actual values, since array A only store the last element in the subsequence, not the actual values.

6. Zero-One Knapsack

Zero-One Knapsack Problem:
Input: N items, each with various Vi (Value) and Wi (Weight) and max Knapsack size MW.
Output: Maximum value of items that one can carry, if he can either take or not-take a particular item.

Let C[i][w] be the maximum value if the available items are {X₁,X₂,...,X_i} and the knapsack size is w.

Recurrence Relation:

;; if i == 0 or w == 0 (if no item or knapsack full), we can't take anything
C[i][w] = 0

;; if Wi > w (this item too heavy for our knapsack), skip this item
C[i][w] = C[i-1][w];

;; if Wi <= w, take the maximum of "not-take" or "take"
C[i][w] = max(C[i-1][w] , C[i-1][w-Wi]+Vi);

;; The solution can be found in C[N][W];

DP pseudo code:

for (i=0;i<=N ;i++) C[i][0] = 0;
for (w=0;w<=MW;w++) C[0][w] = 0;

for (i=1;i<=N;i++)
  for (w=1;w<=MW;w++) {
    if (Wi[i] > w)
      C[i][w] = C[i-1][w];
    else
      C[i][w] = max(C[i-1][w] , C[i-1][w-Wi[i]]+Vi[i]);
  }

output(C[N][MW]);

Note: actually, top-down is faster than bottom up in this problem since we unnecessarily compute too much thing if MW is big.

7. Counting Change

Counting Change Problem:

Input: A list of denominations and a value N to be changed with these denominations
Output: Number of ways to change N

Suppose you have coins of 1 cent, 5 cents and 10 cents. You are asked to pay 16 cents, therefore you have to give 1 one cent, 1 five cents, and 1 ten cents. Counting Change algorithm can be used to determine how many ways you can use to pay an amount of money.

The number of ways to change amount A using N kinds of coins equals to:

1. The number of ways to change amount A using all but the first kind of coins, +

2. The number of ways to change amount A-D using all N kinds of coins, where D is the denomination of the first kind of coin.

The tree recursive process will gradually reduce the value of A, then using this rule, we can determine how many ways to change coins.

1. If A is exactly 0, we should count that as 1 way to make change.

2. If A is less than 0, we should count that as 0 ways to make change.

3. If N kinds of coins is 0, we should count that as 0 ways to make change.

And finally, this is the Dynamic Programming solution for Counting Change problem (in C):

#include <stdio.h>
#define MAXTOTAL 10000

// This can be very big... long long may not be enough and
// you may need to use Big Integer
long long nway[MAXTOTAL+1];

// Assume we have 5 different coins here
int coin[5] = { 50,25,10,5,1 };

void main() {
  int i,j,n,v,c;
  scanf("%d",&n);
  v = 5;
  nway[0] = 1;
  for (i=0; i<v; i++) {
    c = coin[i];
    for (j=c; j<=n; j++)
      nway[j] += nway[j-c];
  }
  printf("%lld\n",nway[n]);
}

8. Maximum Interval Sum

Maximum Interval Sum Problem:

Input: A sequence of integers
Output: A sum of an interval starting from index i to index j (consecutive), this sum must be maximum among all possible sums.

Initially Sum[i..n] are the integers from the input (individual number).

Sum[i] = Sum[start] + ... + Sum[i]
         if sum from index 'start' to i is >= 0 or
         Sum[i], set start=i+1 (start new interval)
         if sum from index 'start' to 'i' < 0

The simple reasoning of this DP formulation is as follows: if you have positive (or zero) sum, then this current sequence can still be extended to a longer interval with bigger value or at least similar value but longer interval... but if the partial sum is negative... then there is no point to extend it further...

Example:

Numbers : -1 6
Sum     : -1 6
             ^
          max sum

Numbers : 4 -5  4 -3  4  4 -4  4 -5
Sum     : 4 -1  4  1  5  9  5  9  4
             ^                 ^
            stop            max sum

Numbers : -2 -3 -4
Sum     : -2 -3 -4
           ^
        max sum, but negative... (this is the maximum anyway)

So, just do a linear sweep from left to right, accumulate the sum one element by one element, start new interval whenever you encounter partial sum < 0 (and record current best maximum interval encountered so far)...

At the end, output the value of the maximum intervals.

9. Other Dynamic Programming Algorithms

Problems that can be solved using Floyd Warshall and it's variant, which belong to the category all-pairs shortest path algorithm, can be categorized as Dynamic Programming solution. Explanation regarding Floyd Warshall can be found in Graph section of this website.

Other than that, there are a lot of ad hoc problems that can utilize DP, just remember that when the problem that you encountered exploits optimal sub-structure and repeating sub-problems, apply DP techniques, it may be helpful. Good luck :)