Design and Analysis of

Algorithms (CS-306)

Dynamic Programming

Lecture No. 5

Dr. Javed Iqbal

 Summary
Divide and Conquer Dynamic Programming
Partitions a problem into Partitions a problem into
independent smaller sub- overlapping sub-
problems problems
Does not store solutions of Store Solutions of sub-
sub-problems.(Identical sub problems: these avoids
problems may arise-results calculations of same
in the same computations quantity twice
are performed repeatedly)
Top down algorithms: which Bottom up algorithms: in
logically progresses from which the smallest sub
initial instance down to the problems are explicitly
smallest sub instances via solved first and the
intermediate sub-instances results of these are used
Dynamic Programming
Intro
Dynamic programming, is similar to divide-and-
conquer in that an instance of a problem in divided
into smaller instances. However, in this approach we
solve small instances first, store the results, and later,
whenever we need a result, look it up instead of
recomputing it.

Dynamic programming is a bottom-up

approach. The steps in the development of a
dynamic programming algorithm are as follows:
1. Establish a recursive property that gives the
solution to an instance of the problem.
2. Solve an instance of the problem in a bottom-
up fashion by solving smaller instances first.
Dynamic Programming
Intro
We have looked at several algorithms
that involve recursion.

In some situations, these algorithms

solve fairly difficult problems
efficiently
◦ BUT in other cases they are inefficient
because they recalculate certain
function values many times.

The example of this given in the text

is the Fibonacci example.
Dynamic Programming
Intro
The Recursive solution to finding the nth Fibonacci
number:
public static int fibrec(int n)
{
if (n < 2)
return n;
else
return fibrec(n-1)+fibrec(n-2);
}

The problem:
◦ Lots and lots of calls to Fib(1) and Fib(0) are made.
 It would be nice if we only made those method calls once, then
simply used those values as necessary.

 If I asked you to compute the 10th Fibonacci number, you would

never do it using the recursive steps above. Instead, you'd start
making a chart:
◦ F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5, F6 = 8, F7 = 13, F8 = 21, F9 = 34, F10
= 55.
◦ First you calculate F3 by adding F1 and F2, then F4, by adding F3 and F4,
Dynamic Programming
The idea of dynamic programming is to
avoid making redundant method calls
◦ Instead, one should store the answers to all necessary
method calls in memory and simply look these up as
necessary.

 Using this idea, we can code up a dynamic programming

solution to the Fibonacci number question that is far
more efficient than the recursive version:
public static int fib(int n) {

int[] fibnumbers = new int[n+1];

fibnumbers[0] = 0;
fibnumbers[1] = 1;

for (int i=2; i<n+1;i++)

fibnumbers[i] = fibnumbers[i-1]+fibnumbers[i-2];

return fibnumbers[n];
}
Dynamic Programming
Usually, a dynamic programming
algorithm presents a time-space
trade off.
◦ More space is used to store values,
◦ BUT less time is spent because
these values can be looked up.
Dynamic Programming
Example Problems
◦ Longest Common Subsequence
Problem
◦ Edit Distance
◦ Binomial Coefficient
◦ Chain Matrix Multiplication Problem
◦ Knapsack 0-1 Algorithm
◦ Floyd Warshall Algorithm
◦ The Fibonacci example
◦ The Coin Change problem
Longest Common Subsequence
Problem
Theproblem is to find the longest
common subsequence in 2 given strings.

A subsequence of a string is simply some

subset of the letters in the whole string in
the order they appear in the string.
◦ For example, given the string
“GOODMORNING”

◦ “ODOR” is a subsequence
 made up of the characters at indices 1, 3, 5, and 6.

◦ “MOOD” is not a subsequence,

 since the characters are out of order.
Longest Common
Subsequence
Recursive solution to the problem:
◦ If the last characters of both strings s1 and s2
match,
 then the LCS = 1 + the LCS of
Forboth of the strings with
example,
their last characters removed.
“BIRD” and “FIND”

◦ If the last characters of both strings do NOT

match, then the LCS will be one of twoFor example,
options:
“BIR” and “FIN”
1)The LCS of x and y without its last character.
2)The LCS of y and x without its last character.

◦ We will then take the maximum of the 2

values. Max ( LCS(“BI” , “FIN”) , LCS(“BIR” ,
“FI”) )

 (Also, we could just have easily compared the first 2

public static int lcsrec(String x, String y)
{
// If one of the strings has 1 character, search for that
// character in the other string and return 0 or 1.
if (x.length() == 1)
return find(x.charAt(0), y);
if (y.length() == 1)
return find(y.charAt(0), x);

// Solve the problem recursively.

// Check if corresponding last characters match.
if (x.charAt(len1-1) == y.charAt(len2-1))
return 1 + lcsrec(x.substring(0, x.length()-1),
y.substring(0,y.length()-1));

// Corresponding characters do not match.

else
return max(lcsrec(x, y.substring(0, y.length()-1)),
lcsrec(x.substring(0,x.length()-1), y));
}
 LCS – trace through
recursive solution
LCS(“FUN” =2
, “FIN”)
◦ Last chars match: 1 + LCS (“FU”,=“FI”)
1+1=2

LCS(“FU”, “FI”)
=1
◦ Last chars Do NOT match:
max(LCS(“FU”, “F”), LCS(“F”, “FI”)
= max (1 , 1) = 1
LCS(“FU”, “F”) LCS(“F”, “FI”)
Base case: return 1, since “F” is in “FU” return 1, since “F” is in “FI”
 Longest Common

Subsequence
Now, our goal will be to take this
recursive solution and build a
dynamic programming solution.
◦ The key here is to notice that the heart
of each recursive call is the pair of
indexes, telling us which prefix string we
are considering.
◦ In some sense, we can build the answer
to "longer" LCS questions based on the
answers to smaller LCS questions.
◦ This can be seen trace through the
recursion at the very last few steps.
Longest Common
Subsequnce
Ifwe make the recursive call on the
strings RACECAR and CREAM,
◦ once we have the answers to the
recursive calls for inputs RACECAR and
CREA and the inputs RACECA and
CREAM,
◦ we can use those two answers and
immediately take the maximum of the
two to solve our problem!
 Longest Common
Subsequence
Thus, think of storing the
answers to these recursive calls
in a table, such as this:
R A C E C A R
C
R
E
A XXX
M

In this chart for example, the slot

with the XXX will store an integer
that represents the longest common
subsequence of CREA and RAC. (In
this case 2.)
Longest Common
Subsequence
To build the table, first initialize the
first row and column.
◦ Basically, we search for the first letter in
the other string, when we get there, we
put a 1, and all other values subsequent
to that on the row or column are also
one.
◦ This corresponds to the base case in the
recursive Rcode.
A C E C A R
C 0 0 1 1 1 1 1
R 1
E 1
A 1
M 1
Longest Common
Subsequence
Now, we simply fill out the chart according to the
recursive rule:
1) Check to see if the "last" characters match.
Recursive: If so, delete this and take the LCS of what's left
and add 1 to it.
Dynamic Programming: Look up&left in the table,
add 1 to that.

2) If not, then we try 2 possibilities, and take the maximum of

those 2 possibilities.
Recursive: (These possibilities are simply taking the LCS of
the whole first word and the second word minus the last
letter, and vice versa.)
Dynamic Programming: Max ( cell to the left , cell
above )
R A C E C A R
C 0 0 1 1 1 1 1
R 1 1 1 1 1 1 2
E 1 1 1 2 2 2 2
A 1 2 2 2 2 3 3
M 1 2 2 2 2 3 3
Longest Common
Subsequence
Dynamic Programming Code…
public static int computeLCS(String a, String b)
{
int[][] lengths = new int[a.length()+1][b.length()+1];

// row 0 and column 0 are init. to 0 already

for (int i = 1; i <= a.length(); i++)
for (int j = 1; j <= b.length(); j++)
if (a.charAt(i) == b.charAt(j))
lengths[i][j] = lengths[i-1][j-1] + 1;
else
lengths[i][j] = Math.max(lengths[i][j-1], lengths[i-1]
[j]);

return lengths[a.length()][b.length()];
}
Edit Distance
 The Edit Distance (or Levenshtein
distance) is a metric for measuring the
amount of difference between two.
◦ The Edit Distance is defined as the
minimum number of edits needed to
transform one string into the other.

 Ithas many applications, such as spell

checkers, natural language translation,
and bioinformatics.
◦ Another major application in
Bioinformatics, measuring the amount of
difference between two DNA sequences.
Edit Distance
The problem of finding an edit distance
between two strings is as follows:

◦ Given an initial string s, and a target

string t, what is the minimum number of
changes that have to be applied to s to turn
it into t ?

The list of valid changes are:

1)Inserting a character
2)Deleting a character
3)Changing a character to another character.
Edit Distance
You may think there are too many
recursive cases. We could insert a
character in quite a few locations!
◦ (If the string is length n, then we can
insert a character in n+1 locations.)
◦ However, the key observation that leads
to a recursive solution to the problem is
that ultimately, the last characters will
have to match.
Edit Distance
 So,when matching one word to another one,
consider the last characters of strings s and t.

 If we are lucky enough that they ALREADY match,

◦ then we can simply "cancel" and recursively find the
edit distance between the two strings left when we
delete this last character from both strings.

 Otherwise, we MUST make one of three changes:

1)delete the last character of string s
2)delete the last character of string t
3)change the last character of string s to the last
character of string t.

◦ Also, in our recursive solution, we must note that the

edit distance between the empty string and another
string is the length of the second string. (This
corresponds to having to insert each letter for the
transformation.)
 Edit Distance
 So, an outline of our recursive solution is as
follows:
1) If either string is empty, return the length of the
other string.

2) If the last characters of both strings match,

recursively find the edit distance between each
of the strings without that last character.

3) If they don't match then return 1 + minimum

value of the following three choices:
a) Recursive call with the string s w/o its last character
and the string t
b) Recursive call with the string s and the string t w/o its
last character
c) Recursive call with the string s w/o its last character
Edit Distance
Now, how do we use this to
create a DP solution?
◦ We simply need to store the answers
to all the possible recursive calls.
◦ In particular, all the possible
recursive calls we are interested in
are determining the edit distance
between prefixes of s and t.
 Edit Distance
 Considerthe following example with
s="hello" and t="keep".
◦ To deal with empty strings, an extra row and
column have been added to the chart below:

 Anentry in this table simply holds the

edit distance between two prefixes of the
two strings.
◦ For example, the highlighted square
indicates that the edit distance between the
Edit Distance
In order to fill in all the values in this
table we will do the following:
1) Initialize values corresponding to the
base case in the recursive solution.
h e l l o
0 1 2 3 4 5
k 1
e 2
e 3
p 4
Edit Distance
Inorder to fill in all the values in this
table we will do the following:
2) Loop through the table from the top left
to the bottom right. In doing so, simply
follow the recursive solution.
 If the characters you are looking at match,
Just bring down
h e l l o the up&left value.
0 1 2 3 4 5
k 1 1 2 3 4 5
e 2 2
e 3
p 4
 Else the characters don't match,
min ( 1+ above, 1+ left, 1+diag up)
h e l l o
0 1 2 3 4 5
k 1 1 2 3 4 5
e 2 2 1
e 3
p 4
Binomial Coefficient
 Binomial coefficient is given by the
following relation

 For
values of n and k that are not small,
we cannot compute the binomial
coefficient directly from this definition
because n! is very large even for
moderate values of n.
For simplicity the following relation is used

We can eliminate the need to compute n! or

k! by using this recursive property. This
suggests the following divide-and-conquer
algorithm.
Binomial Coefficient
Like some other Algorithms, this
algorithm is very inefficient.
In the exercises you will establish
that the algorithm computes
terms to determine
The problem is that the same instances
are solved in each recursive call.
For example, bin (n − 1) k − 1) and bin
(n − 1, k) both need the result of bin (n
− 2, k − 1), and this instance is solved
separately in each recursive call.
the divide-and-conquer approach is
always inefficient when an instance is
divided into two smaller instances that
are almost as large as the original
instance.
A more efficient algorithm is developed next using
dynamic programming.
 A recursive property has already been established.
 We will use that property to construct our solution in an
array B, where B [i] [j] will contains i C j.
 The steps for constructing a dynamic programming
algorithm for this problem are as follows:
 1. Establish a recursive property. This has already been
done. Written in terms of B, it is

 2. Solve an instance of the problem in a bottom-up

fashion by computing the rows in B in sequence starting
with the first row.
Example
Compute
B [0] [0] = 1
Compute row 1: B [1] [0] = 1
B [1] [1] = 1
Compute row 2: B [2] [0] = 1
B [2] [1] = B [1] [0] + B [1] [1] = 1+1 = 2
B [2] [2] = 1
Compute row 3: B [3] [0] = 1
B [3] [1] = B [2] [0] + B [2] [1] = 1+2 = 3
B [3] [2] = B [2] [1] + B [2] [2] = 2+1 = 3
Compute row 4: B [4] [0] = 1
B [4] [1] = B [3] [0] + B [3] [1] = 1+3 = 4
B [4] [2] = B [3] [1] + B [3] [2] = 3+3 = 6
Figure 3.1: The array B used
to compute the binomial
coefficient
 Algorithm for Binomial
Coefficient
 Algorithm 3.2: Binomial Coefficient Using Dynamic
Programming
 Problem: Compute the binomial coefficient.
 Inputs: nonnegative integers n and k, where k ≤ n.
 Outputs: bin 2, the binomial coefficient
int bin2 (int n, int k)
{
index i, j;
int B[0..n] [0..k];
for (i = 0; i <= n; i++)
for (j = 0; j <= minimum (i, k); j++)
if (j = = 0 || j = = i)
B[i][ j] = 1'
else
B[i[j] = B[i - 1][j - 1] + B[i - 1] [j];
return B[n[k];
}
The parameters n and k are not the size of
the input to this algorithm.
Rather, they are the input, and the input
size is the number of symbols it takes to
encode them.
However, we can still gain insight into the
efficiency of the algorithm by determining
how much work it does as a function for n
and k.
For given n and k, let's compute the
number of passes through the for-j loop.
The following table shows the number of
passes for each value of i;
Total number of passes are given by
 By using dynamic programming instead of divide-
and-conquer, we have developed a much more
efficient algorithm.
 Dynamic programming is similar to divide-and-
conquer in that we find a recursive property that
divides an instance into smaller instances.
 The difference is that in dynamic programming we
use the recursive property to iteratively solve the
instances in sequence, starting with the smallest
instance, instead of blindly using recursion.
 In this way we solve each smaller instance just
once.
 Dynamic programming is a good technique to try
when divide-and-conquer leads to an inefficient
algorithm.
 Another improvement to the algorithm would be to
take advantage of the fact that
The Change Problem
Given a certain amount of money,
how many different ways are there
to make change for that amount of
money?

Or more simply…

Given a positive integer n, how
many ways can we make change
for n cents using pennies, nickels,
dimes and quarters?
The Change Problem
 Recursively, we could break down the problem as
follows:
◦ To make change for n cents we could:
1)Give the customer a quarter. Then we have to make change for
n-25 cents
2)Give the customer a dime. Then we have to make change for n-
10 cents
3)Give the customer a nickel. Then we have to make change for
n-5 cents
4)Give the customer a penny. Then we have to make change for
n-1 cents.

 Ifwe let T(n) = number of ways to make change for n

cents, we get the formula
◦ T(n) = T(n-25)+T(n-10)+T(n-5)+T(n-1)

◦ Is there anything wrong with this?

◦ In particular, for this recurrence relation T(6)=3, but in

actuality, we want T(6)=2.)
The Change Problem
 Sothis can not be right. What is wrong
with our logic?
◦ In particular, it can been seen that this
formula is an OVERESTIMATE of the actual
value.
◦ Specifically, this counts certain combinations
multiple times. In the above example, the one
penny, one nickel combination is counted
twice. Why is this the case?

 Theproblem is that we are counting all

combinations of coins that can be given
out where ORDER matters.
◦ (We are counting giving a penny then a nickel
separately from giving a nickel and then a
penny.)
The Change Problem
 We have to find a way to NOT do this.
◦ One way to do this is IMPOSE an order on the way the
coins are given.
◦ We could do this by saying that coins must be given from
most value to least value.
 Thus, if you "gave" a nickel, afterwards, you would only be
allowed to give nickels and pennies.

 Usingthis idea, we need to adjust the format of our

recursive computation:
◦ To make change for n cents using the largest coin d, we
could

1)If d is 25, give out a quarter and make change for n-25 cents
using the largest coin as a quarter.
2)If d is 10, give out a dime and make change for n-10 cents using
the largest coin as a dime.
3)If d is 5, give out a nickel and make change for n-5 cents using
the largest coin as a nickel.
4)If d is 1, we can simply return 1 since if you are only allowed to
give pennies, you can only make change in one way.
The Change Problem
There's a whole bunch of stuff going on
here, but one of the things you'll notice
is that the larger n gets, the slower and
slower this will run, or maybe your
computer will run out of stack space.
◦ Further analysis will show that many, many
method calls get repeated in the course of
a single initial method call.

Indynamic programming, we want to

AVOID these reoccurring calls.
◦ To do this, rather than making those three
recursive calls above, we could store the
values of each of those in a two
dimensional array.
 The Change Problem
Denominations:
Amount we’re making change for
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
penny 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
nickel 5 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4
dime 10 1 1 1 1 2 2 2 2 2 4 4 4 4 4 6
quarter 25 1 1 1 1 2 2 2 2 2 4 4 4 4 4 6

Essentially,each row label stands for

the number of cents we are making
change for
Each column label stands for the largest
coin value allowed to make change.
The Change Problem
Originally our table looks like this:
Denominations:
Amount we’re making change for
0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1
penny 0 1 2 3 4 5
nickel 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
dime 5 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0
quarter 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0
0
Because1 we
1 1know
1 1 0 our
0 0 initial
2 0 0 0 conditions:
0 0 0 0 0
5
 There is only 1 way to make change for
1cent through 15 cents using only pennies.
 That’s the first row.
 And there is only one way to make change
for 4 cents or less, you can only use
pennies.
 That’s the first 4 columns
The Change Problem
 Now we need to fill in the cells initialized to 0.
◦ Sum for each denomination less than or equal to
the one we are on, whether there we can use that
denomination (and how many times based on
previous values).
◦ For example, in the red space below:
 can we make change for 5 cents using pennies? +1
 Can we make change for 5 cents using nickels? +1
 Stop.
Denominations:

Amount we’re making change for

0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1
penny 0 1 2 3 4 5
nickel 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
dime 5 1 1 1 1 1 20 0 0 0 0 0 0 0 0 0 0
quarter 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0
0
2 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0
5
public static int makeChangedyn(int n, int d) {
// Take care of simple cases.
if (n < 0) return 0;
else if ((n>=0) && (n < 5)) return 1;

// Build table here.

else {
int[] denominations = {1, 5, 10, 25};
int[][] table = new int[4][n+1];

// Initialize table
for (int i=0; i<n+1;i++)
table[0][i] = 1;
for (int i=0; i<5; i++) {
table[1][i] = 1;
table[2][i] = 1;
table[3][i] = 1;
}
for (int i=5;i<n+1;i++) {
table[1][i] = 0;
table[2][i] = 0;
table[3][i] = 0;
// Fill in table, row by row. Remember,
for (int i=1; i<4; i++) { int[] denominations = {1, 5, 10, 25};
for (int j=5; j<n+1; j++) {
for (int k=0; k<=i; k++) {
if ( j >= denominations[k])
table[i][j] +=
table[k][j - denominations[k]];
}
}
}
return table[lookup(d)][n];
}
}

 Now see if you can finish filling in the zeroed

out portion of the table using the code above.
0 1 2 3 4 5 6 7 8 9 1 1 1 1 14 1
0 1 2 3 5
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
5 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0
0
2 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0
The Change Problem
 Analternate way to code this up is to realize
that we DON'T need to add many different
cases up together.
◦ Instead, we note that the number of ways to
make change for n cents using denomination d
can be split up into counting two groups:
1) The number of ways to make change for n cents using
denominations LESS than d
 simply the value in the table that is directly above the
one we are trying to fill.
2) The number of ways to make change for n cents using
at least ONE coin of denomination d.
 the value on the table that is on the same row, by d
spots to the left.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
5 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4
10 1 1 1 1 1 2 2 2 2 2 4 4 4 4 4 6
25 1 1 1 1 1 2 2 2 2 2 4 4 4 4 4 6
The Change Problem
To make this change in the code,
just substitute this line for the for
loop with k in the previous code:
if ( j >= denominations[i])
table[i][j] = table[i-1][j] + table[i][j -
denominations[k]];
else
table[i][j] = table[i-1][j]
 Now see if you can finish filling in the
zeroed out portion of the table using the
code above.
0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1
0 1 2 3 4 5
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
5 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0
0
2 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0
References
Slides adapted from Arup Guha’s
Computer Science II Lecture notes:
http://www.cs.ucf.edu/~dmarino/ucf/c
op3503/lectures/
Additional material from the textbook:
Data Structures and Algorithm Analysis in
Java (Second Edition) by Mark Allen Weiss
Additional images:
www.wikipedia.com
xkcd.com