Dynamic Programming

Introduction
• Dynamic programming solves problems by
combining the solutions to subproblems.
• Dynamic programming breaks up a problem into a
series of overlapping sub-problems, and builds up
solution to larger problem from sub-problems.
• Dynamic Programming algorithm solves every
subproblem just once and then saves its answer in a
table.
• Looking up the solution when subproblem is
encountered again.
 Divide-and-conquer VS Dynamic
Programming
• In divide-and-conquer a problem is partitioned into
separate sub-problems, solve each sub-problem
independently, and combine solutions to form solution
to original problem.
• Divide-and-conquer algorithms can be thought of as
top-down algorithms
• In contrast, a dynamic programming algorithm
proceeds by solving small problems, then combining
them to find the solution to larger problems.
• Dynamic programming can be thought of as bottom-up.
 Cont.
• Like divide-and-conquer, dynamic programming
solves problems by combining solutions to
subproblems.
• Unlike divide-and- conquer, subproblems are not
independent. Subproblems may share
subsubproblems,
 Steps of a Dynamic Programming

• Characterize the structure of an optimal

solution
• Recursively define the value of an optimal
solution
• Compute the value of an optimal solution in a
bottom-up fashion
• Construct an optimal solution from computed
information
 Matrix-Chain Multiplication
Problem: Given a sequence of matricesA1, A2, .., An,
compute the product: A1  A2  An.
In what order should we multiply the matrices?
A1  A2  An
• Parenthesize the product to get the order in which
matrices are multiplied –
A1  A2  A3 = ((A1  A2)  A3) = (A1  (A2  A3))
• Which one of these orderings should we choose?
– The order in which we multiply the matrices has a
significant impact on the cost.
6
 Example
A1  A2  A3
• A1: 10 x 100 A2: 100 x 5 A3: 5 x 50
1. ((A1  A2)  A3): A1  A2 = 10 x 100 x 5 = 5,000
((A1  A2)  A3) = 10 x 5 x 50 = 2,500
Total: 7,500 scalar multiplications
2. (A1  (A2  A3)): A2  A3 = 100 x 5 x 50 = 25,000
(A1  (A2  A3)) = 10 x 100 x 50 = 50,000
Total: 75,000 scalar multiplications
one order of magnitude difference!!
7
 Matrix-Chain Multiplication:
Problem Statement
• Given a chain of matrices A1, A2, …, An, where
Ai has dimensions pi-1  pi, fully parenthesize the
product A1  A2  An in a way that minimizes the
number of scalar multiplications.
A1  A2  Ai  Ai+1  An
p0  p1 p1  p2 pi-1  pi pi  pi+1 pn-1  pn

8
 Number of possible parenthesizations
• Exhaustively checking all possible prenthesizations
is not efficient!
• Fully parenthesized matrix product is product of two
fully parenthesized matrix subproducts, and the split
between two subproducts may occur between the kth
and k + 1 matrices for any k = 1.2…n - 1.
 P(n) is no. of possibilities
for a chain of n matrices

• It can be shown that the number of parenthesizations

grows as Ω(2n). 9
 Greedy Approach

• Idea #1: repeatedly select the product that uses

the fewest operations.
• Counter-example: A is 101 × 11 B is 11 × 9
C is 9 × 100 D is 100 × 99
• Greedy idea #1 gives A*((B*C)*D)), which
takes 109989+9900+108900=228789 ops
• (A*B)*(C*D) takes
9999+89991+89100=189090 ops . The greedy
approach is not giving us the optimal value.
 1. The Structure of an Optimal
Parenthesization
• Notation:
Ai…j = Ai Ai+1  Aj, i  j

• Suppose that an optimal parenthesization of Ai…j

splits the product between Ak and Ak+1, where
ik<j

Ai…j = Ai Ai+1  Aj

= Ai Ai+1  Ak Ak+1  Aj
= Ai…k Ak+1…j
11
 Cont.
Ai…j = Ai…k Ak+1…j
• The parenthesization of the “prefix” Ai…k must be
an optimal parentesization
• If there were a less costly way to parenthesize
Ai…k, substitute that one in the parenthesization of
Ai…j and produce a parenthesization with a lower
cost than the optimum  contradiction!
• An optimal solution to an instance of the matrix-
chain multiplication contains within it optimal
solutions to subproblems
12
 2. A Recursive Solution

• Subproblem:
determine the minimum cost of parenthesizing
Ai…j = Ai Ai+1  Aj for 1  i  j  n
• Let m[i, j] = the minimum number of
multiplications needed to compute Ai…j
– full problem (A1..n): m[1, n]
– i = j: Ai…i = Ai  m[i, i] = 0, for i = 1, 2, …, n

13
 2. Recursive Solution
• Let m[i, j] =minimum no. of multiplications for Ai…j

• Consider the subproblem of parenthesizing

Ai…j = Ai Ai+1  Aj for 1  i  j  n

pi-1pkpj
= Ai…k Ak+1…j for i  k < j
m[i, k] m[k+1,j]

m[i, j] = m[i, k] + m[k+1, j] + pi-1pkpj

min # of multiplications min # of multiplications # of multiplications
to compute Ai…k to compute Ak+1…j to compute Ai…kAk…j
14
 Cont.
m[i, j] = m[i, k] + m[k+1, j] + pi-1pkpj
• We do not know the value of k
– There are j – i possible values for k: k = i, i+1, …, j-1
• Minimizing the cost of parenthesizing the product
Ai Ai+1  Aj becomes:
0 if i = j
m[i, j] = min {m[i, k] + m[k+1, j] + pi-1pkpj}
ik<j if i < j

15
 3.Computing the optimal costs
• Easy to write a recursive algorithm based on
recurrence for computing m[i,j].
• But the running time will be exponential!...
• Compute the optimal cost by using a tabular,
bottom-up approach.
MATRIX-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]← 
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
Example: min {m[i, k] + m[k+1, j] + pi-1pkpj}
1 2 3
Compute A1  A2  A3 1 2
1 0 7500
• A1: 10 x 100 (p0 x p1) 5000
2 2
0 25000
• A2: 100 x 5 (p1 x p2)
0
• A3: 5 x 50 (p2 x p3) 3

m[i, i] = 0 for i = 1, 2, 3
m[1, 2] = m[1, 1] + m[2, 2] + p0p1p2 (A1A2)
= 0 + 0 + 10 *100* 5 = 5,000
m[2, 3] = m[2, 2] + m[3, 3] + p1p2p3 (A2A3)
= 0 + 0 + 100 * 5 * 50 = 25,000
m[1, 3] = min m[1, 1] + m[2, 3] + p0p1p3 = 75,000 (A1(A2A3))
m[1, 2] + m[3, 3] + p0p2p3 = 7,500 ((A1A2)A3)
18
Example min {m[i, k] + m[k+1, j] + pi-1pkpj}
1 2 3
Compute A1  A2  A3 2
3 2
7500 25000 0
• A1: 10 x 100 (p0 x p1)
1 j
2 5000 0
• A2: 100 x 5 (p1 x p2)
• A3: 5 x 50 (p2 x p3) 1 0

m[i, i] = 0 for i = 1, 2, 3 i

m[1, 2] = m[1, 1] + m[2, 2] + p0p1p2 (A1A2)

= 0 + 0 + 10 *100* 5 = 5,000
m[2, 3] = m[2, 2] + m[3, 3] + p1p2p3 (A2A3)
= 0 + 0 + 100 * 5 * 50 = 25,000
m[1, 3] = min m[1, 1] + m[2, 3] + p0p1p3 = 75,000 (A1(A2A3))
m[1, 2] + m[3, 3] + p0p2p3 = 7,500 ((A1A2)A3)
19
 4. Construct the Optimal Solution
• Matrix s keeps the
optimal values of k 1 2 3 n
1
• s[i, j] = a value of k
2 k
such that an optimal
3
parenthesization of
Ai..j splits the product
between Ak and Ak+1 n

20
 4. Construct the Optimal Solution
• s[i, j] = a value of k such
that an optimal
parenthesization of Ai..j
splits the product between 1 2 3 n
Ak and Ak+1 n
• s[1, n] is associated with
the entire product A1..n
– The final matrix j
multiplication will be split 3
at k = s[1, n] 2
A1..n = A1..s[1, n]  As[1, n]+1..n 1
– For each subproduct
recursively find the i
corresponding value of k
that results in an optimal
parenthesization 21
 Example

• s[i, j] = value of k such that the optimal

parenthesization of Ai Ai+1  Aj splits
the product between Ak and Ak+1
1 2 3 4 5 6
6 3 3 3 5 5 -
5
s[1, n] = 3  A1..6 = A1..3 A4..6
3 3 3 4 -
4 3 3 3 -
s[1, 3] = 1  A1..3 = A1..1 A2..3
3 1 2 - s[4, 6] = 5  A4..6 = A4..5 A6..6
j
2 1 -
1 -
i
22
 Cont.
PRINT-OPT-PARENS(s, i, j)

if i = j

then print “A”i

else print “(”

PRINT-OPT-PARENS(s, i, s[i, j])

PRINT-OPT-PARENS(s, s[i, j] + 1, j)

print “)”

23
Example: A1  A6 ( ( A1 ( A2 A3 ) ) ( ( A4 A5 ) A6 ) )

PRINT-OPT-PARENS(s, i, j) s[1..6, 1..6] 1 2 3 4 5 6

if i = j 6 3 3 3 5 5 -
then print “A”i 5 3 3 3 4 -
else print “(”
4 3 3 3 -
PRINT-OPT-PARENS(s, i, s[i, j]) j
PRINT-OPT-PARENS(s, s[i, j] + 1, j) 3 1 2 -
print “)” 2 1 -
P-O-P(s, 1, 6) s[1, 6] = 3 1 -
i = 1, j = 6 “(“ P-O-P (s, 1, 3) s[1, 3] = 1 i
i = 1, j = 3 “(“ P-O-P(s, 1, 1)  “A1”
P-O-P(s, 2, 3) s[2, 3] = 2
i = 2, j = 3 “(“ P-O-P (s, 2, 2)  “A2”
P-O-P (s, 3, 3)  “A3”
“)”
“)” … 24
Elements of Dynamic Programming
• Optimal substructure
• Overlapping subproblems
 Optimal Substructure
• An optimal solution to a problem contains
within it an optimal solution to subproblems
• Build an optimal solution to the problem from
optimal solutions to subproblems.

26
 Parameters of Optimal Substructure
Optimal substructure varies across problem domains:
• How many subproblems are used in an optimal solution for the
original problem
– Matrix multiplication: Two subproblems (Ai..k, Ak+1..j)
• How many choices we have in determining which
subproblems to use in an optimal solution
– Matrix multiplication: j - i choices for k (splitting the product)
• Informally, running time depends on (# of subproblems
overall)  (# of choices).
• Matrix multiplication:
– (n2) subproblems (1  i  j  n) (n3) overall
– At most n-1 choices 27
 Cont.
• Dynamic programming uses optimal substructure bottom up.
– First find optimal solutions to subproblems.
– Then choose which to use in optimal solution to the problem.
• Does optimal substructure apply to all optimization
problems? No.
• Applies to determining the shortest path but NOT the longest
simple path of an unweighted directed graph.
• Why?
– Shortest path has independent subproblems.
– Subproblems are not independent in longest simple path.
 Overlapping Subproblems
• If a recursive algorithm revisits the same
subproblems over and over  the problem has
overlapping subproblems.
• The total number of distinct subproblems is a
polynomial in the input size.
• A recursive algorithm is exponential because it
solves the same problems repeatedly.
• If divide-and-conquer is applicable, then each
problem solved will be brand new.
RECURSIVE_MATRIX_CHAIN

RECURSIVE_MATRIX_CHAIN(p, i, j)
1 if i = j
2 then return 0
3 m[i, j]  
4 for k  i to j – 1
5 do q  RMC(p,i,k) + RMC(p,k+1,j) + pi-1pkpj
6 if q < m[i, j]
7 then m[i, j]  q
8 return m[i, j]
The recursion tree for the computation
of RECURSUVE-MATRIX-CHAIN(P, 1, 4)
  T (1)  1
T (n)  1  n1(T (k )  T (n  k )  1) for n  1
 k 1

n 1
T( n )  2  T( i)  n
i 1
• We can prove that T(n) = (2n) using
substitution method.
 Cont.
• Alternative approach: memoization
• Store, do not recompute.
• Make a table indexed by subproblem.
• When solving a subproblem:
- Lookup in table.
- If answer is there, use it.
- Else, compute answer, then store it.
 Memoization
• Top-down approach with the efficiency of typical
dynamic programming approach

• Maintaining an entry in a table for the solution to each

subproblem

– memoize the inefficient recursive algorithm

• When a subproblem is first encountered its solution is

computed and stored in that table

• Subsequent “calls” to the subproblem simply look up

34
that value
Dynamic Progamming vs. Memoization
• Advantages of dynamic programming vs.
memoized algorithms
– No overhead for recursion, less overhead for
maintaining the table
– The regular pattern of table accesses may be
used to reduce time or space requirements
• Advantages of memoized algorithms vs.
dynamic programming
– Some subproblems do not need to be solved
35
Matrix-Chain Multiplication - Summary
• Both the dynamic programming approach and the
memoized algorithm can solve the matrix-chain
multiplication problem in O(n3)
• Both methods take advantage of the overlapping
subproblems property
• There are only (n2) different subproblems
– Solutions to these problems are computed only once
• Without memoization the natural recursive
algorithm runs in exponential time
36
 Optimal Binary Search Trees
• Given sequence K = k1 < k2 <··· < kn of n sorted
keys, with a search probability pi for each key ki.
• Some searches may be for values not in ki, and
need n+1 “dummy keys” d0,d1,…,dn representing
not in ki.
• d0 represents all values less than k1, and dn
represents all values greater than kn, and qi is
probability that a search will correspond to di .
• Every search is either successful or unsuccessful.
n n

 p q
i 1
i
i 0
i 1
 Cont.
• Want to build a binary search tree (BST) with
minimum expected search cost.
• Actual cost of a search is the number of nodes
examined.
• Expected cost of a search in a given binary
search tree T:
n n
E[search cost in T]   (depthT (ki )  1)  pi   (depthT (di )  1)  qi
i 1 i 0
n n
 1   depthT (ki )  pi   depthT (di )  qi
i 1 i 0
 k2 k2

k1 k4 k1 k5

d0 d1
d0 d1 d5
k3 k5 k4

d2 d3 d4 d5 d4
k3
Cost =2.80
i 0 1 2 3 4 5
d2 d3

pi 0.15 0.10 0.05 0.10 0.20

Cost =2.75
qi 0.05 0.10 0.05 0.05 0.05 0.10
• By Figure (a), we can calculate the expected search cost node by node:

Cost=
Node# Depth probability cost
Probability *
k1 1 0.15 0.30 (Depth+1)

k2 0 0.10 0.10
k3 2 0.05 0.15
k4 1 0.10 0.20
K5 2 0.20 0.60
d0 2 0.05 0.15
d1 3 0.10 0.30
d2 3 0.05 0.20
d3 3 0.05 0.20
d4 3 0.05 0.20
d5 3 0.10 0.40
 Example
• Observations:
– Optimal BST may not have smallest height.
– Optimal BST may not have highest-probability key
at root.
• Build by exhaustive checking?
– Construct each n-node BST.
– For each,
assign keys and compute expected search cost.
– But there are (4n/n3/2) different BSTs with n
nodes.
 Optimal Substructure
• Any subtree of a BST contains keys in a contiguous
range ki, ..., kj for some 1 ≤ i ≤ j ≤ n and also have
dummy keys di-1, ..., dj as leaves.
• If T is an optimal BST containing a subtree T with
keys ki, ... ,kj , then T must be an optimal BST for keys
ki, ..., kj and dummy keys di-1, ..., dj.
T
• One of the keys in ki, …,kj, say kr, where i ≤ r ≤ j,
must be the root of an optimal subtree for these keys.
kr
• Left subtree of kr contains ki,...,kr1
and the dummy keys( di-1 ,…, dr-1).
• Right subtree of kr contains kr+1, ...,kj.
and the dummy keys( dr ,…, dj). ki kr-1 kr+1 kj
 Optimal Substructure
• If ki is root, then ki ‘s left subtree has no actual
keys but contains the single dummy key di-1.
• Symmetrically, if kj is root, then kj‘s right
subtree has no actual keys, but contains the
dummy key dj.
• To find an optimal BST:
– Examine all candidate roots kr , for i ≤ r ≤ j
– Determine all optimal BSTs containing
ki,...,kr1 and containing kr+1,...,kj
 Recursive Solution
• Find optimal BST for ki,...,kj, where i ≥ 1, j ≤ n, j ≥ i1.
When j = i1, the tree has just the dummy key di-1.
• Define e[i, j ] = expected search cost of optimal BST for
ki,...,kj.

• If j = i1, then e[i, j ] = e[i,i-1]= qi-1.

• If j ≥ i,
– Select a root kr, for some i ≤ r ≤ j .
– Recursively make an optimal BSTs
• for ki,..,kr1 as the left subtree, and
• for kr+1,..,kj as the right subtree.
 Recursive Solution
• When the OPT subtree becomes a subtree of a node:
– Depth of every node in OPT subtree goe
– Excepted search cost of this subtree increases by the
sum of all the probabilities in the subtree
j j
w(i, j)   p   q
l l
l i l  i 1

• If kr is the root of an optimal BST for ki,..,kj :

e[i, j ] = pr + (e[i, r1] + w(i, r1))+(e[r+1, j] + w(r+1, j))
= e[i, r1] + e[r+1, j] + w(i, j).
(because w(i, j)=w(i,r1) + pr + w(r + 1, j))
 • Hence

 qi1 if ji-1,

e[i, j ]  min {e[i,r1]e[r 1, j ]w(i, j )} if i j.
 ir j
 Computing an Optimal Solution
For each subproblem (i,j), store:
• expected search cost in a table e[1 ..n+1 , 0 ..n]
– Will use only entries e[i, j ], where j ≥ i1.
• root[i, j ] = root of subtree with keys ki,..,kj, for
1 ≤ i ≤ j ≤ n.
• w[1..n+1, 0..n] = sum of probabilities
– w[i, i1] = 0 for 1 ≤ i ≤ n.
– w[i, j ] = w[i, j-1] + pj for 1 ≤ i ≤ j ≤ n.
 Pseudo-code
OPTIMAL-BST(p, q, n)
1. for i ← 1 to n + 1
2. do e[i, i 1] ← 0
Consider all trees with l keys.
3. w[i, i 1] ← 0
4. for l ← 1 to n Fix the first key.
5. do for i ← 1 to nl + 1 Fix the last key
6. do j ←i + l1
7. e[i, j ]←∞
8. w[i, j ] ← w[i, j1] + pj
9. for r ←i to j
10. do t ← e[i, r1] + e[r + 1, j ] + w[i, j ] Determine the root
11. if t < e[i, j ] of the optimal
12. then e[i, j ] ← t (sub)tree
13. root[i, j ] ←r
14. return e and root

Time: O(n3)