Dept.
of ECE, TKU
Fall, 2023
Opportunities and Challenges of The AI Era
Chapter 4
Dynamic Programming
© 2023 by Jiann-Chyi Rau
Dept. of ECE, TKU
Fall, 2023
Optimization Problems
• Find an optimal solution (maybe not unique)
from many possible solutions
• Applications
– Electronic design automation (EDA) –
floorplan, placement, and routing…
– Control, operation, our daily lives…
© 2023 by Jiann-Chyi Rau Algorithms 4-2
Dept. of ECE, TKU
Fall, 2023
Dynamic Programming (DP) (1/3)
• Divide the problem into subproblems which
overlap (subproblems share subproblems)
– Unlike the divide-and-conquer approach where
subproblems are disjoint, e.g. the maximum-
subarray problem
• Solve each subproblem “just once” and
store the result (best solution) in a table
– “Programming” means using (combining) a
tabular solution to an optimal problem
© 2023 by Jiann-Chyi Rau Algorithms 4-3
Dept. of ECE, TKU
Fall, 2023
Dynamic Programming (DP) (2/3)
Matrix Chain Multiplication: [1][2][3][4]
© 2023 by Jiann-Chyi Rau Algorithms 4-4
Dept. of ECE, TKU
Fall, 2023
Dynamic Programming (DP) (3/3)
• Four steps:
1. Characterize the structure of an optimal
solution (optimal substructure)
2. Recursively define the value of an optimal
solution
3. Compute the value of an optimal solution
(either bottom-up or top-down)
4. Construct an optimal solution from step 3.
© 2023 by Jiann-Chyi Rau Algorithms 4-5
Dept. of ECE, TKU
Fall, 2023
Rod Cutting (1/3)
• Given a rod of length n inches and a table of
prices pi for i = 1, 2,.., n, determine the
maximum revenue rn obtainable by cutting
up the rod and selling the prices. Note that
rod lengths are always an integral number
of inches.
© 2023 by Jiann-Chyi Rau Algorithms 4-6
Dept. of ECE, TKU
Fall, 2023
Rod Cutting (2/3)
A sample price table for rods
– E.g. n = 4 Optimal
No cutting
© 2023 by Jiann-Chyi Rau Algorithms 4-7
Dept. of ECE, TKU
Fall, 2023
Rod Cutting (3/3)
• There are 2n-1 different ways to cut up a rod
of length n
– Brute force solution is exponential complexity!!
– How can we do better?
© 2023 by Jiann-Chyi Rau Algorithms 4-8
Dept. of ECE, TKU
Fall, 2023
Optimal Substructure (1/3)
• Divide the optimization problem into subproblems
– Let rn be the optimal revenue of length n
rn can be obtained by taking the maximum of
• pn: the price we get by not cutting
• p1 + rn-1: the maximum from a 1-inch rod and a n-1 inches rod
• p2 + rn-2: the maximum from a 2-inch rod and a n-2 inches rod
n-1 n-2 n-3 1 0
• ... n
•
n-1
pn-1 + r1 p1 + rn-1 n-2
rn = max(p1 + rn-1 , p2 + rn-2 ,…, pn-1 + r1 , pn )
2
• n different possibilities 1
© 2023 by Jiann-Chyi Rau Algorithms 4-9
Dept. of ECE, TKU
Fall, 2023
Optimal Substructure (2/3)
Optimal solution to original problem results from
incorporating solutions to smaller subproblems
• For rod cutting, if rn is optimal solution for length n,
then the solution to its subproblem (rn-i) is also an
optimal cut of length n-i
– Proof. If rn-i is not an optimal cut, then replace it by an
optimal cut violate the assumption that rn is an
optimal cut.
rn rn-i pi
also an optimal solution last cut length = i
© 2023 by Jiann-Chyi Rau Algorithms 4-10
Dept. of ECE, TKU
Fall, 2023
Optimal Substructure (3/3)
– E.g. Optimal solution to n = 8 is r8 = r2 + r6 = 22
• r6 = 17 is optimal solution to subproblem n = 6
• r2 = 5 is optimal solution to subproblem n = 2
• Not reversible
– Combine optimal solutions
may not give
an optimal solution
– r2 + r2 + r2 + r2 = 20 < 22
© 2023 by Jiann-Chyi Rau Algorithms 4-11
Dept. of ECE, TKU
Fall, 2023
Recursive Solution
• How to know what is the last cut i during
the optimization process?
– Try all possible values of last cuts and find the
optimal solution
• Recursive version of the equation for rn
© 2023 by Jiann-Chyi Rau Algorithms 4-12
Dept. of ECE, TKU
Fall, 2023
Computation of Optimal Value (1/2)
• A direct implementation: top-down
recursive approach
© 2023 by Jiann-Chyi Rau Algorithms 4-13
Dept. of ECE, TKU
Fall, 2023
Computation of Optimal Value (2/2)
• It work, but inefficiently
– Call itself repeatedly, even on subproblems
already solved
– E.g. n = 4, solve the subproblem for
• size 2 twice
• size 1 four times
• size 0 eight times
© 2023 by Jiann-Chyi Rau Algorithms 4-14
Dept. of ECE, TKU
Fall, 2023
Complexity Analysis
• T(n) = number of calls to CUT-ROD of size
n
T(n) = 2n , exponential growth!!
© 2023 by Jiann-Chyi Rau Algorithms 4-15
Dept. of ECE, TKU
Fall, 2023
Top-Down Dynamic Programming (1/2)
• Still top-down recursive, but store each
result in array r[n] guarantee that each
subproblem is solved “just once”
– Memoization
// initialize r
© 2023 by Jiann-Chyi Rau Algorithms 4-16
Dept. of ECE, TKU
Fall, 2023
Top-Down Dynamic Programming (2/2)
// modify recur_cut_rod
// r[n] has been solved n-1 n-2 n-3 1 0
Top n
n-1
n-2
Down 1
// memoization
© 2023 by Jiann-Chyi Rau Algorithms 4-17
Dept. of ECE, TKU
Fall, 2023
Bottom-Up Dynamic Programming
• Sort subproblems by size
j
– Solve smaller subproblems first
j-i
vertex labels for sizes
© 2023 by Jiann-Chyi Rau Algorithms 4-18
Dept. of ECE, TKU
Fall, 2023
Time Complexity
• Both (top-down and bottom-up) running
time Θ(n2)
– Doubly-nested loop structure for bottom-up
– Aggregate analysis for top-down (shall see later)
© 2023 by Jiann-Chyi Rau Algorithms 4-19
Dept. of ECE, TKU
Fall, 2023
Reconstruct Optimal Solution (1/2)
• Modify BOTTOM-UP-CUT-ROD
– s[j] = optimal length of first piece to cut for rod size n
© 2023 by Jiann-Chyi Rau Algorithms 4-20
Dept. of ECE, TKU
Fall, 2023
Reconstruct Optimal Solution (2/2)
• Print size s[n], then continue with n = n – s[n]
© 2023 by Jiann-Chyi Rau Algorithms 4-21
Dept. of ECE, TKU
Fall, 2023
Inspect (1/2)
• Four steps of dynamic programming
1. Characterize the structure of an optimal
solution (optimal substructure)
How to solve a smaller problem?
What is the last choice in the optimal solution?
2. Recursively define the value of an optimal
solution
Search all possibilities
© 2023 by Jiann-Chyi Rau Algorithms 4-22
Dept. of ECE, TKU
Fall, 2023
Inspect (2/2)
3. Compute the value of an optimal solution
(either bottom-up or top-down)
Memoize solutions to many overlapping
subproblems
4. Construct an optimal solution from step 3.
© 2023 by Jiann-Chyi Rau Algorithms 4-23
Dept. of ECE, TKU
Fall, 2023
The Knapsack Problem (1/4)
• Given n items of know weights (positive
integers) w1, w2, …, wn and values v1, v2, …,
vn and a knapsack of capacity W (positive
integers), find the most valuable subset of
the items that fit into the knapsack.
© 2023 by Jiann-Chyi Rau Algorithms 4-24
Dept. of ECE, TKU
Fall, 2023
The Knapsack Problem (2/4)
• Let F(i, j) be the value of an optimal
solution to the first i items fitting into the
knapsack of capacity j
– max{F(i-1, j), vi+F(i-1, j-wi)} if j-wi 0
– F(i-1, j) if j-wi < 0
– Initially, F(0, j) = F(i, 0) = 0 for all i, j 0
Time complexity: Θ(nW)
© 2023 by Jiann-Chyi Rau Algorithms 4-25
Dept. of ECE, TKU
Fall, 2023
The Knapsack Problem (3/4)
• Reconstruct optimal solution
– take[i, j] = 1, take the i-th item for j
• if j-wi 0 and vi+F(i-1, j-wi) > F(i-1, j)
– take[i, j] = 0, do not take the i-th item for j
• if j-wi < 0
• if j-wi 0 and vi+F(i-1, j-wi) ≤ F(i-1, j)
© 2023 by Jiann-Chyi Rau Algorithms 4-26
Dept. of ECE, TKU
Fall, 2023
The Knapsack Problem (4/4)
• E.g. n = 5 and W =10,
w[5] = {3, 4, 2, 1, 5}
v[5] = {5, 10, 2, 4, 8}
© 2023 by Jiann-Chyi Rau Algorithms 4-27
Dept. of ECE, TKU
Fall, 2023
The LCS Problem (1/2)
• The Longest Common Subsequence (LCS)
problem
– Given 2 sequences, X = <x1, …, xm> and Y =
<y1, …, yn> , find a subsequence common to
both whose length is longest
• Subsequence does not have to be consecutive,
but has to be in order
© 2023 by Jiann-Chyi Rau Algorithms 4-28
Dept. of ECE, TKU
Fall, 2023
The LCS Problem (2/2)
– E.g. (a) The bottom is a subsequence to the top
(b)
S1=ACCGGTCGAGTGCGCGGAAGCCGGCCGAA
S2=GTCGTTCGGAATGCCGTTGCTCTGTAAA
LCS=GTCGT CGGAA GCCG GC C G AA
© 2023 by Jiann-Chyi Rau Algorithms 4-29
Dept. of ECE, TKU
Fall, 2023
Brute Force Approach
• For every subsequence of X, check whether
it is a subsequence of Y
• Time complexity: Θ(n·2m)
– 2m subsequences of X to check
– Each subsequence take Θ(n) time to check,
scanning Y for first letter, from there for second
one, and so on…
• How can we do better?
© 2023 by Jiann-Chyi Rau Algorithms 4-30
Dept. of ECE, TKU
Fall, 2023
DP--Optimal Substructure (1/2)
• Notation:
– Xi = prefix <x1, …, xi>
– Yj = prefix <y1, …, yj>
[Theorem 4-1 ] Let Z = <z1, …, zk> be any LCS of X
= <x1, …, xm> and Y = <y1, …, yn>
(a) If xm = yn, then zk = xm = yn and Zk-1 is an LCS of Xm-1
and Yn-1
(b) If xm ≠ yn , then zk ≠ xm implies Z is an LCS of Xm-1 and
Y
(c) If xm ≠ yn , then zk ≠ yn implies Z is an LCS of X and
Yn-1
© 2023 by Jiann-Chyi Rau Algorithms 4-31
Dept. of ECE, TKU
Fall, 2023
DP--Optimal Substructure (2/2)
[Proof] If Z is an LCS of X and Y, and Z contains
a subsequence Z’, then Z’ must be LCS of
prefixes of X and Y; otherwise, if Z’ is not LCS,
replace it by LCS so Z is not longest
Z Z’ match
also an LCS
© 2023 by Jiann-Chyi Rau Algorithms 4-32
Dept. of ECE, TKU
Fall, 2023
DP--Recursive Solution
• Let c[i, j] = LCS length of Xi and Yj
© 2023 by Jiann-Chyi Rau Algorithms 4-33
Dept. of ECE, TKU
Fall, 2023
DP--Compute Optimal Solution (1/2)
Time complexity: Θ(mn)
© 2023 by Jiann-Chyi Rau Algorithms 4-34
Dept. of ECE, TKU
Fall, 2023
DP--Compute Optimal Solution (2/2)
• E.g. Let X = <A, B, C, B, D, A, B> and
Y = <B, D, C, A, B, A>
b[i, j] points to
optimal solution of subproblem
© 2023 by Jiann-Chyi Rau Algorithms 4-35
Dept. of ECE, TKU
Fall, 2023
DP--Reconstruct Optimal Solution (1/2)
• Construct answer in reverse order
– Time complexity: O(m+n)
© 2023 by Jiann-Chyi Rau Algorithms 4-36
Dept. of ECE, TKU
Fall, 2023
DP--Reconstruct Optimal Solution (2/2)
• E.g. LCS = BCBA
© 2023 by Jiann-Chyi Rau Algorithms 4-37
Dept. of ECE, TKU
Fall, 2023
Matrix Multiplication (1/2)
• We can multiply two matrices A and B only
if they are compatible: the number of
columns of A must equal the number of
rows of B
– If A is a p x q matrix and B is a q x r matrix, the
resulted matrix C = AB is a p x r matrix
– The time to compute C is dominated by the
number of scalar multiplications, which is pqr
© 2023 by Jiann-Chyi Rau Algorithms 4-38
Dept. of ECE, TKU
Fall, 2023
Matrix Multiplication (2/2)
//A.row is p
//B.column is r
//A.column is q
© 2023 by Jiann-Chyi Rau Algorithms 4-39
Dept. of ECE, TKU
Fall, 2023
Matrix-Chain Multiplication (1/3)
• Given a sequence (chain) <A1, A2, …, An>
of n matrices to be multiplied, and compute
the product
A1A2…An
Parenthesize the chain to resolve all ambiguities
Associative such that all parenthesizations yield
the same product
© 2023 by Jiann-Chyi Rau Algorithms 4-40
Dept. of ECE, TKU
Fall, 2023
Matrix-Chain Multiplication (2/3)
• A product of matrices is fully parenthesized if
(a) a single matrix, or
(b) the product of two fully parenthesized matrix
products
– E.g. Given the chain of matrices <A1, A2, A3, A4>,
there are five distinct ways to parenthesize it
(1) (A1(A2( A3 A4)))
(2) (A1(( A2A3)A4))
(3) ((A1A2)(A3 A4))
(4) ((A1(A2A3))A4)
(5) (((A1A2)A3)A4)
© 2023 by Jiann-Chyi Rau Algorithms 4-41
Dept. of ECE, TKU
Fall, 2023
Matrix-Chain Multiplication (3/3)
• Different parenthesizations incur different
costs
– E.g. Consider <A1, A2, A3>, suppose that the
dimensions of the matrices are 10 x 100,
100 x 5, and 5 x 50
(a) ((A1A2)A3) performs 10 x 100 x 5 + 10 x 5 x 50 =
7,500 scalar multiplications
(b) (A1(A2A3)) performs 100 x 5 x 50 + 10 x 100 x 50 =
75,000 scalar multiplications
© 2023 by Jiann-Chyi Rau Algorithms 4-42
Dept. of ECE, TKU
Fall, 2023
The 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 x pi , fully parenthesize the
product A1, A2, …, An in a way that minimizes
the number of scalar multiplications.
– Only determine an order for multiplying matrices
instead of actually multiplying matrices
© 2023 by Jiann-Chyi Rau Algorithms 4-43
Dept. of ECE, TKU
Fall, 2023
The Number of Parenthesizations
• Let P(n) be the number of alternative
parenthesizations of a sequence of n matrices
<A1, A2, …, An>
– P(n) = Ω(2n)
• The brute-force method of exhaustive search makes for
a poor strategy when determining how to optimally
parenthesize a matrix chain
• How can we do better?
© 2023 by Jiann-Chyi Rau Algorithms 4-44
Dept. of ECE, TKU
Fall, 2023
An Optimal Parenthesization
• Suppose to optimally parenthesize
Ai Ai+1… Aj, we split the product between Ak
and Ak+1
Then the way we parenthesize the “prefix”
subchain Ai Ai+1… Ak within this optimal
parenthesization of Ai Ai+1… Aj must be an
optimal parenthesization of Ai Ai+1… Ak
Similar observation holds for “postfix”
subchain
© 2023 by Jiann-Chyi Rau Algorithms 4-45
Dept. of ECE, TKU
Fall, 2023
A Recursive Solution
• Let m[i, j] be the minimum number of scalar
multiplications needed to compute the
matrix Ai…j, where 1 ≤ i ≤ j ≤ n
© 2023 by Jiann-Chyi Rau Algorithms 4-46
Dept. of ECE, TKU
Fall, 2023
Compute the Optimal Cost (1/2)
//i + (l – 1) ≤ n
Time complexity: Θ(n3)
© 2023 by Jiann-Chyi Rau Algorithms 4-47
Dept. of ECE, TKU
Fall, 2023
Compute the Optimal Cost (2/2)
• E.g.
l=6
l=1
© 2023 by Jiann-Chyi Rau Algorithms 4-48
Dept. of ECE, TKU
Fall, 2023
Reconstruct an Optimal Solution
© 2023 by Jiann-Chyi Rau Algorithms 4-49
Dept. of ECE, TKU
Fall, 2023
Bottom-Up vs. Top-Down (1/3)
• Bottom-up iterative approach
– Start with recursive divide-and-conquer
algorithm
– Find which solutions are needed for computing
a subproblem
– Solve subproblems from smaller ones
© 2023 by Jiann-Chyi Rau Algorithms 4-50
Dept. of ECE, TKU
Fall, 2023
Bottom-Up vs. Top-Down (2/3)
• Top-down recursive approach (with
memorization)
– Start with recursive divide-and-conquer
algorithm
– Keep top-down approach of original algorithm
– Solve solutions to subproblems in a table
– Recur a subproblem only if the solution is not
already in table
© 2023 by Jiann-Chyi Rau Algorithms 4-51
Dept. of ECE, TKU
Fall, 2023
Bottom-Up vs. Top-Down (3/3)
If all subproblems must be solved at least
once
Bottom-up dynamic programming is better, less
overhead for recursion
If many (but not all) subproblems need NOT
be solved
Top-down dynamic programming is better,
since it computes only those required (beyond the
scope)
© 2023 by Jiann-Chyi Rau Algorithms 4-52
Dept. of ECE, TKU
Fall, 2023
Conclusions (1/2)
• Elements of dynamic Programming
– Optimal substructure
• The solutions to the subproblems used within the
optimal solution must themselves be optimal
– Overlapping subproblems
• Recursively solve the same subproblems over and
over again
Divide-and-conquer generates new subproblems
(e.g. merge sort is not dynamic programming)
© 2023 by Jiann-Chyi Rau Algorithms 4-53
Dept. of ECE, TKU
Fall, 2023
Conclusions (2/2)
• When to use dynamic programming
– Objects are linearly ordered, cannot rearranged
• E.g. Matrices in a chain, characters in a string
Suitable for
contiguous substrings of a n-character string
Not suitable for
n! permutation of an n-element set
2n subsets of an n-element set
© 2023 by Jiann-Chyi Rau Algorithms 4-54
Dept. of ECE, TKU
Fall, 2023
Notes
© 2023 by Jiann-Chyi Rau Algorithms 4-55
Dept. of ECE, TKU
Fall, 2023
Notes
© 2023 by Jiann-Chyi Rau Algorithms 4-56
