Advanced Computer

Programming
Dynamic Programming

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

Dynamic Programming Elements
Table Element Definition
Recursive Formula
Computing Sequence

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

Fundamental Elements in CS
Recursion
Structural Complexity
Mathematical Induction
Logic
Divide-and-Conquer
Programming Language

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

Fibonacci Numbers
Definition
F[i] = F[i-1] + F[i-2]
F[0] = 1
F[1] = 1

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

DP Elements
Table Element Definition
F[i] is the i-th element in the sequence.
Recursive Formula
F[i] = F[i-1] + F[i-2]
Computing Sequence
Compute F[2], F[3], … etc.

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

Comparison
A direct loop implementation.
A recursive implementation.
One major advance of DP is to reuse the
elements that we know already.

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

Partition
Given a set of numbers ei, determine whether
we can partition it into two subsets, so that the
sum of these two subset of numbers are equal.
Given 1, 3, 3, 4, 5, the answer is “
yes” .
One set has 1, 3, and 4.
The other set has 3, and 5.

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

DP Elements
Table Element Definition
Let P(i, j) be 1 if it is possible to select from the
first i elements so that the sum is j.
Recursive Formula
P(i, j) is 1 if P(i –1, j) is 1, or P(i -1, j –ei) is 1.
Computing Sequence
Compute one row of P at a time.

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

Table Computation
The numbers are 1, 3, 3, 4, 5

0 1 2 3 4 5 6 7 8
1 1 1 0 0 0 0 0 0 0
3 1 1 0 1 1 0 0 0 0
3 1 1 0 1 1 0 1 1 0
4 1 1 0 1 1 1 1 1 1
5 1 1 0 1 1 1 1 1 1
Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University
Approximate String Matching
Given two string S1 and S2, find a shortest sequence
of operations that transform s1 to S2.
The operations include the following.
Substitution
cat to bat
Insertion
cat to cats
Deletion
cat to at

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

An example
bronze
brownze
brownz
brown
crown

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

DP Elements
Table Element Definition
Let E(i, j) be the minimum number of operations
to transform the first i character to the first j
characters of S2.
Let the i-th char of S1 be c and the j-th char of S2
be d.

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

DP Elements
Recursive Formula
If c is d, E(i, j) = E(i-1, j-1)
If c is not d, E(i, j) is the minimum of the following.
E(i –1, j –1) + 1, (substitute c by d).
E(i –1, j) + 1, (delete c).
E(i, j –1) + 1, (insert d).
Computing Sequence
Compute one row of E at a time.

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

Table Computation

b r o n z e
c 1 2 3 4 5 6
r 2 1 2 3 4 5
o 3 2 1 2 3 4
w 4 3 2 2 3 4
n 5 4 3 2 3 4

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

Longest Common Subsequence
Given two string S1 and S2, find the longest
substring of both S1 and S2.
A is a substring of B if we can find all of A’
s
characters in B in the same order they appear
in A.
abc is a substring of gafbfc.

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

An example
The longest common substring of “ bronze”
and “crown”is “ ron”.
The LCS is not necessarily unique.

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

DP Elements
Let L(i, j) be the length of LCS of the first i
character to the first j characters of S2.
Let the i-th char of S1 be c and the j-th char
of S2 be d.

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

DP Elements
If c is d, L(i, j) = L(i, j) + 1
If c is not d, E(i, j) is the maximum of the
following.
E(i –1, j)
E(i, j –1)
Computing Sequence
Compute one row of L at a time.

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

Table Computation

b r o n z e
c 0 0 0 0 0 0
r 0 1 1 1 1 1
o 0 1 2 2 2 2
w 0 1 2 2 2 2
n 0 1 2 3 3 3

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

Longest Increasing Sequence
Given a sequence of numbers, find the
longest subsequence in which each element is
at least as large as the previous one.
If the sequence is 9, 5, 2, 8, 7, 3, 1, 6, and 4,
the answer is 3.
2, 3, 6
2, 3, 4

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

DP Elements
Let L(i) be the length of the longest
subsequence for the first i numbers that ends
at the i-th number.
L(i) is the maximum of L(j) + 1 for all j that
the i-th number is greater than the j-th number.

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

Table Computation
9, 5, 2, 8, 7, 3, 1, 6, and 4.
The final answer is the maximum of all L(i).

9 5 2 8 7 3 1 6 4

N/A N/A N/A 2, 5 2, 5 2 N/A 2, 3, 1 2, 3, 1

1 1 1 2 2 2 1 3 3

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

Matrix Multiplication
Given a sequence of matrixes M1, … Mn, find the
order to multiply them so that the number of
operations is minimized.
The number of operations of multiplying a a b
matrix to an b c matrix is ac(2b-1).
Multiplication:
 abc
Addition
a(b-1)c

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

An Example
(((A B) C) D)
3 2 4 = 24
3 5 2 = 30
3 4 5 = 60
Total is 114.

1111
11 1111
1111 11 1111
1111 11 11111 1111
1111 11 11111 1111
A B C D
Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University
DP Elements
Let M(i, j) be the minimum number of
multiplications to compute the product form the i-th
to the j-th matrix.
M(i, j) = mink (M(i, k) + M(k + 1, j) + rickcj)
k is where we “ break”the product into two halves.
ri is the number of rows in the i-th matrix.
ck is the number of columns in the k-th matrix.
cj is the number of columns in the j-th matrix.

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

Table Computation
4 Min(54 + 3 5 4, Min(40 + 4 5 4, 2 5 4 = 40 0
24 + 40 + 3 2 4, 40 +4 2 5) = 80
80 + 3 4 4) = 88
3 Min(24 + 3 2 5, 4 2 5 = 40 0
40 + 3 4 5) = 54
2 3 4 2 = 24 0

j=1 0

i=1 2 3 4

1111
11 1111
1111 11 1111
1111 11 11111 1111
1111 11 11111 1111
Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University
Grammar and Words
Given a binary operator on an alphabet A,
and a table of results of , and a string of
characters taken from A, find all the possible
resuls.

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

An Example
 A = {a, b, c}
 a b c
 ((b b) b) a
= (a b) a
= c a = c a a c c
 (b (b b)) a
= (b a) a b a a b
= a a = a
 There is no way to
construct “ b”. c c c c

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

DP Elements
Let C(i, j) be the set of characters we can
construct from the substring of S from the i-th
to the j-th character.
C(i, j)=m{c1c2|c1C(i, m), c2C(m+1, j)}
We “
break”the product into two halves at m.

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

Table Computation
4 c, a a a a  a b c
3 c, a a b
a a c c
2 a b
b a a b
j=1 b
i=1 2 3 4 c c c c

S = b b b a

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

DP Elements
We could also use the following definition.
Let C(i, j, k) be 1 if we can construct the character k
with the substring of S from the i-th to the j-th
character.
C(i, j, k) = 1
There exist k1, k2 in A, and m between i and j so that both
C(i, m, k1) is 1 and C(m+1, j, k2) is 1, and k1 k2 = k.
 We “ break”the product into two halves at m.

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

Minimum Length Triangulation
Given a convex polygon, find the
triangulation that has the minimum total
length.
A Triangulation is a set of non-intersecting
edges that partition a polygon into triangles.

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

A Triangulation Example

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

A Triangle
Every polygon edge is associated with one triangle,
which can be identified by a vertex.

e e e

e e

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

Recursion
Let T(i, j) be the minimum triangulation from vi to
vj.
T(i, j) = min(T(i, k) + T(k, j) + dik + dkj), for all k
between i and j.
i

j
k

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

One-dimensional Shortest Path
Given a directed graph with all of its edge
going from left to right, find a shortest path
from the leftmost node to the rightmost node.

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

An Example

4 8

4 4 3 2

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

DP Elements
Let L(i) be the length of the shortest path that
ends at the i-th node from the left.
L(i) = minj L(j) + distance from j to i

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

Table Computation

1 2 3 4 5

0 4 Min(0+4, 4+4) Min(0+6, 8+3) Min(4+8, 6+2)

0 4 8 6 8

4 8

4 4 3 2

6
Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University
Stereo Sets
We want to ship stereo sets. Each stereo set
has a receiver and a pair of speakers.
A receiver weights R, and a speaker weights S.
We ship the sets by C containers. The i-th
container can ship up to Wi in weight.
Find the maximum number of set that we can
ship.

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

DP Elements
Let N(i, r) be the maximum number of speakers we
can ship with the first i container when the number
of receivers is r.
N(i, r)=maxk (S(i –1, r –k) +  Wi –k R)/S )
k is the number of receiver we placed in the i-th container.
 The answer is the maximum r such that N(C, r) 2r.

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

 Table Computation
R = 3, S = 2, W1 = 8, W2 = 8, W3 = 5.

3 8+2= 10 max(8+(5-3)/2, max(6+(5-3)/2, max(5+(5-3)/2, max(4+(5-3)/2, Don’

t care
6+(5/2)) = 10 5+5/2) = 7 4+5/2) = 6 2+5/2) = 5
2 4+4 = 8 max(4+(8-3)/2, max(4+(8-6)/2, max(2+(8-6)/2, 2 0
2+(8/2)) = 6 2+(8-3)/2, 1+ (8–3)/2,
1+8/2) = 5 0+ 8/2) = 4
i=1 4 2 1 0 0 0

r=0 1 2 3 4 5

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

DP Elements
Let N(i, r) be the maximum number of speakers we
can ship with the first i container when the number
of receivers is r.
N(i, r)=maxk (S(i –1, r –k) +  Wi –k R)/S )
k is the number of receiver we placed in the i-th container.
 The answer is the maximum r such that N(C, r) 2r.

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

Fast Food Chain
There are n fast food restaurants along a
highway. Their positions are given as p1,
p2, …pn.
Select k restaurants as suppliers, so that the
sum of distance between restaurants and their
corresponding suppliers is minimized.

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

An Example
 n = 7, k = 3
 p1=0, p2 = 1, p3 = 3, p4=6, p5 = 7, p6 = 9, p7 = 10.
 By selecting p2 , p4 , and p6 ,the sum of distance is
1 + 0 + 2 + 0 + 1 + 0 + 1 = 5

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

DP Elements
Let C(i, j) be the minimum cost of selecting j
suppliers in the first i restaurants.
C(i, j)=mink (C(i –k, j - 1)+Mk+1,i)
Mk+1,i is the minimum cost of selecting a supplier
from the pk+1 to pi.

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

Table Computation

3 N/A N/A 0 Not used Not used Not used min(0+9,1+6,

3+3,4+1,6+0)
=5
2 N/A 0 min(0+2, min(0+5,1+3, min(0+9,1 min(0+12,1+7 Not used
1+0)=1 3+0) = 3 +4,3+1,8+0) ,3+3,8+2,12+
=4 0)=6
j=1 0 1 3 8 12 18 22

i=1 2 3 4 5 6 7

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

Just Talking
There are m male students, f female students, and a
teacher in a classroom.
The teacher wants to compute the total amount of
money in the classroom by a “ reduction”procedure.
A student tells his/her amount of money to another
student (or to the teacher). The receiver computes
the sum, and relay the information to the next
receiver.

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

Reduction
Everyone can only speak to one person,
everyone can only listen to one person, and
no one can speak and listen at the same time.
It takes 3 seconds for a female student to tell
a number, and 5 seconds for a male student.
How to do this in the least amount of time?

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

Examples
We have the teacher, Tom, John and Mary in the
classroom.
 Tom tells John, Mary tells the teacher, then John
tells the teacher.
10 seconds.
Tom tells teacher, John tells Mary, then Mary tells
teacher.
8 seconds.

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

Minimum Critical Path
A path is a route from a leaf to the root.
A path is critical if it has the longest length, where
the length is defined as the sum of node costs.
The minimum critical path problem is to arrange a
set of nodes into a binary tree so that the length of
the critical path is minimized.

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

Observation
It is always possible to find an optimal
arrangement where the cost of every parent is
no greater than both of its children.
This implies we can always put the smallest
node at the root.

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

An Example

3 5

5 5 5 3

8 8 10 8

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

Two Classes of Gossips
If there are only two kinds of nodes, the
minimum critical path problem can be solved
by dynamic programming.

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

DP Elements
Let C(f, s) be the minimum critical path for a tree
with f fast talkers and s slow talkers.
If f > 0, C(f, s) = T(f)+min(C(fl, sl) + C(fr, sr))
fl, and sl are the number of fast/slow talkers in the left
subtree.
fr, and sr are the number of fast/slow talkers in the right
subtree.
If f is 0, C(f, s) = 
log(s+1)

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

Cutting Pieces
IOI 2004
Given a plate of size w by h, we want to cut it
into pieces so that minimum area is wasted..
There are only k sizes we can sell these pieces.
Every cut must go through the entire width or
the entire length.

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

An Example
The size of the plate is
5 by 7.
The sellable sizes are 2
by 3, 5 by 2 and, 7 by
10.

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

DP Elements
Let M(w, h) be the minimum waste area.
M(w, h) = min (M(wl, h) + M(wr, h), M(w, hl)
+ M(w, hu))
wl and wr are the width after a vertical cut.
hl and hu are the height after a horizontal cut.

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

Possible Saving
Do not cut a piece that is too narrow or too
short.
Cut till the middle is fine due to symmetry.
Is it possible to prove that there exist an
optimal solution that we always
Cut horizontally with the one of the height?
Cut vertically with one of the width?

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

A Similar Problem
What if the problem is reduced to one
dimension?
We have a problem similar to partition, but
The elements can be selected multiple times.
We are minimize the “leftover”.
In this case you can prove the “ pick one of
the sizes”is a correct strategy.

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

The Largest Square
We have a rectangular construction site, in
which we want to build a square house.
Some part of the land is not suitable for
construction.
What is the largest house you can build?

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

An Example

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

DP Elements
Let S(i, j) be the maximum size one can build for a
house whose lower left corner is at (i, j).
S(i+1,j) == S(i,j+1)
S(i,j) = S(i,j+1)+1 if (i+S(i,j+1), j+S(i,j+1)) is subitable
for construction.
S(i,j) = S(i,j+1) otherwise.
S(i+1,j) != S(i,j+1)
S(i,j) = min(S(i+1,j), S(i,j+1)) + 1

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

An Illustration

(i,j) (i,j)

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

The Result

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

An Example

1 1 1 1 1 1 1 1 1

2 2 2 1 0 2 1 0 1

1 0 2 1 1 2 1 1 1

1 1 2 2 1 0 2 2 1

2 1 0 2 1 1 1 0 1

2 1 1 2 2 2 1 1 1

1 0 2 3 3 2 2 2 1

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

Maximum Triangle
The problem is similar to the maximum
square.
Find the maximum sized triangle in a
triangular area.
The only complication is that you might have
a“ up-side-down”triangle.

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

An Example

1 1

1 2

1 1 1

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

Postage Stamps Problem
We have infinite amount of stamps of
different values.
What is the smallest postage amount that
could not be paid by these stamps?

Stamps : 1 , 3 , 5

Need : 14 = 5 + 5 + 3 + 1

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

DP Elements
Let A(i) be 1 if we could pay for the postage
of i units, 0, otherwise.
Let the postage stamps be of s1, s2, … sk units.
A(i) = 1 if and only if there is an j such that
A(i –sj) is 1, where j is between 1 and k.
The smallest i such that A(i) is 0 is the answer.

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

The Messenger
There is a messenger and N recipients on a unit grid
mesh.
The messenger can talk to a recipient as long as they
have the same x or y coordinate, so he only needs to
move to the same row or column of the recipient.
Given the coordinates of all recipients, how to move
the messenger so that he could send the message to
all recipients with the shortest moving distance.

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University

An Illustration
M

R R
R

Pangfeng Liu, Advanced Computer Programming 2004, National Taiwan University