Transcript C(2, 1)

Dynamic Programming
Part One
HKOI Training Team 2004
Recurrences
• Function defined in terms of itself
– M(X) = X * M(X-1)
– Fn+2 = Fn+1 + Fn
– Kn+1 = max{Kn-1+100, Kn}
• One or more base cases are needed
– M(0) = 1
– F0 = 1, F1 = 1
– K10 = 100, K11 = 177
2
Evaluating recurrences
• Combination
– C(n, r) = C(n-1, r) + C(n-1, r-1)
– C(n, 0) = C(n, n) = 1
• Algorithm:
function C(n, r)
if (r=0) or (r=n)
return 1
else
return C(n-1, r) + C(n-1, r-1)
3
Slow...
C(5, 2)
C(4, 2)
C(4, 1)
C(3, 2)
C(3, 1)
C(3, 1)
C(3, 0)
C(2, 2)
C(2, 1)
C(2, 1)
C(2, 0)
C(2, 1)
C(2, 0)
C(1, 1)
C(1, 0)
C(1, 1)
C(1, 0)
C(1, 1)
C(1, 0)
4
A table...
C(5, 2)
C(4, 2) C(4, 1)
C(3, 2) C(3, 1) C(3, 0)
C(2, 2) C(2, 1) C(2, 0)
C(1, 1) C(1, 0)
5
Redundant calculations
C(5, 2)
C(4, 2)
C(4, 1)
C(3, 2)
C(3, 1)
C(3, 1)
C(3, 0)
C(2, 2)
C(2, 1)
C(2, 1)
C(2, 0)
C(2, 1)
C(2, 0)
C(1, 1)
C(1, 0)
C(1, 1)
C(1, 0)
C(1, 1)
C(1, 0)
6
Fast...
C(5, 2)
C(4, 2)
C(4, 1)
C(3, 2)
C(3, 1)
C(3, 1)
C(3, 0)
C(2, 2)
C(2, 1)
C(2, 1)
C(2, 0)
C(2, 1)
C(2, 0)
C(1, 1)
C(1, 0)
C(1, 1)
C(1, 0)
C(1, 1)
C(1, 0)
7
Dynamic programming
• Abbreviation: DP / DyP
• Not particularly related to programming
– As in “Linear Programming”!
• An approach (paradigm) for solving
certain kinds of problems
– Not a particular algorithm
• Usually applied on recurrences
8
Principles of DP
• Evaluating recurrences may
sometimes be slow (exponential time)
• Accelerate by avoiding redundant
calculations!
– Memorize previously calculated values
• Usually applied to problems with:
– a recurrence relation
– overlapping subproblems
– solutions exhibiting optimal substructure
9
Why DP?
• Reduce runtime
– In the previous computation of C(n, k),
how many times is the function invoked?
• Slow algorithm: 2C(n,k) – 1 [exponential in n]
• Fast algorithm: O(nk) [polynomial in n]
• Tradeoff – memory
– In the C(n, k) problem, the memory
requirement is O(n) using pure recursion;
O(nk) is required for memorization
• In fact, the O(nk) bound can be improved
10
Classification of problems
• Induction
– Evaluation of a certain function is the main
concern
– Examples:
• The N-th Fibonacci number
• Number of different binary trees with N nodes
• Optimization
– Maximization or minimization of certain
function is the objective
– Examples:
• Shortest paths
• Activity scheduling (maximize no. of activities)
11
Triangle (IOI ’94)
7
• Given a triangle with N
levels like the one on the
left, find a path with
maximum sum from the top
to the bottom
• Only the sum is required
6
9
8
1
4
2
4
5
3
12
Triangle (analysis)
• Exhaustion?
– How many paths are there in total?
• Greedy?
– It doesn’t work. Why?
• Graph problem?
– Possible, but not simple enough
13
Triangle (formulation)
• Let A[i][j] denote the number in the ith row and j-th column, (i, j)
• Let F[i][j] denote the sum of the
numbers on a path with max sum
from (1, 1) to (i, j)
• Answer = maximum of F[N][1],
F[N][2], …, F[N][N]
14
Triangle (formulation)
• Base case: F[1][1] = A[1][1]
• Progress: (i > 1, 1 < j < i)
– F[i][1] = F[i-1][1]+A[i][1]
– F[i][i] = F[i-1][i-1]+A[i][i]
– F[i][j] = max{F[i-1][j-1],F[i-1][j]}+A[i][j]
i-1, j-1
i-1, j
i, j
15
Triangle (order of calc.)
• F[i][*] depends on F[i-1][*]
• Compute F row by row, from top to
bottom
16
Triangle (algorithm)
• Algorithm:
– F[1][1]  A[1][1];
for i  2 to N do
F[i][1] = F[i-1][1]+A[i][1];
F[i][i] = F[i-1][i-1]+A[i][i];
for j  2 to i-1 do
F[i][j]  max{F[i][j],F[i][j-1]}
+ A[i][j]
answer  max{F[N][1], …, F[N][N]}
17
Triangle (complexity)
• Number of array entries to be
computed: about N(N-1)/2
• Time for computing one entry: O(1)
• Thus the total time complexity is
O(N2)
• Memory complexity: O(N2)
– This can be reduced to O(N) since F[i][*]
only depends on F[i-1][*]
– We can discard some previous entries
after starting on a new row
18
Longest Common Subsequence
• Given two strings A and B of length n
and m respectively, find their longest
common subsequence (NOT substring)
• Example
–
–
–
–
A: aabcaabcaadyyyefg
B: cdfehgjaefazadxex
LCS: caaade
Explanation
• A: a a b c a a b c a a d y y y e f g
• B: c d f e h g j a e f a z a d x e x
19
LCS (analysis)
• Exhaustion
– Number of subsequences of A = 2n
– Number of subsequences of B = 2m
– Exponential time!
• Observation
– If a LCS of A and B is nonempty then it
must have a last character (trivial)
A: a a b c a a b c a a d y y y e f g
B: c d f e h g j a e f a z a d x e x
20
LCS (analysis)
• Observation
– Suppose the last LCS character
corresponds to A[i] and B[j]
– Removing the last LCS character results in
a LCS of A[1..i-1] and B[1..j-1]
A: a a b c a a b c a a d y y y e f g
B: c d f e h g j a e f a z a d x e x
A: a a b c a a b c a a d y y y e f g
B: c d f e h g j a e f a z a d x e x
21
LCS (formulation)
• Thus it is reasonable to define F[i][j]
as the length of any LCS of A[1..i] and
B[1..j]
• Base cases:
– F[i][0] = 0 for all i
– F[0][j] = 0 for all j
• Progress: (0 < i <= n, 0 < j <= m)
– F[i][j] = F[i-1][j-1] + 1
if A[i]=B[j]
– F[i][j] = max{F[i-1][j], F[i][j-1]}
else
22
LCS (order of calc.)
• F[i][j] depends on F[a][b], a ≤ i and b ≤ j
• Order: from top to bottom, from left to right
– There are some other possible orders!
0 1 2 3 4
0
1
2
3
23
LCS (complexity)
• Time complexity: O(NM)
• Memory complexity: O(NM)
– Again, this can be reduced to O(N+M), but
why and how?
24
Coins
• Given an unlimited supply of $2, $3
and $5 coins, find the number of
different ways to form a denomination
of $N
• Example:
– N = 10
– {2, 2, 2, 2, 2}, {2, 2, 3, 3}, {2, 3, 5},
{5, 5}
• Solve this induction problem by
yourself
25
Matrix Chain Multiplication
• A matrix is a rectangle of numbers
2 7 9
20 4 -1
A matrix of size 2×3
• The number of “usual” multiplications
needed to multiply a n×m matrix and
a m×r matrix is nmr
• Matrix multiplication is associative
– (AB)C = A(BC)
26
Matrix Chain Multiplication
• Given a sequence of matrices A1, A2,
…, An, find an order of multiplications
such that the total number of “usual”
multiplications is minimized
• Example:
– A: 3×7, B: 7×5, C: 5×2
– (AB)C takes 3×7×5+3×5×2 = 135 muls
– A(BC) takes 7×5×2+3×7×2 = 112 muls
27
MCM (analysis)
• How many different orders of
multiplications are there?
– This can be solved by DP!
• Does greedy work?
• Let’s have a look at the brackets
–
–
–
–
(A((BC)((DE)F)))(G((HI)J))
There must be one last multiplication
(A((BC)((DE)F)))(G((HI)J))
Every subexpression with more than one
matrix has one last multiplication
28
MCM (analysis)
• Optimal substructure
– If the last multiplication is
(A1A2…Ai)(Ai+1…AN) and the multiplication
scheme is optimal, then the multiplication
schemes for A1A2…Ai and Ai+1…AN must
also be optimal
29
MCM (formulation)
• Let r[i] and c[i] be the number of rows
and the number of columns of Ai
respectively
• Let F[i][j] be the minimum number of
“usual” multiplications required to
compute AiAi+1…Aj
• Base case: F[i][i] = 0 for all i
• Progress: for all i < j
F[i][j] = min{F[i][k]+F[k+1][j]+
i≤k<j
r[i]*c[k]*c[j]}
30
MCM (order of calc.)
• F with fewer matrices first
j, i
1
2
3
4
5
6
1
2
3
first
4
5
6
last
31
MCM (alternative)
• Let G[i][j] be the minimum number of
“usual” multiplications required to
compute AiAi+1…Ai+j-1
• Base case: G[i][1] = 0 for all i
• Progress: for all 1 < j < N-i
G[i][j] = min{G[i][k]+G[i+k][j-k]+
1≤k<j
r[i]*r[i+k]*c[i+j-1]}
• Explain!!
32
MCM (alternative)
• Still, G with fewer matrices first
i, j
1
2
3
4
5
6
1
2
last
3
4
5
6
first
33
MCM (algorithm)
• Bottom-up algorithm (algorithm 2):
for i  1 to N do
G[i][1]  0
for j  2 to N do
for i  1 to N-j+1
G[i][j]  min{G[i][k]
1≤k<j
+G[i+k][j-k]+
r[i]*r[i+k]*c[i+j-1]}
answer  G[1][N]
34
MCM algorithm)
• Top-down algorithm (algorithm 1):
function MCM_DP(i, j)
if F[i][j] is not ∞, return F[i][j]
m∞
for k  i to j-1 do
m  min{m,
MCM_DP(i, k)+
MCM_DP(k+1, j)+
r[i]*c[k]*c[j]}
F[i][j]  m
return F[i][j]
35
MCM (algorithm)
• Top-down algorithm (main):
initialize everything in F to ∞
for i  1 to N do
F[i][i]  0
answer  MCM_DP(1, N)
36
MCM (complexity)
• Number of array entries to be
computed: about N(N-1)/2
• Number of references to other entries
when computing one single entry:
– It varies
– On the average, about N/2
• Thus the total time complexity is
O(N3)
37
Fishing
• There are N fish ponds and you are
going to spend M minutes on fishing
• Given the time-reward relationship of
each pond, determine the time you
should spend at each pond in order to
get the biggest reward
time/pond
1
2
3
1 minute
0 fish
2 fish
1 fish
2 minutes
3 fish
2 fish
2 fish
3 minutes
3 fish
4 fish
4 fish
38
Fishing (example)
• For example, if N=3, M=3 and the
relationships are given in the previous
slide, then the optimal schedule is
–
–
–
–
Pond 1: 2 minutes
Pond 2: 1 minute
Pond 3: 0 minute
Reward: 5 fish
39
Fishing (analysis)
• You can think of yourself visiting
ponds 1, 2, 3, …, N in order
– Why?
• Suppose in an optimal schedule you
spend K minutes on fishing at pond 1
• So you have M-K minutes to spend at
the remaining N-1 ponds
– The problem is reduced
• But how can I know what is K?
– You don’t know, so try all possible values!
40
Fishing (formulation)
• Let F[i][j] be the maximum reward
you can get by spending j minutes at
the first i ponds
• Base cases: 0 ≤ i, j ≤ N
F[i][0] = 0
F[0][j] = 0
• Progress: 1 ≤ i ≤ N, 1 ≤ j ≤ M
F[i][j] = max{F[i-1][k]+R[i][j-k]}
0≤k≤j
41
Brackets
• A balanced-bracket expression (BBE)
is defined as follows
– The empty string is a BBE
– If X and Y are BBEs then (X) and XY BBEs
– Nothing else is a BBE
• For example, (), (()), ()(()())(()) are
BBEs while ((), )(, (()()))()() are not
BBEs
• Find the number of different BBEs with
exactly N pairs of brackets
42
Brackets (analysis)
• Obviously this is an induction problem
• Listing out all BBEs with N pairs of
brackets is not a good idea
• What makes a bracket expression not
a BBE?
– the numbers of opening and closing
brackets do not match
– the number of closing brackets exceeds
the number of opening brackets at some
point during a scan from left to right
43
Brackets (analysis)
• Clearly only the second rule matters in
this problem
• Intuitively it is easy to construct a BBE
from left to right
• We call a bracket expression a BBEprefix (BP) if the number of closing
brackets never exceeds the number of
opening brackets during a scan from
left to right
44
Brackets (formulation)
• Let F[i][j] be the number of BPs with i
opening brackets and j closing
brackets (thus of length i+j)
• Base cases:
F[0][0] = 1
F[i][j] = 0 for all 0 ≤ i < j ≤ N
• Progress: (0 < j ≤ i ≤ N)
F[i][j] = F[i-1][j]+F[i][j-1]
45
Polygon Triangulation
1
• Given an Nsided convex
polygon A, find
6
a triangulation
scheme with
minimum total
cut length
2
5
4
3
46
Polygon (analysis)
• Every edge of A belongs to exactly one
triangle resulting from the
triangulation
1 1
• We get two 6
(or one)
smaller
polygons
after
5
deleting a
triangle
2
4 4
4
2
3
47
Polygon (analysis)
• The order of cutting does not matter
• Optimal substructure
– If the cutting scheme for A is optimal,
then the cutting schemes for B and C
must also be optimal
A
C
B
48
Polygon (formulation)
• Take this problem as an exercise
• A small hint: similar to Matrix Chain
Multiplication
• Nothing more
49
Summary
• Remember, DP is just a technique, not a
particular algorithm
• The problems we have discussed are quite
straightforward that you should be able to
know they can be solved by DP with little
inspection
• The DP problems in NOI and IOI are much
harder
– They are well disguised
• Looking at a wide variety of DP problems
seems to be the only way to master DP
50
Looking forward…
• Hopefully the trainer responsible for
Advanced DP II will talk about DP on
non-rectangular structures, such as
trees and graphs
• The problems discussed will be more
complicated than those you have just
seen, so please be prepared
51
The end
The last thing…
LET’S HAVE LUNCH!!!
52