Dynamic Programming

1
1. Introduction
i. What is Dynamic Programming?
ii. Elements of Dynamic Programming

2. Matrix-Chain Multiplication
i. Matrix-Chain Multiplication Problem
ii. Algorithms
iii. Examples

2
 Introduction

3
 What is Dynamic Programming?

 Dynamic programming solves optimization

problems by combining solutions to
subproblems.
 “Programming” refers to a tabular method
with a series of choices, not “coding”
 A set of choices must be made to arrive at
an optimal solution.
 As choices are made, subproblems of the
same form arise frequently.
 The key is to store the solutions of
subproblems to be reused in the future.

4
 What is Dynamic Programming?

 Dynamic programming is applicable when

subproblems are not independent.
 i.e., subproblems share subsubproblems
 Solve every subsubproblem only once
and store the answer for use when it
reappears.
 A dynamic programming approach consists
of a sequence of 4 steps:
 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

5
 Elements of Dynamic Programming

 For dynamic programming to be applicable,

an optimization problem must have:
 Optimal substructure
 An optimal solution to the problem
contains within it optimal solution to
subproblems (but this may also mean a
greedy strategy applies)
 Overlapping subproblems
 The space of subproblems must be
small; i.e., the same subproblems are
encountered over and over

6
 Matrix-Chain
Multiplication

7
 Matrix-Chain Multiplication

 Suppose we have a sequence or chain A1,

A2, …, An of n matrices to be multiplied.
 That is, we want to compute the product
A1A2…An.
 There are many possible ways
(parenthesizations) to compute the product.
 Example: consider the chain A1, A2, A3, A4 of 4
matrices.
 Let us compute the product A1A2A3A4.
 There are 5 possible ways:
 (A1(A2(A3A4)))
 (A1((A2A3)A4))
 ((A1A2)(A3A4))
 ((A1(A2A3))A4)
 (((A1A2)A3)A4)

8
 Multiplication of Two Matrices

To compute the number of scalar

multiplications necessary, we must know:
Algorithm to multiply two matrices.
Matrix dimensions.
Input: Matrices Ap×q and Bq×r
Output: Matrix Cp×r resulting from A·B
Algorithm Matrix-Multiply(Ap×q , Bq×r)
{ for i : = 1 to p do
for j := 1 to r do
{ C[i, j] := 0;
for k := 1 to q do
C[i, j] := C[i, j] + A[i, k] · B[k, j];
}
return C;
}
Number of scalar multiplications = pqr

9
 Example

 Example: Consider three matrices A10100,

B1005, and C550
 There are 2 ways to parenthesize
 ((AB)C) = D105 · C550
 AB  10·100·5 = 5,000 scalar
multiplications,
 DC  10·5·50 = 2,500 scalar
multiplications,
 Total scalar multiplication = 7,500
 (A(BC)) = A10100 · E10050
 BC  100·5·50 = 25,000 scalar
multiplications,
 AE  10·100·50 = 50,000 scalar
multiplications,
 Total scalar multiplication = 75,000

10
 Matrix-Chain Multiplication Problem

 Matrix-chain multiplication problem

 Given a chain A1, A2, …, An of n matrices,
where for i=1, 2, …, n, matrix Ai has
dimension pi-1pi.
 Parenthesize the product A1A2…An such
that the total number of scalar
multiplications is minimized.
 Note that in the matrix-chain multiplication
problem, we are not actually multiplying
matrices.
 Our aim is only to determine the an order for
multiplying matrices that has the lowest cost.
 Typically, the time invested in determining this
optimal order is more than paid for by the time
saved later on when actually performing the
matrix multiplications, such as performing only
7,500 scalar multiplications instead of 75,000.
 Brute force method of exhaustive search
takes time exponential in n.

11
 Dynamic Programming Approach

 Step 1: The structure of an optimal solution

 Let us use the notation Ai..j for the matrix
that results from the product Ai Ai+1 … Aj
 An optimal parenthesization of the product
A1A2…An splits the product between Ak and
Ak+1 for some integer k where1 ≤ k < n
 First compute matrices A1..k and Ak+1..n ;
then multiply them to get the final matrix
A1..n
 Key observation: parenthesizations of the
subchains A1A2…Ak and Ak+1Ak+2…An must
also be optimal if the parenthesization of
the chain A1A2…An is optimal
 That is, the optimal solution to the problem
contains within it the optimal solution to
subproblems

12
 Dynamic Programming Approach (Contd.)

 Step 2: A Recursive solution

 Let m[i, j] be the minimum number of scalar
multiplications necessary to compute Ai..j
 Minimum cost to compute A1..n is m[1, n]
 Suppose the optimal parenthesization of Ai..j
splits the product between Ak and Ak+1 for
some integer k where i ≤ k < j
 Ai..j = (Ai Ai+1…Ak)·(Ak+1Ak+2…Aj)= Ai..k · Ak+1..j
 Cost of computing Ai..j = cost of computing
Ai..k + cost of computing Ak+1..j + cost of
multiplying Ai..k and Ak+1..j
 Cost of multiplying Ai..k and Ak+1..j is pi-1pk pj
 m[i, j ] = m[i, k] + m[k+1, j ] + pi-1pk pj
for i ≤ k < j
 m[i, i ] = 0 for i=1,2,…,n
 But… optimal parenthesization occurs at one
value of k among all possible i ≤ k < j
 Check all these and select the best one

13
 Dynamic Programming Approach (Contd.)

 Step 2: A Recursive solution (contd..)

 Thus, our recursive definition for the
minimum cost of parenthesizing the product
Ai Ai+1…Aj becomes
0 if i  j,

m[i, j ]   min
i  k  j {m[i, k ]  m[k  1, j ]  p j 1 pk p j } if i  j.

 To keep track of how to construct an optimal
solution, let us define s[i, j ] = value of k at
which we can split the product Ai Ai+1 … Aj to
obtain an optimal parenthesization.
 That is, s[i, j] equals a value k such that m[i, j
] = m[i, k] + m[k+1, j ] + pi-1pk pj

 Step 3: Computing the optimal cost

 Algorithm: next slide
 First computes costs for chains of length l=1
 Then for chains of length l=2,3, … and so on
 Computes the optimal cost bottom-up

14
 Dynamic Programming Approach (Contd.)
 Input: Array p[0…n] containing matrix dimensions
and n
 Result: Minimum-cost table m and split table s

Algorithm MatrixChainOrder(p[ ], n)
{
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] + p[i-1] p[k] p[j];
if (q < m[i, j]) then
{ m[i, j] := q;
s[i, j] := k;
}
}
return m and s
}
15
 Example

 The algorithm takes O(n3) time and requires

O(n2) space.
 Example:
 Consider the following six matrix problem.

Matrix A1 A2 A3 A4 A5 A6
Dimensions 10x20 20x5 5x15 15x50 50x10 10x15

 The problem therefore can be phrased as one

of filling in the following table representing the
values m.

i\j 1 2 3 4 5 6
1 0
2 0
3 0
4 0
5 0
6 0
16
 Example (Contd.)

 Chains of length 2 are easy, as there is no

minimization required, so
 m[i, i+1] = pi-1pipi+1

 m[1, 2] = 10x20x5 = 1000

 m[2, 3] = 20x5x15 = 1500
 m[3, 4] = 5x15x50 = 3750
 m[4, 5] = 15x50x10 = 7500
 m[5, 6] = 50x10x15 = 7500

i\j 1 2 3 4 5 6
1 0 1000
2 0 1500
3 0 3750
4 0 7500
5 0 7500
6 0
17
 Example (Contd.)
 Chains of length 3 require some minimization –
but only one each.
 m[1,3]=min{(m[1,1]+m[2,3]+p0p1p3),(m[1,2]+m[3,3]+p0p2p3)}
= min{(0+1500+10x20x15), (1000+0+10x5x15)}
= min { 4500, 1750 } = 1750
 m[2,4]=min{(m[2,2]+m[3,4]+p1p2p4),(m[2,3]+m[4,4]+p1p3p4)}
= min{(0+3750+20x5x50), (1500+0+20x15x50)}
= min { 8750, 16500 } = 8750
 m[3,5]=min{(m[3,3]+m[4,5]+p2p3p5),(m[3,4]+m[5,5]+p2p4p5)}
= min{(0+7500+5x15x10), (3750+0+5x50x10)}
= min { 8250, 6250 } = 6250
 m[4,6]=min{(m[4,4]+m[5,6]+p3p4p6),(m[4,5]+m[6,6]+p3p5p6)}
= min{(0+7500+15x50x15), (7500+0+15x10x15)}
= min { 18750, 9750 } = 9750

i\j 1 2 3 4 5 6
1 0 1000 1750
2 0 1500 8750
3 0 3750 6250
4 0 7500 9750
5 0 7500
6 0
18
 Example (Contd.)
 m[1,4]=min{(m[1,1]+m[2,4]+p0p1p4),(m[1,2]+m[3,4]+p0p2p4),
(m[1,3]+m[4,4]+p0p3p4)}
= min{(0+8750+10x20x50), (1000+3750+10x5x50),
(1750+0+10x15x50)}
= min { 18750, 7250, 9250 } = 7250
 m[2,5]=min{(m[2,2]+m[3,5]+p1p2p5),(m[2,3]+m[4,5]+p1p3p5),
(m[2,4]+m[5,5]+p1p4p5)}
= min{(0+6250+20x5x10), (1500+7500+20x15x10),
(8750+0+20x50x10)}
= min { 7250, 12000, 18750 } = 7250
 m[3,6]=min{(m[3,3]+m[4,6]+p2p3p6),(m[3,4]+m[5,6]+p2p4p6),
(m[3,5]+m[6,6]+p2p5p6)}
= min{(0+9750+5x15x15), (3750+7500+5x50x15),
(6250+0+5x10x15)}
= min { 10875, 15000, 7000 } = 7000
i\j 1 2 3 4 5 6
1 0 1000 1750 7250
2 0 1500 8750 7250
3 0 3750 6250 7000
4 0 7500 9750
5 0 7500
6 0
19
 Example (Contd.)
 m[1,5]=min{(m[1,1]+m[2,5]+p0p1p5),(m[1,2]+m[3,5]+p0p2p5),
(m[1,3]+m[4,5]+p0p3p5),(m[1,4]+m[5,5]+p0p4p5)}
= min{(0+7250+10x20x10), (1000+6250+10x5x10),
(1750+7500+10x15x10), (7250+0+10x50x10)}
= min { 9250, 7750, 10750, 12250 } = 7750
 m[2,6]=min{(m[2,2]+m[3,6]+p1p2p6),(m[2,3]+m[4,6]+p1p3p6),
(m[2,4]+m[5,6]+p1p4p6),(m[2,5]+m[6,6]+p1p5p6)}
= min{(0+7000+20x5x15), (1500+9750+20x15x15),
(8750+7500+20x50x15), (7250+0+20x10x15)}
= min { 8500, 15750, 31,250, 10250 } = 8500
 m[1,6]=min{(m[1,1]+m[2,6]+p0p1p6),(m[1,2]+m[3,6]+p0p2p6),
(m[1,3]+m[4,6]+p0p3p6),(m[1,4]+m[5,6]+p0p4p6),
(m[1,5]+m[6,6]+p0p5p6)}
= min{(11500, 8750, 13750, 22250, 9250 } = 8750

i\j 1 2 3 4 5 6
1 0 1000 1750 7250 7750 8750
2 0 1500 8750 7250 8500
3 0 3750 6250 7000
4 0 7500 9750
5 0 7500
6 0
20
 Dynamic Programming Approach (Contd.)
 The algorithm takes O(n3) time and requires O(n2)
space.
 Step 4: Constructing an optimal solution
 Our algorithm computes the minimum-cost
table m and the split table s.
 The optimal solution can be constructed from
the split table s.
 Each entry s[i, j ]=k shows where to split the
product Ai Ai+1 … Aj for the minimum cost.
 The following recursive procedure prints an
optimal parenthesization.

Algorithm PrintOptimalPerens(s, i, j)
{ if (i=j) then
Print “A”i;
else
{ Print “(“;
PrintOptimalPerens(s, i, s[i,j]);
PrintOptimalPerens(s, s[i,j]+1, j);
Print “)”;
}
21
}
 Example (Contd.)
 So far we have decided that the best way to
parenthesize the expression results in 8750
multiplication.
 But we have not addressed how we should
actually DO the multiplication to achieve the
value.
 However, look at the last computation we did –
the minimum value came from computing

A = (A1A2)(A3A4A5A6)

 Therefore in an auxiliary array, we store value

s[1,6]=2.
 In general, as we proceed with the algorithm, if
we find that the best way to compute Ai..j is as
Ai..j = Ai..kA(k+1)..j

then we set
s[i, j] = k.

 Then from the values of k we can reconstruct

the optimal way to parenthesize the expression.

22
 Example (Contd.)
 If we do this then we find that the s array looks
like this:
i\j 1 2 3 4 5 6
1 1 1 2 2 2 2
2 2 2 2 2 2
3 3 3 4 5
4 4 4 5
5 5 5
6 6
 We already know that we must compute A1..2
and A3..6.
 By looking at s[3,6] = 5, we discover that we
should compute A3..6 as A3..5A6..6 and then by
seeing that s[3,5] = 4, we get the final
parenthesization

A = ((A1A2)(((A3A4)A5)A6)).

 And quick check reveals that this indeed takes

the required 8750 multiplications.

23