Dynamic Programming

動態規劃 (1)
5.1
Algorithm Design and Analysis
演算法設計與分析
Yun-Nung (Vivian) Chen 陳縕儂
(Slides modified from Hsu-Chun Hsiao) [Link]
 Outline
• Dynamic Programming
• DP #1: Rod Cutting
• DP #2: Stamp Problem
• DP #3: Matrix-Chain Multiplication
• DP #4: Weighted Interval Scheduling
• DP #5: Sequence Alignment Problem
• Longest Common Subsequence (LCS) / Edit Distance
• Viterbi Algorithm
• Space Efficient Algorithm
• DP #6: Knapsack Problem
• 0/1 Knapsack
• Unbounded Knapsack
• Multidimensional Knapsack
• Fractional Knapsack

2
 動腦一下 – 囚犯問題
• 有100個死囚，隔天執行死刑，典獄長開恩給他們一個存活的機會。
• 當隔天執行死刑時，每人頭上戴一頂帽子(黑或白)排成一隊伍，在死刑執行前，由隊
伍中最後的囚犯開始，每個人可以猜測自己頭上的帽子顏色(只允許說黑或白)，猜對
則免除死刑，猜錯則執行死刑。
• 若這些囚犯可以前一天晚上先聚集討論方案，是否有好的方法可以使總共存活的囚
犯數量期望值最高？

3
 猜測規則
• 囚犯排成一排，每個人可以看到前面所有人的帽子，但看不到自己及後面囚犯的。
• 由最後一個囚犯開始猜測，依序往前。
• 每個囚犯皆可聽到之前所有囚犯的猜測內容。
Example: 奇數者猜測內容為前面一位的帽子顏色 → 存活期望值為75人

有沒有更多人可以存活的好策略?

……

4
 Algorithm Design Strategy
• Do not focus on “specific algorithms”
• But “some strategies” to “design” algorithms

• First Skill: Divide-and-Conquer (各個擊破/分治法)

• Second Skill: Dynamic Programming (動態規劃)

5
 Dynamic Programming
Textbook Chapter 15 – Dynamic Programming
Textbook Chapter 15.3 – Elements of dynamic programming

Slides modified from Prof. Hsu-Chun Hsiao 6

 What is Dynamic Programming?
• Dynamic programming, like the divide-and-conquer method, solves
problems by combining the solutions to subproblems.
• 用空間換取時間
• 讓走過的留下痕跡
• “Dynamic”: time-varying
• “Programming”: a tabular method

Dynamic Programming: planning over time

Slides modified from Prof. Hsu-Chun Hsiao 7

 Algorithm Design Paradigms

• Divide-and-Conquer • Dynamic Programming

• partition the problem into • partition the problem into dependent
independent or disjoint or overlapping subproblems
subproblems • avoid recomputation
• repeatedly solving the common ✓ Top-down with memoization
subsubproblems ✓ Bottom-up method
→ more work than necessary

Slides modified from Prof. Hsu-Chun Hsiao 8

 Dynamic Programming Procedure
• Apply four steps
1. Characterize the structure of an optimal solution
2. Recursively define the value of an optimal solution
3. Compute the value of an optimal solution, typically in a bottom-up fashion
4. Construct an optimal solution from computed information

Slides modified from Prof. Hsu-Chun Hsiao 9

 Rethink Fibonacci Sequence
• Fibonacci sequence (費波那契數列) Fibonacci(n)
if n < 2 // base case
• Base case: F(0) = F(1) = 1 return 1
// recursive case
• Recursive case: F(n) = F(n-1) + F(n-2) return Fibonacci(n-1)+Fibonacci(n-2)
F(5)
✓F(3) was computed twice
F(4) F(3)
✓F(2) was computed 3 times
F(3) F(2) F(2) F(1)

F(2) F(1) F(1) F(0) F(1) F(0)

F(1) F(0) Calling overlapping subproblems result in poor efficiency

Slides modified from Prof. Hsu-Chun Hsiao 10
 Fibonacci Sequence
Top-Down with Memoization
• Solve the overlapping subproblems recursively with memoization
• Check the memo before making the calls

F(5) 備忘錄

F(4) F(3)

F(3) F(2)
n 0 1 2 3 4 5
F(n) 1 1 ?
2 ?
3 ?
5 8?
F(2) F(1)

F(1) F(0)
Avoid recomputation of the same subproblems using memo

Slides modified from Prof. Hsu-Chun Hsiao 11

 Fibonacci Sequence
Top-Down with Memoization
Memoized-Fibonacci(n)
// initialize memo (array a[])
a[0] = 1
a[1] = 1
for i = 2 to n
a[i] = 0
return Memoized-Fibonacci-Aux(n, a)

Memoized-Fibonacci-Aux(n, a)
if a[n] > 0
return a[n]
// save the result to avoid recomputation
a[n] = Memoized-Fibonacci-Aux(n-1, a) + Memoized-Fibonacci-Aux(n-2, a)
return a[n]

Slides modified from Prof. Hsu-Chun Hsiao 12

 Fibonacci Sequence
Bottom-Up Method
• Building up solutions to larger and larger subproblems

F(5)
Bottom-Up-Fibonacci(n)
if n < 2
F(4) return 1
a[0] = 1
F(3) a[1] = 1
for i = 2 … n
a[i] = a[i-1] + a[i-2]
F(2)
return a[n]

F(1)

F(0) Avoid recomputation of the same subproblems

Slides modified from Prof. Hsu-Chun Hsiao 13

 Optimization Problem
• Principle of Optimality
• Any subpolicy of an optimum policy must itself be an optimum policy with
regard to the initial and terminal states of the subpolicy
• Two key properties of DP for optimization
• Overlapping subproblems
• Optimal substructure – an optimal solution can be constructed from optimal
solutions to subproblems
✓ Reduce search space (ignore non-optimal solutions)

If the optimal substructure (principle of optimality) does not hold, then it is

incorrect to use DP

Slides modified from Prof. Hsu-Chun Hsiao 14

 Optimal Substructure Example
• Shortest Path Problem
• Input: a graph where the edges have positive costs
• Output: a path from S to T with the smallest cost
The path costing CS→M+ CM→T is the shortest path from S to T
→ The path with the cost CS→M must be a shortest path from S to M

Taipei (T)
CM→T
CS→M

M
C’S→M < CS→M?

Proof by “Cut-and-Paste” argument (proof by contradiction):

Suppose that it exists a path with smaller cost C’S→M, then we can
Tainan (S)
“cut” CS→M and “paste” C’S→M to make the original cost smaller
Slides modified from Prof. Hsu-Chun Hsiao 15
 DP#1: Rod Cutting
Textbook Chapter 15.1 – Rod Cutting

Slides modified from Prof. Hsu-Chun Hsiao 16

 Rod Cutting Problem
• Input: a rod of length 𝑛 and a table of prices 𝑝𝑖 for 𝑖 = 1, … , 𝑛
length 𝑖 (m) 1 2 3 4 5
price 𝑝𝑖 1 5 8 9 10

• Output: the maximum revenue 𝑟𝑛 obtainable by cutting up the rod and

selling the pieces

4m

2m
2m

Slides modified from Prof. Hsu-Chun Hsiao 17

 Brute-Force Algorithm
length 𝑖 (m) 1 2 3 4 5
price 𝑝𝑖 1 5 8 9 10

• A rod with the length = 4

4m →9
3m 1m →8+1=9
2m 2m → 5 + 5 = 10
1m 3m →1+8=9
2m 1m 1m →5+1+1=7
1m 2m 1m →1+5+1=7
1m 1m 2m →1+1+5=7
1m 1m 1m 1m →1+1+1+1=4

Slides modified from Prof. Hsu-Chun Hsiao 18

 Brute-Force Algorithm
length 𝑖 (m) 1 2 3 4 5
price 𝑝𝑖 1 5 8 9 10

• A rod with the length = 𝑛

• For each integer position, we can choose “cut” or “not cut”

• There are 𝑛 – 1 positions for consideration
• The total number of cutting results is 2𝑛−1 = Θ 2𝑛−1

[Link]

Slides modified from Prof. Hsu-Chun Hsiao 19

 𝑟𝑛 : the maximum revenue
Recursive Thinking obtainable for a rod of
length 𝑛
• We use a recursive function to solve the subproblems
• If we know the answer to the subproblem, can we get the answer to
the original problem?

𝑟𝑖 𝑟𝑛−𝑖

no cut
cut at the i-th position (from left to right)

• Optimal substructure – an optimal solution can be constructed from

optimal solutions to subproblems
Slides modified from Prof. Hsu-Chun Hsiao 20
 Recursive Algorithms
• Version 1

no cut
cut at the i-th position (from left to right)

• Version 2
• try to reduce the number of subproblems → focus on the left-most cut

𝑝𝑖 𝑟𝑛−𝑖

left-most value maximum value obtainable from

the remaining part

Slides modified from Prof. Hsu-Chun Hsiao 21

 Recursive Procedure
• Focus on the left-most cut
• assume that we always cut from left to right → the first cut

optimal solution optimal solution to subproblems

𝑝1 𝑟𝑛−1

𝑝2 𝑟𝑛−2
:
:

𝑝𝑖 𝑟𝑛−𝑖

Rod cutting problem has optimal substructure

Slides modified from Prof. Hsu-Chun Hsiao 22
 Naïve Recursion Algorithm

Cut-Rod(p, n)
// base case
if n == 0
return 0
// recursive case
q = -∞
for i = 1 to n
q = max(q, p[i] + Cut-Rod(p, n - i))
return q

• 𝑇 𝑛 = time for running Cut-Rod(p, n)

Slides modified from Prof. Hsu-Chun Hsiao 23

 Naïve Recursion Algorithm
• Rod cutting problem
CR(4)
Cut-Rod(p, n)
// base case
if n == 0 CR(3) CR(2) CR(1) CR(0)
return 0
// recursive case
q = -∞ CR(2) CR(1) CR(0) CR(1) CR(0) CR(0)
for i = 1 to n
q = max(q, p[i] + Cut-Rod(p, n - i)) CR(0)
CR(1) CR(0) CR(0)
return q

CR(0)

Calling overlapping subproblems result in poor efficiency

Slides modified from Prof. Hsu-Chun Hsiao 24

 Dynamic Programming
• Idea: use space for better time efficiency
• Rod cutting problem has overlapping subproblems and optimal
substructures → can be solved by DP
• When the number of subproblems is polynomial, the time complexity is
polynomial using DP
• DP algorithm
• Top-down: solve overlapping subproblems recursively with memoization
• Bottom-up: build up solutions to larger and larger subproblems

Slides modified from Prof. Hsu-Chun Hsiao 25

 Dynamic Programming

• Top-Down with Memoization • Bottom-Up with Tabulation

• Solve recursively and memo the • Fill the table from small to large
subsolutions (跳著填表) • Suitable that each small problem
• Suitable that not all subproblems should be solved
should be solved

f(0) f(1) f(2) … f(n) f(0) f(1) f(2) … f(n)

Slides modified from Prof. Hsu-Chun Hsiao 26

 Algorithm for Rod Cutting Problem
Top-Down with Memoization
Memoized-Cut-Rod(p, n)
// initialize memo (an array r[] to keep max revenue)
r[0] = 0
for i = 1 to n
r[i] = -∞ // r[i] = max revenue for rod with length = i
return Memorized-Cut-Rod-Aux(p, n, r)

Memoized-Cut-Rod-Aux(p, n, r)
if r[n] >= 0
return r[n] // return the saved solution
q = -∞
for i = 1 to n
q = max(q, p[i] + Memoized-Cut-Rod-Aux(p, n-i, r))
r[n] = q // update memo
return q

• 𝑇 𝑛 = time for running Memoized-Cut-Rod(p, n)

Slides modified from Prof. Hsu-Chun Hsiao 27
 Algorithm for Rod Cutting Problem
Bottom-Up with Tabulation

Bottom-Up-Cut-Rod(p, n)
r[0] = 0
for j = 1 to n // compute r[1], r[2], ... in order
q = -∞
for i = 1 to j
q = max(q, p[i] + r[j - i])
r[j] = q
return r[n]

• 𝑇 𝑛 = time for running Bottom-Up-Cut-Rod(p, n)

Slides modified from Prof. Hsu-Chun Hsiao 28

 Rod Cutting Problem
• Input: a rod of length 𝑛 and a table of prices 𝑝𝑖 for 𝑖 = 1, … , 𝑛
length 𝑖 (m) 1 2 3 4 5
price 𝑝𝑖 1 5 8 9 10

• Output: the maximum revenue 𝑟𝑛 obtainable and the list of cut pieces

4m

2m
2m

Slides modified from Prof. Hsu-Chun Hsiao 29

 Algorithm for Rod Cutting Problem
Bottom-Up with Tabulation
• Add an array to keep the cutting positions cut
Extended-Bottom-Up-Cut-Rod(p, n)
r[0] = 0
for j = 1 to n //compute r[1], r[2], ... in order
q = -∞
for i = 1 to j
if q < p[i] + r[j - i]
q = p[i] + r[j - i]
cut[j] = i // the best first cut for len j rod
r[i] = q
return r[n], cut

Print-Cut-Rod-Solution(p, n)
(r, cut) = Extended-Bottom-up-Cut-Rod(p, n)
while n > 0
print cut[n]
n = n – cut[n] // remove the first piece

Slides modified from Prof. Hsu-Chun Hsiao 30

 Dynamic Programming
• Top-Down with Memoization • Bottom-Up with Tabulation
F(5)
f(0) f(1) f(2) … f(n) f(0) f(1) f(2) … f(n)

F(4)

• Better when some subproblems F(3) • Better when all subproblems must
not be solved at all be solved at least once
• Solve only the required parts of F(2) • Typically outperform top-down
subproblems method by a constant factor
• No overhead for recursive calls
F(1)
• Less overhead for maintaining the table

F(0)

Slides modified from Prof. Hsu-Chun Hsiao 31

 Informal Running Time Analysis
• Approach 1: approximate via (#subproblems) * (#choices for each
subproblem)
• For rod cutting
• #subproblems = n
• #choices for each subproblem = O(n)
• → T(n) is about O(n2)
• Approach 2: approximate via subproblem graphs

Slides modified from Prof. Hsu-Chun Hsiao 32

 Subproblem Graphs
F(5)
• The size of the subproblem graph allows us to estimate the time
complexity of the DP algorithm
F(4)
• A graph illustrates the set of subproblems involved and how
subproblems depend on another 𝐺 = 𝑉, 𝐸 (E: edge, V: vertex) F(3)
• 𝑉 : #subproblems
• A subproblem is run only once F(2)
• |𝐸|: sum of #subsubproblems are needed for each subproblem
• Time complexity: linear to 𝑂( 𝐸 + 𝑉 ) F(1)
Top-down: Depth First Search
Graph Algorithm
F(0)
Bottom-up: Reverse Topological Sort (taught later)

Slides modified from Prof. Hsu-Chun Hsiao 33

 Dynamic Programming Procedure
1. Characterize the structure of an optimal solution
✓ Overlapping subproblems: revisit same subproblems
✓ Optimal substructure: an optimal solution to the problem contains within it
optimal solutions to subproblems
2. Recursively define the value of an optimal solution
✓ Express the solution of the original problem in terms of optimal solutions for
subproblems
3. Compute the value of an optimal solution
✓ Typically in a bottom-up fashion
4. Construct an optimal solution from computed information
✓ Step 3 and 4 may be combined

Slides modified from Prof. Hsu-Chun Hsiao 34

 Revisit DP for Rod Cutting Problem
1. Characterize the structure of an optimal solution
2. Recursively define the value of an optimal solution
3. Compute the value of an optimal solution
4. Construct an optimal solution from computed information

Slides modified from Prof. Hsu-Chun Hsiao 35

 Step 1: Characterize an OPT Solution
Rod Cutting Problem
Input: a rod of length 𝑛 and a table of prices 𝑝𝑖 for 𝑖 = 1, … , 𝑛
Output: the maximum revenue 𝑟𝑛 obtainable
• Step 1-Q1: What can be the subproblems?
• Step 1-Q2: Does it exhibit optimal structure? (an optimal solution can
be represented by the optimal solutions to subproblems)
• Yes. → continue
• No. → go to Step 1-Q1 or there is no DP solution for this problem

Slides modified from Prof. Hsu-Chun Hsiao 36

 Step 1: Characterize an OPT Solution
Rod Cutting Problem
Input: a rod of length 𝑛 and a table of prices 𝑝𝑖 for 𝑖 = 1, … , 𝑛
Output: the maximum revenue 𝑟𝑛 obtainable
• Step 1-Q1: What can be the subproblems?
• Subproblems: Cut-Rod(0), Cut-Rod(1), …, Cut-Rod(n-1)
• Cut-Rod(i): rod cutting problem with length-i rod
• Goal: Cut-Rod(n)
• Suppose we know the optimal solution to Cut-Rod(i), there are i cases:
• Case 1: the first segment in the solution has length 1
從solution中拿掉一段長度為1的鐵條, 剩下的部分是Cut-Rod(i-1)的最佳解
• Case 2: the first segment in the solution has length 2
從solution中拿掉一段長度為2的鐵條, 剩下的部分是Cut-Rod(i-2)的最佳解
:
• Case i: the first segment in the solution has length i
從solution中拿掉一段長度為i的鐵條, 剩下的部分是Cut-Rod(0)的最佳解

Slides modified from Prof. Hsu-Chun Hsiao 37

 Step 1: Characterize an OPT Solution
Rod Cutting Problem
Input: a rod of length 𝑛 and a table of prices 𝑝𝑖 for 𝑖 = 1, … , 𝑛
Output: the maximum revenue 𝑟𝑛 obtainable
• Step 1-Q2: Does it exhibit optimal structure? (an optimal solution can
be represented by the optimal solutions to subproblems)
• Yes. Prove by contradiction.

Slides modified from Prof. Hsu-Chun Hsiao 38

 Step 2: Recursively Define the Value of an
OPT Solution
Rod Cutting Problem
Input: a rod of length 𝑛 and a table of prices 𝑝𝑖 for 𝑖 = 1, … , 𝑛
Output: the maximum revenue 𝑟𝑛 obtainable
• Suppose we know the optimal solution to Cut-Rod(i), there are i cases:
• Case 1: the first segment in the solution has length 1
從solution中拿掉一段長度為1的鐵條, 剩下的部分是Cut-Rod(i-1)的最佳解
• Case 2: the first segment in the solution has length 2
從solution中拿掉一段長度為2的鐵條, 剩下的部分是Cut-Rod(i-2)的最佳解
:

• Case i: the first segment in the solution has length i

從solution中拿掉一段長度為i的鐵條, 剩下的部分是Cut-Rod(0)的最佳解

• Recursively define the value

Slides modified from Prof. Hsu-Chun Hsiao 39

 Step 3: Compute Value of an OPT Solution
Rod Cutting Problem
Input: a rod of length 𝑛 and a table of prices 𝑝𝑖 for 𝑖 = 1, … , 𝑛
Output: the maximum revenue 𝑟𝑛 obtainable
• Bottom-up method: solve smaller subproblems first
i 0 1 2 3 4 5 … n
r[i]

Bottom-Up-Cut-Rod(p, n)
r[0] = 0
for j = 1 to n // compute r[1], r[2], ... in order
q = -∞
for i = 1 to j
q = max(q, p[i] + r[j - i])
r[j] = q
return r[n]

Slides modified from Prof. Hsu-Chun Hsiao 40

 Step 4: Construct an OPT Solution by
Backtracking length 𝑖
price 𝑝𝑖
1
1
2
5
3
8
4
9
5
10

Rod Cutting Problem

Input: a rod of length 𝑛 and a table of prices 𝑝𝑖 for 𝑖 = 1, … , 𝑛
Output: the maximum revenue 𝑟𝑛 obtainable
• Bottom-up method: solve smaller subproblems first

i 0 1 2 3 4 5 … n
r[i] 0 1 5 8 10
cut[i] 0 1 2 3 2

Slides modified from Prof. Hsu-Chun Hsiao 41

 Step 4: Construct an OPT Solution by
Backtracking
Cut-Rod(p, n)
r[0] = 0
for j = 1 to n // compute r[1], r[2], ... in order
q = -∞
for i = 1 to j
if q < p[i] + r[j - i]
q = p[i] + r[j - i]
cut[j] = i // the best first cut for len j rod
r[i] = q
return r[n], cut

Print-Cut-Rod-Solution(p, n)
(r, cut) = Cut-Rod(p, n)
while n > 0
print cut[n]
n = n – cut[n] // remove the first piece

Slides modified from Prof. Hsu-Chun Hsiao 42

DP#2: Stamp Problem

43
 Stamp Problem
• Input: the postage 𝑛 and the stamps with values 𝑣1 , 𝑣2 , … , 𝑣𝑘

• Output: the minimum number of stamps to “exactly” cover the postage

44
 A Recursive Algorithm
• The optimal solution 𝑆𝑛 can be recursively defined as

Stamp(v, n)
r_min = ∞
if n == 0 // base case
return 0
for i = 1 to k // recursive case
r[i] = Stamp(v, n - v[i])
if r[i] < r_min
r_min = r[i]
return r_min + 1

45
 Step 1: Characterize an OPT Solution
Stamp Problem
Input: the postage 𝑛 and the stamps with values 𝑣1 , 𝑣2 , … , 𝑣𝑘
Output: the minimum number of stamps to cover the postage
• Subproblems
• S(i): the min #stamps with postage i
• Goal: S(n)
• Optimal substructure: suppose we know the optimal solution to S(i), there are k
cases:
• Case 1: there is a stamp with v1 in OPT
從solution中拿掉一張郵資為v1的郵票, 剩下的部分是S(i-v[1])的最佳解
• Case 2: there is a stamp with v2 in OPT
從solution中拿掉一張郵資為v2的郵票, 剩下的部分是S(i-v[2])的最佳解
:

• Case k: there is a stamp with vk in OPT

從solution中拿掉一張郵資為vk的郵票, 剩下的部分是S(i-v[k])的最佳解
46
Step 2: Recursively Define the Value of an
OPT Solution
Stamp Problem
Input: the postage 𝑛 and the stamps with values 𝑣1 , 𝑣2 , … , 𝑣𝑘
Output: the minimum number of stamps to cover the postage
• Suppose we know the optimal solution to S(i), there are k cases:
• Case 1: there is a stamp with v1 in OPT
從solution中拿掉一張郵資為v1的郵票, 剩下的部分是S(i-v[1])的最佳解

• Case 2: there is a stamp with v2 in OPT

從solution中拿掉一張郵資為v2的郵票, 剩下的部分是S(i-v[2])的最佳解
:

• Case k: there is a stamp with vk in OPT

從solution中拿掉一張郵資為vk的郵票, 剩下的部分是S(i-v[k])的最佳解

• Recursively define the value

47
Step 3: Compute Value of an OPT Solution
Stamp Problem
Input: the postage 𝑛 and the stamps with values 𝑣1 , 𝑣2 , … , 𝑣𝑘
Output: the minimum number of stamps to cover the postage
• Bottom-up method: solve smaller subproblems first
i 0 1 2 3 4 5 … n
S[i]
Stamp(v, n)
S[0] = 0
for i = 1 to n // compute r[1], r[2], ... in order
r_min = ∞
for j = 1 to k
if S[i - v[j]] < r_min
r_min = 1 + S[i – v[j]]
S[i] = r_min
return S[n]
48
Step 4: Construct an OPT Solution by
Backtracking
Stamp(v, n)
S[0] = 0
for i = 1 to n
r_min = ∞
for j = 1 to k
if S[i - v[j]] < r_min
r_min = 1 + S[i – v[j]]
B[i] = j // backtracking for stamp with v[j]
S[i] = r_min
return S[n], B

Print-Stamp-Selection(v, n)
(S, B) = Stamp(v, n)
while n > 0
print B[n]
n = n – v[B[n]]

49
DP#3: Matrix-Chain Multiplication
Textbook Chapter 15.2 – Matrix-chain multiplication

50
 Matrix-Chain Multiplication
• Input: a sequence of n matrices 𝐴1 , … , 𝐴𝑛
• Output: the product of 𝐴1 𝐴2 … 𝐴𝑛

𝐴1 .cols=𝐴2 .rows

𝐴1 𝐴2 𝐴3 …… 𝐴𝑛
𝐴4

𝐴1 and 𝐴2 are compatible.

51
 Observation

A B C

• Each entry takes 𝑞 multiplications

• There are total 𝑝𝑟 entries
Matrix multiplication is associative: 𝐴 𝐵𝐶 = (𝐴𝐵)𝐶. The time required by
obtaining 𝐴 × 𝐵 × 𝐶 could be affected by which two matrices multiply first .
52
 Example

= =

• Overall time is
53
 Example

= =

• Overall time is
54
 Matrix-Chain Multiplication Problem
• Input: a sequence of integers 𝑙0 , 𝑙1 , … , 𝑙𝑛
• 𝑙𝑖−1 is the number of rows of matrix 𝐴𝑖
• 𝑙𝑖 is the number of columns of matrix 𝐴𝑖
• Output: an order of performing 𝑛 − 1 matrix multiplications in the
minimum number of operations to obtain the product of 𝐴1 𝐴2 … 𝐴𝑛
𝐴1 .cols=𝐴2 .rows

𝐴1 𝐴2 𝐴3 …… 𝐴𝑛
𝐴4

𝐴1 and 𝐴2 are compatible.

Do not need to compute the result but find the fast way to get the result!
(computing “how to fast compute” takes less time than “computing via a bad way”)
55
 Brute-Force Naïve Algorithm
• 𝑃𝑛 : how many ways for 𝑛 matrices to be multiplied

4𝑛
• The solution of 𝑃𝑛 is Catalan numbers, Ω 3 , or is also Ω 2𝑛
𝑛2 Exercise 15.2-3

56
 Step 1: Characterize an OPT Solution
Matrix-Chain Multiplication Problem
Input: a sequence of integers 𝑙0 , 𝑙1 , … , 𝑙𝑛 indicating the dimensionality of 𝐴𝑖
Output: an order of matrix multiplications with the minimum number of operations
• Subproblems
• M(i, j): the min #operations for obtaining the product of 𝐴𝑖 … 𝐴𝑗
• Goal: M(1, n)
• Optimal substructure: suppose we know the OPT to M(i, j), there
are k cases: 𝑖≤𝑘<𝑗
𝐴𝑖 𝐴𝑖+1 … 𝐴𝑘 𝐴𝑘+1 𝐴𝑘+2 … 𝐴𝑗

• Case k: there is a cut right after Ak in OPT

左右所花的運算量是M(i, k)及M(k+1, j)的最佳解

57
Step 2: Recursively Define the Value of an
OPT Solution
Matrix-Chain Multiplication Problem
Input: a sequence of integers 𝑙0 , 𝑙1 , … , 𝑙𝑛 indicating the dimensionality of 𝐴𝑖
Output: an order of matrix multiplications with the minimum number of operations
• Suppose we know the optimal solution to M(i, j), there are k cases:
• Case k: there is a cut right after Ak in OPT
左右所花的運算量是M(i, k)及M(k+1, j)的最佳解

𝐴𝑘 .cols=𝑙𝑘
𝐴𝑖 𝐴𝑖+1 … 𝐴𝑘 𝐴𝑘+1 𝐴𝑘+2 … 𝐴𝑗 = 𝐴𝑖 .rows
=𝑙𝑖−1
𝐴𝑘+1..𝑗

𝐴𝑘+1 .rows=𝑙𝑘
𝐴𝑗 .cols=𝑙𝑗
• Recursively define the value

58
Step 3: Compute Value of an OPT Solution
Matrix-Chain Multiplication Problem
Input: a sequence of integers 𝑙0 , 𝑙1 , … , 𝑙𝑛 indicating the dimensionality of 𝐴𝑖
Output: an order of matrix multiplications with the minimum number of operations
• Bottom-up method: solve smaller subproblems first

• How many subproblems to solve

• #combination of the values 𝑖 and 𝑗 s.t. 1 ≤ 𝑖 ≤ 𝑗 ≤ 𝑛

59
Step 3: Compute Value of an OPT Solution
Matrix-Chain(n, l)
initialize two tables M[1..n][1..n] and B[1..n-1][2..n]
for i = 1 to n
M[i][i] = 0 // boundary case
for p = 2 to n // p is the chain length
for i = 1 to n – p + 1 // all i, j combinations
j = i + p – 1
M[i][j] = ∞
for k = i to j – 1 // find the best k
q = M[i][k] + M[k + 1][j] + l[i - 1] * l[k] * l[j]
if q < M[i][j]
M[i][j] = q
return M

60
Dynamic Programming Illustration

1 2 3 4 5 6 … n
How to decide the 1 0
order of the matrix 2 0
multiplication?
3 0
4 0
5 0
6 0
： 0
n 0

61
 Step 4: Construct an OPT Solution by
Backtracking
Matrix-Chain(n, l)
initialize two tables M[1..n][1..n] and B[1..n-1][2..n]
for i = 1 to n
M[i][i] = 0 // boundary case
for p = 2 to n // p is the chain length
for i = 1 to n – p + 1 // all i, j combinations
j = i + p – 1
M[i][j] = ∞
for k = i to j – 1 // find the best k
q = M[i][k] + M[k + 1][j] + l[i - 1] * l[k] * l[j]
if q < M[i][j]
M[i][j] = q
B[i][j] = k // backtracking
return M and B

Print-Optimal-Parens(B, i, j)
if i == j
print 𝐴𝑖
else
print “(”
Print-Optimal-Parens(B, i, B[i][j])
Print-Optimal-Parens(B, B[i][j] + 1, j)
print “)”

62
 Exercise
Matrix 𝑨𝟏 𝑨𝟐 𝑨𝟑 𝑨𝟒 𝑨𝟓 𝑨𝟔
Dimension 30 x 35 35 x 15 15 x 5 5 x 10 10 x 20 20 x 25

1 2 3 4 5 6 1 2 3 4 5 6
1 0 15,7507,875 9,37511,87515,125 1 1 1 3 3 3
2 0 2,625 4,375 7,12510,500 2 2 3 3 3
3 0 750 2,500 53,75 3 3 3 3
4 0 1,000 3,500 4 4 5
5 0 5,000 5 5
6 0 6

63
To Be Continued…

64
Question?
Important announcement will be sent to
@[Link] mailbox & post to the course website

Course Website: [Link]

Email: ada-ta@[Link]