Nhân bản – Phụng sự – Khai phóng

Dynamic programming
 Dynamic programming
• The principle is similar to divide and conquer algorithm
• The problem is divided into many subproblems
• The problem is further divided into subproblems, until the
subproblems can be solved easily
• Combining the solutions of the subproblems gives the solution
of the original problem

2
 Dynamic programming
• Difference with divide and conquer algorithm
• Dynamic programming is applied when the subproblems are
not independent
• Common subproblems
• When subproblems are not independent
• Applying divide and conquer algorithm
– Do the same work (solve the same subproblem) multiple times
• Applying dynamic programming algorithm
– Each subproblem is solved once and the result is saved to an array,
then if the subproblem is encountered again, only the result is
reused
– Reduce complexity

3
 Dynamic programming
• Dynamic programming = Divide and conquer + Memory

• Divide and conquer: top-down approach

• Solve the big problem first, then solve the subproblems later

• Dynamic programming: bottom-up approach

• Solve the subproblems first, then based on the solved
subproblems, solve the larger problem later

4
 Dynamic programming
• Dynamic programming algorithms are often applied to
optimization problems
• These problems can have multiple solutions, we want to find the optimal
solution according to an objective function

• Building a dynamic programming algorithm usually goes through

the following steps:
• Determine the structural properties of the optimal solution
• Recursive definition of the value of the optimal solution
• Compute the value of the optimal solution through simple cases (the
stopping case of the recursion) and iterate until the original problem is
solved
• Build optimal solutions for the information just calculated
• If we need the optimal solution, not just the value of the optimal solution

5
 Some applications
• Binomial expansion (a+b)n
• Matrix chain multiplication
• Longest common subsequence
• Backpacking

6
 Binomial expansion (a+b)n

• The binomial (a+b)n is developed according to the following formula

n
(a  b) n   Cnk a n  k b k
k 0
• With
n(n  1)...(n  k  1) n!
C 
k

k (k  1)...1 k!(n  k )!
n

• Formula for calculating k combinations of n

1 k  0, k  n
C   k 1
k

 n 1 1  k  n  1
n k
 n 1
C C

7
 Binomial expansion (a+b)n

• Divide and Conquer Algorithm

C(k, n)
begin
if (k = 0 or k = n) then
return (1)
else
return (C(k-1, n-1) + C(k, n-1))
end

• There are many values of C(i, j) with i<k and j < n, which are calculated
many times
• High complexity

8
 Binomial expansion (a+b)n

• Divide and Conquer Algorithm

C(4,6)

C(3,5) C(4,5)

C(2,4) C(3,4) C(3,4) C(4,4)

C(1,3) C(2,3) C(2,3) C(3,3) C(2,3) C(3,3)

C(1,2) C(2,2) C(1,2) C(2,2) C(1,2) C(2,2)

C(0,1) C(1,1) C(0,1) C(1,1) C(0,1) C(1,1)

9
 Binomial expansion (a+b)n

• Divide and Conquer Algorithm

• Calculate running time
• Let C(n) be the worst case running time and compute C(k, n) for all
k
• So from the algorithm, we have

c if n  1
C ( n)  
 2C (n  1)  d else
where c and d are constants

10
 Binomial expansion (a+b)n

• Divide and Conquer Algorithm

• Calculate running time
C (n)  2C (n  1)  d
 2(C (n  2)  d )  d  4C (n  2)  2d  d
 4(2C (n  3)  d )  2d  d  8C (n  3)  4d  2d  d
i 1
 2 C (n  i )  d  2 k
i

k 0
n2
2 n 1  1
2 n 1
C (1)  d  2  2 k n 1
cd
k 0 2 1
 2 n 1 (c  d )  d
• So: C(n) = (2n)

11
 Binomial expansion (a+b)n
• Dynamic programming algorithm
• Use array C[0..n,0..k] to store intermediate results
• C[i, j] contains the value Ci j
• C[i,j] is calculated

1 j  0 hay j  i
C[i, j ]  
 C[i  1, j  1]  C[i  1, j ]
• Calculate the values of Pascal's triangle
n/k 0 1 2 3 4 5
0 1
1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
5 1 5 10 10 5 1

12
 Binomial expansion (a+b)n

• Dynamic programming algorithm

C1(k, n)
begin
// Initialize column 0 and diagonal
for i from 0 to nk do C[i,0] = 1 endfor
for i from 0 to k do C[i,i] = 1 endfor
// Calculate each column
for j from 1 to k do
for i from j+1 to n-k+j do
C[i,j] = C[i-1,j-1] + C[i-1,j]
endfor
endfor
return (C[n,k])
end

13
 Binomial expansion (a+b)n

• Dynamic programming algorithm

• Example: n=8, k=5

n/k 0 1 2 3 4 5 n/k 0 1 2 3 4 5
0 1 0 1
1 1 1 1 1 1
2 1 1 2 1 2 1
3 1 1 3 1 3 3 1
4 1 4 4 6 4 1
5 1 5 10 10 5 1
6 6 20 15 6
7 7 35 21
8 8 56
Initialize column 0 and diagonal Calculate by column

Just calculate the values needed for calculating C[8,5]

14
 Binomial expansion (a+b)n

• Dynamic programming algorithm (4)

• Running time
• Number of values to calculate (assuming addition is the basic operation)
k(nk) = nk – k2 ≤ nk
• So running time O(nk)
• Use an array with nk memory cells to store intermediate values, or space
complexity O(nk)

• Can the algorithm be improved to reduce the number of memory cells

used?

15
 Binomial expansion (a+b)n
• Dynamic programming algorithm
C2(k, n)
begin
// use one-dimensional array C[0..n]
C[0] = 1 // initialize row 1
C[1] = 1
// calculate each row
Use only one- for i from 2 to n do
dimensional array p1 = 1
to store current for j from 1 to i-1 do
line of Pascal's p2 = C[j]
triangle C[j] = p1 + p2
p1 = p2
endfor
C[i] = 1 // element on the diagonal
endfor
return (C[k])
end
16
 Binomial expansion (a+b)n

• Dynamic programming algorithm

• Example: n=8, k=5
n/k 0 1 2 3 4 5 6 7 8
0
1 1 1
2 1 2 1
p1 p2
3 1 3 3 1
4 1 4 6 4 1 Cj
5 1 5 10 10 5 1
6 1 6 15 20 15 6 1
7 1 7 21 35 35 21 7 1
8 1 8 28 56 70 56 28 8 1

17
 Binomial expansion (a+b)n

• Dynamic programming algorithm

• Running time
• Number of values to calculate (assuming addition is the basic operation)
n n 1
n(n  1)
•
 (i  1)   k 
i  2 O(n2)
So time complexity 1 2
• Use an array of n memory cells to store intermediate values, or space
complexity O(n)

18
 Dynamic programming algorithm design
• Identification
• Build a divide and conquer algorithm/simple algorithm
• Complexity assessment (exponential)
• The same subproblem is solved multiple times
• Build
• Extract the ”conquer" part of the divide and conquer algorithm and replace
the recursive calls with searching for values in an array
• Instead of returning the value, save the value to the array
• Use the divide and conquer algorithm's stopping condition to initialize the
array values
• Find a way to calculate the values of array
• Build a loop to calculate the values of array

19
 Dynamic programming algorithm design

C(k, n) Divide and conquer

begin
if (k = 0 or k = n) then return (1)
else return (C(k-1, n-1) + C(k, n-1))
end
Dynamic
C1(k, n)
programming
begin
for i from 0 to n-k do C[i,0] = 1 endfor
for i from 0 to k do C[i,i] = 1 endfor
for j from 1 to k do
for i from j+1 to n-k+j do
C[i,j] = C[i-1,j-1] + C[i-1,j]
endfor
endfor
return (C[n,k])
end
20
 Matrix chain multiplication
• Problem
• There are n matrices M1, M2, … Mn. we need to calculate the product
M1.M2 .….Mn so that the fewest multiplications are performed

• Matrix multiplication is associative

• M1.M2 .….Mn can be calculated by many different orders of combination

• Suppose we use a simple algorithm to multiply two matrices

• Multiplying two matrices of size pxq and qxr requires performing pxqxr
multiplications

21
 Matrix chain multiplication

• Example
• Matrix multiplication
M1(10x20).M2(20x50).M3(50x1).M4(1x100)

• There are 5 combinations

• (M1.(M2.(M3.M4))): 50x1x100+20x50x100+10x20x100=125000 multiplications
• (M1.((M2 .M3).M4)): 72000
• ((M1.M2).(M3 .M4)): 65000
• ((M1.(M2.M3)).M4): 2200
• (((M1.M2).M3).M4): 60500

• Question: Which combination performs the fewest multiplications?

22
 Matrix chain multiplication
• Brute Force Algorithm (1)
• Try all possible combinations
• Calculate the number of multiplications for each method
• Choose the best way

• The number of all possible combinations is exponential

• Let P(n) be the number of ways to combine n matrices

• When n = 1 then P(1) = 1
• When n >= 2, the product M1.M2.….Mn can be divided into two sequences
M1.M2.….Mn = (M1.M2…Mk).(Mk+1 ...Mn )

there are n-1 ways to divide (k=1..n-1)

P(k) ways P(n-k) ways

23
 Matrix chain multiplication

• Brute Force Algorithm (2)

• So
1 n 1

P (n)   n 1

P(k ) P(n  k ) n  2
k 1

• Can be pointed out

P ( n)  ( 2 n )

24
 Matrix chain multiplication

• Divide and conquer algorithm (1)

• Let mi,j be the minimum number of multiplications when performing the product
Mi Mi+1…Mj
• Obviously, mi,i = 0
• Suppose the dimensions of the matrices Mi, Mi+1,…, Mj are (di-1, di), (di,di+1), …, (dj-
1,dj ) respectively
• Suppose that we know the combination MiMi+1…Mj with the minimum cost
(smallest mi,j) is (MiMi+1…Mk ).(Mk+1…Mj)
• means k already known
• then:
mi,j = mi,k + mk+1,j + number of multiplications to multiply two matrices
(di-1,dk).(dk,dj)
mi,j = mi,k + mk+1,j + [Link]
• However, k is undefined, k  [i..j-1], so:
 0 i j
mi , j  
min (mi ,k  mk 1, j  d i 1d k d j ) i  j
ik  j 25
 Matrix chain multiplication

• Divide and conquer algorithm (2)

• Therefore, we build a divide-and-conquer algorithm for calculating mi,j with all
possible values of k
matrixChainRecur(i, j)
m = +
begin
if (i=j) then m = 0
else for k from i to j-1 do
r = matrixChainRecur(i,k) + matrixChainRecur(k+1,j) + di-1dkdj
if (r < m) then
m=r
endif
endfor
endif
return (m)
end

The solution of the problem is matrixChainRecur(1,n)

26
 Matrix chain multiplication

• Divide and conquer algorithm (3)

• Complexity evaluation
• Let C(n) be the running time of chainMatrixRecur(i,j) when i=1, j=n
• We have
c n0
 n 1
C ( n)  

C (k )  C (n  k )  d  n  0
where c andk 1d are constants
• Or
n 1
C (n)  2 C (k )  d (n  1)
1
• So C(n)  2C(n-1), whichkmeans C(n) = (2n)

• If calculating exactly, then C(n) = (3n)

27
 Matrix chain multiplication

• Divide and conquer algorithm (4)

• Example

chainMatrixRecur(1,4)

(1,1) (2.4) (1,2) (3,4) (1.3) (4.4)

(2.2) (3,4) (2,3) (4.4) (1,1) (2.2) (3.3) (4.4) (1,1) (2,3) (1,2) (3.3)

(3.3) (4.4) (2.2) (3.3) (2.2) (3.3) (1,1) (2.2)

There are many subproblems that are done multiple times!

28
 Matrix chain multiplication

• Dynamic programming algorithm (1)

• We have to use the array m[1..n,1..n]
• For each m[i,j], ij, only the upper half of the main diagonal of array m
is used
• Each m[i,j] is calculated by the formula
 0 i j
mi , j  
min (mi ,k  mk 1, j  d i 1d k d j ) i  j
ik  j

• So, to calculate mi,j we must have the values mi,k and mk+1,j with ik<j

29
 Matrix chain multiplication

• Dynamic programming algorithm (2)

• Illustration of how to calculate mi,j
i j
m[i,j]

 0 i j
i mi , j  
min (mi ,k  mk 1, j  d i 1d k d j ) i  j
ik  j

m[i,k]
j

Need to build gradually

m[k+1,j]
array m along the diagonals

30
 Matrix chain multiplication

• Dynamic programming algorithm (3)

• The array m will be built gradually for each diagonal
• Diagonal s will consist of elements m[i,j] such that j-i=s
• So
 0 s0
mi , j  
min (mi ,k  mk 1,i  s  d i 1d k d i  s ) 0  s  n
ik  j

• Building a new array m that only allows to calculate the minimum

number of multiplications (values) of the solution
• Building a solution (how to perform matrix multiplication)
• Use array g[1..n,1..n] to store the index k for the optimal solution at each
step

31
 Matrix chain chain multiplication

• Dynamic programming algorithm (4)

matrixChain(n)
begin
for i from 0 to n do m[i,i] = 0 endfor
for s from 1 to n-1 do // calculate all diagonals of s
for i from 1 to ns do // calculate a diagonal s
j=i+s
// calculate mi,j = min(mi,k +mk+1,i+s +di-1dkdi+s )
m[i,j] = +
for k from i to j-1 do
r = m[i,k] + m[k+1,j] + di-1dkdj
if (r < m[i,j]) then
m[i,j] = r
g[i,j] = k // memorize k
endif
endfor
endfor
endfor
return m and g
end
32
 Matrix chain multiplication

• Dynamic programming algorithm (5)

• Example
• M1(10x20).M2(20x50).M3(50x1).M4(1x100)
means: d0 = 10, d1 = 20, d2 = 50, d3 = 1, d4 = 100

• Build diagonal s = 1
– m[1,2] = min(m[1,k] + m[k+1,2] + d 0 d 1 d 2 ), with 1 k<2
= min(m[1,1] + m[2,2] + d 0 d 1 d 2 )
= d 0 d 1 d 2 = 10x20x50 = 10000
g[1,2] = k = 1
– m[2,3] = min(m[2,k] + m[k+1,3] + d 1 d 2 d 3 ), with 2 k<3
= d 1 d 2 d 3 = 20x50x1 = 1000
g[2,3] = k = 2
– m[3,4] = d 2 d 3 d 4 = 50x1x100 = 5000
g[3,4] = k = 3

33
 Matrix multiplication

• Dynamic programming algorithm (6)

• Example
• Build diagonal s = 2
– m[1,3] = min(m[1,k] + m[k+1,3] + d 0 d k d 3 ), with 1 k<3
= min(m[1,1] + m[2,3] + d 0 d 1 d 3 ,
m[1,2] + m[3,3] + d 0 d 2 d 3 )
=min(0 + 1000 + 200, 10000 + 0 + 500)
= 1200
g[1,3] = k = 1
– m[2,4] = min(m[2,k] + m[k+1,4] + d 1 d k d 4 ), with 2 k<4
= min( m[2,2] + m[3,4] + d 1 d 2 d 4 ,
m[2,3] + m[4,4] + d 1 d 3 d 4 )
= min(0 + 5000 + 100000, 1000 + 0 + 2000)
= 3000
g[2,4] = k = 3

34
 Matrix multiplication

• Dynamic programming algorithm (7)

• Example
• Build diagonal s = 3
– m[1,4] = min(m[1,k] + m[k+1,4] + d 0 d k d 4 ), with 1  k<4
= min(m[1,1] + m[2,4] + d 0 d 1 d 4 ,
m[1,2] + m[3,4] + d 0 d 2 d 4 ,
m[1,3] + m[4,4] + d 0 d 3 d 4 )
= min(0 + 3000 + 20000,
10000 + 5000 + 50000,
1200 + 0 + 1000)
= 2200
g[1,4] = k = 3

• m[1,4] is the desired result

35
 Matrix chain multiplication

• Dynamic programming algorithm (8)

• The array m and g

10000 1200 2200

0
1 1 3
s=3
1000 3000
0
2 3
s=2
5000
0
3
s=1

s=0
36
 Matrix chain multiplication

• Dynamic programming algorithm (9)

• Complexity assessment
• The algorithm consists of 3 nested loops
• Each loop does not repeat more than n times
• So the running time is O(n3)

• Dynamic programming algorithm is better than simple algorithm and

divide and conquer algorithm

37
 Matrix chain multiplication

• Dynamic programming algorithm (10)

• Building the optimal solution
• perform multiplications in optimal order
• matrixChain only computes the optimal value of the combination of
multiplications, it does not perform the multiplication itself
• Use the information contained in the array g
– g[i,j] contains the value k, whose product Mi Mi-1 …Mj is split between Mk and Mk+1

• Suppose we have an algorithm to multiply two matrices X and Y:

matrixProduct(X, Y)

38
 Matrix chain multiplication

• Dynamic programming algorithm (11)

• Building the optimal solution

chainMatrixProduct(M, g, i, j)
// array of matrices
begin
if (i < j) then
X = chainMatrixProduct(M, g, i, g[i,j])
Y = chainMatrixProduct(M, g, g[i,j]+1,j)
return (matrixProduct(X,Y))
else // i = j
return (Mi)
endif
end
• chainMatrixProduct(M, g, 1, 4) will calculate the product M1.M2.M3.M4 in the order:
((M1.(M2.M3)).M4)
• Because: g[1,4] = 3, g[1,3] = 1

39
 Matrix chain multiplication

• Dynamic programming algorithm (12)

• Exercise
• Write an algorithm to print out the optimal combination expression to perform
matrix multiplication
– For example
Given the matrix array: M1(10x20).M2(20x50).M3(50x1).M4(1x100)
Result: ((M 1 .(M 2 .M 3 )).M 4 )

40
 Longest common subsequence
• Problem
• Given two sequences of symbols X and Y, the longest common subsequence
(LCS) of X and Y is the sequence of symbols obtained from X by deleting
some elements and also obtained from Y by deleting some elements

• For example: X = ABCBDAB and Y = BDCABA

X=AB C BDAB
Y= B DC A B A
Longest common subsequence: BCBA

• Application to compare the « similarity » of two DNA sequences

41
 Longest common subsequence
• Brute force algorithm
• Suppose X=x1x2…xn and Y = y1y2…ym
• Compare each subsequence of X with the sequence of Y
• There are 2n subsequences of X
• Comparing each subsequence of X with Y will perform m comparisons
• The complexity will be O(m2n)
• Exponential function!

42
 Longest common subsequence

• Divide and conquer algorithm (1)

• The problem can be decomposed into smaller subproblems
• Subproblem: find the longest common subsequence of prefix pairs of X and Y
– Given X=x1 x2 …xn , Xi = X=x1 x2 …xi is called the i-th prefix of X

• Let Z = z1 z2 …zk be the longest common subsequence (LCS) of X=x1 x2 …xn

and Y = y1 y2 …ym
If xn = ym then zk = xn = ym and Zk-1 = LCS(Xn-1 ,Ym-1 )
If xn  ym and zk  xn then Z = LCS(Xn-1,Y)
If xn  ym and zk  ym then Z = LCS(X,Ym-1)

43
 Longest common subsequence

• Divide and conquer algorithm (2)

• Recursive solution
• Let c[i,j] be the length of the longest common subsequence of Xi and Yj
• Then, the length of the longest common subsequence of X and Y will be
c[n,m]
• The length of the longest common subsequence of an empty sequence
and any sequence is always 0
– c[i,0] = 0 and c[0,j] = 0 for all i, j
• So, we have
0 i  0 hay j  0

c[i, j ]   c[i  1, j  1]  1 i, j  0, xi  y j
max(c[i  1, j ], c[i, j  1]) i, j  0, x  y
 i j

44
 Longest common subsequence

• Divide and conquer algorithm (3)

LCS-length(i,j)
begin
if (i = 0 or j = 0) then
return (0)
else
if (xi = yj) then
return (LCS-length(i-1,j-1) + 1)
else
return (max(LCS-length(i-1, j), LCS-length(i, j-1)))
endif
endif
end

45
 Longest common subsequence

• Divide and conquer algorithm (4)

• Complexity assessment
• Suppose n  m
• worst case running time
• So: C(k)  2C(m-1) = 22 C(m-2) = 2m C(0) = 2m
• That is, the algorithm has complexity  2m

46
 Longest common subsequence

• Dynamic programming algorithm (1)

• Store the length values of the longest common subsequences of prefix
pairs in the array c[0..n,0..m]
LCS-length (X,Y)
begin
n = length(X); m = length(Y)
for i from 0 to n do c[i,0]=0 endfor
for j from 0 to m do c[0,j]=0 endfor
for i from 1 to n do
for j from 1 to m do
if (xi = yj) then
c[i,j] = c[i-1,j-1] + 1
else
c[i,j] = max(c[i-1,j], c[i,j-1])
endif
endfor
endfor
return c
end
47
 Longest common subsequence

• Dynamic programming algorithm (2)

• Example j 0 1 2 3 4 5
i yj B D C A B
0 xi
A
1

2 B

3 C
4 B

X=ABCB, Y=BDCAB
48
 Longest common subsequence

• Dynamic programming algorithm (3)

• Example j 0 1 2 3 4 5
i yj B D C A B
0 xi 0 0 0 0 0 0
A
1 0

2 B 0
3 C 0
4 B 0
for i from 0 to n do c[i,0]=0
for j from 0 to m do c[0,j]=0 49
 Longest common subsequence

• Dynamic programming algorithm (4)

• Example j 0 1 2 3 4 5
i yj B D C A B
0 xi 0 0 0 0 0 0
1 A 0 0

2 B 0

3 C 0
4 B 0
if (xi = yj) then c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max(c[i-1,j], c[i,j-1])
50
 Longest common subsequence

• Dynamic programming algorithm (5)

• Example j 0 1 2 3 4 5
i yj B D C A B
0 xi 0 0 0 0 0 0
1 A 0 0 0 0

2 B 0

3 C 0
4 B 0
if (xi = yj) then c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max(c[i-1,j], c[i,j-1])
51
 Longest common subsequence

• Dynamic programming algorithm (6)

• Example j 0 1 2 3 4 5
i yj B D C A B
0 xi 0 0 0 0 0 0
1 A 0 0 0 0 1

2 B 0

3 C 0
4 B 0
if (xi = yj) then c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max(c[i-1,j], c[i,j-1])
52
 Longest common subsequence

• Dynamic programming algorithm (7)

• Example j 0 1 2 3 4 5
i yj B D C A B
0 xi 0 0 0 0 0 0
1 A 0 0 0 0 1 1

2 B 0

3 C 0
4 B 0
if (xi = yj) then c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max(c[i-1,j], c[i,j-1])
53
 Longest common subsequence

• Dynamic programming algorithm (7)

• Example j 0 1 2 3 4 5
i yj B D C A B
0 xi 0 0 0 0 0 0
1 A 0 0 0 0 1 1

2 B 0 1

3 C 0
4 B 0
if (xi = yj) then c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max(c[i-1,j], c[i,j-1])
54
 Longest common subsequence

• Dynamic programming algorithm (8)

• Example j 0 1 2 3 4 5
i yj B D C A B
0 xi 0 0 0 0 0 0
1 A 0 0 0 0 1 1

2 B 0 1 1 1 1

3 C 0
4 B 0
if (xi = yj) then c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max(c[i-1,j], c[i,j-1])
55
 Longest common subsequence

• Dynamic programming algorithm (9)

• Example j 0 1 2 3 4 5
i yj B D C A B
0 xi 0 0 0 0 0 0
1 A 0 0 0 0 1 1

2 B 0 1 1 1 1 2

3 C 0
4 B 0
if (xi = yj) then c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max(c[i-1,j], c[i,j-1])
56
 Longest common subsequence

• Dynamic programming algorithm (10)

• Example j 0 1 2 3 4 5
i yj B D C A B
0 xi 0 0 0 0 0 0
1 A 0 0 0 0 1 1

2 B 0 1 1 1 1 2

3 C 0 1 1
4 B 0
if (xi = yj) then c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max(c[i-1,j], c[i,j-1])
57
 Longest common subsequence

• Dynamic programming algorithm (11)

• Example j 0 1 2 3 4 5
i yj B D C A B
0 xi 0 0 0 0 0 0
1 A 0 0 0 0 1 1

2 B 0 1 1 1 1 2

3 C 0 1 1 2
4 B 0
if (xi = yj) then c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max(c[i-1,j], c[i,j-1])
58
 Longest common subsequence

• Dynamic programming algorithm (12)

• Example j 0 1 2 3 4 5
i yj B D C A B
0 xi 0 0 0 0 0 0
1 A 0 0 0 0 1 1

2 B 0 1 1 1 1 2

3 C 0 1 1 2 2 2
4 B 0
if (xi = yj) then c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max(c[i-1,j], c[i,j-1])
59
 Longest common subsequence

• Dynamic programming algorithm (13)

• Example j 0 1 2 3 4 5
i yj B D C A B
0 xi 0 0 0 0 0 0
1 A 0 0 0 0 1 1

2 B 0 1 1 1 1 2

3 C 0 1 1 2 2 2
4 B 0 1
if (xi = yj) then c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max(c[i-1,j], c[i,j-1])
60
 Longest common subsequence

• Dynamic programming algorithm (14)

• Example j 0 1 2 3 4 5
i yj B D C A B
0 xi 0 0 0 0 0 0
1 A 0 0 0 0 1 1

2 B 0 1 1 1 1 2

3 C 0 1 1 2 2 2
4 B 0 1 1 2 2
if (xi = yj) then c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max(c[i-1,j], c[i,j-1])
61
 Longest common subsequence

• Dynamic programming algorithm (15)

• Example j 0 1 2 3 4 5
i yj B D C A B
0 xi 0 0 0 0 0 0
1 A 0 0 0 0 1 1

2 B 0 1 1 1 1 2

3 C 0 1 1 2 2 2
4 B 0 1 1 2 2 3
if (xi = yj) then c[i,j] = c[i-1,j-1] + 1
else c[i,j] = max(c[i-1,j], c[i,j-1])
62
 Longest common subsequence

• Dynamic programming algorithm (16)

• Complexity assessment
• Algorithm to calculate array c with nxm elements
• Compute each element in O(1) time
• So the running time of the algorithm is O(nm)

63
 Longest common subsequence

• Dynamic programming algorithm (17)

• Building the optimal solution
• LCS-length algorithm only calculates the length of the longest common
subsequence
• Need to determine the longest common subsequence
• Similar to the matrix chain multiplication algorithm, use the array
b[1..n,1..m] to store the elements of array c corresponding to the optimal
solution
– When c[i,j] = c[i-1,j-1] + 1 then memorize xi , because xi belongs to the longest
common subsequence
• Starting from c[m,n] and working backwards
– If c[i,j] = c[i-1,j-1] + 1 then xi belongs to the longest common subsequence
– If i = 0 or j = 0 then stop
• Reverse the sequence of symbols to get the longest common subsequence

64
 Longest common subsequence

• Dynamic programming algorithm (18)

• Example j 0 1 2 3 4 5
i Yj B D C A B
0 Xi 0 0 0 0 0 0
A
1 0 0 0 0 1 1

2 B 0 1 1 1 1 2
3 C 0 1 1 2 2 2
4 B 0 1 1 2 2 3
Longest common subsequence (reverse order): BCB
Longest common subsequence: BCB
65
 Longest common subsequence

• Dynamic programming algorithms (20)

• LCS-length algorithm, saving optimal solution into array b
LCS-length (X,Y)
begin
n = length(X), m = length(Y)
for i from 0 to n do c[i,0]=0 endfor
for j from 0 to m do c[0,j]=0 endfor
for i from 1 to n do
for j from 1 to m do
if (xi = yj) then
c[i,j] = c[i-1,j-1] + 1
b[i,j] = '\'
else
if (c[i-1,j] < c[i,j-1]) then
c[i,j] = c[i,j-1]
b[i,j] = '  ‘
else c[i,j] = c[i-1,j]
b[i,j] = '  '
endif endif endfor endfor
return c
end 66
 Longest common subsequence

• Dynamic programming algorithm (19)

• Building the optimal solution
print-LCS(b, X, i, j)
begin
if (i = 0 or j = 0) then
return
else
if (b[i,j] = '\') then //xi belongs to the longest common subsequence
print-LCS(b,X,i-1,j-1)
print xi
else
if (b[i,j]=‘’) then
print-LCS(b,X,i,j-1)
else //(b[i,j]=‘’)
print-LCS(b,X,i-1,j)
endif
endif
endif
end
67
 Backpacking

• Problem
• There is a backpack that can hold at most a weight W. There are n objects, each
object has a weight wi and a value bi
• W, wi and bi are integers
• Put the items in the backpack so that the total value of the backpack is the
largest
• Example
Objects Weight - wi Value - bi
2 8

5 10

3 6
W = 12

Backpack 9 2

4 3
68
 Backpacking
• Brute force algorithm
• There are n objects, so there are 2n subsets of objects of the set of n objects
• Iterate through all 2n subsets of objects and select the set with the largest total
value whose total weight is less than W

• The algorithm complexity is O(2n)

• Exponential function!

69
 Backpacking
• Divide and conquer algorithm (1)
• The problem can be divided into subproblems
• Instead of considering k objects, consider k-1 objects…
• Let vk,w be the maximum total value of the backpack whose weight does not
exceed w when using only 1…k objects
• For each object k, we need to answer the question:
• Can the current backpack contain object k?
• Answer
• If the current remaining weight w of the backpack is less than wk then the
backpack cannot contain object k
• On the contrary, w  wk then two cases occur:
– Don't add object k into the backpack, use only 1…k-1 objects
– Add object k to the backpack, then the value of the backpack increases by bk but the
remaining weight of the backpack decreases by wk (i.e. equal to w-wk)
– The case giving the largest total value of the backpack will be selected

70
 Backpacking

• Divide and conquer algorithm (2)

• So, vk,w is calculated as follows

vk 1, w if wk  w
vk , w 
max{vk 1, w , vk 1, w wk  bk } else
• Explanation
• If wk > w, it is not possible to add object k to the backpack, only consider
objects 1…k-1 (including k-1 objects)
• If wk  w,
– If using only objects 1…k-1 gives the largest total backpack value, then don't use
object k
– Use object k if the total value of the backpack is the largest, then consider
objects 1…k-1 with the remaining weight of the backpack being w-wk

71
 Backpacking

• Divide and conquer algorithm (3)

• Note that, vk,w = 0 if k = 0
• So the full formula to calculate vk,w is

 0 k 0

vk , w   vk 1, w wk  w
max(v
 k 1, w , vk 1, w  wk  bk ) wk  w

• The optimal solution of the problem is the value of vn,W

72
 Backpacking

• Divide and conquer algorithm (4)

backpack (k, w)
begin
if (k = 0) then return 0
else
if (wk > w) then
return backpack(k-1,w) // don't use object k
else
x = backpack(k-1,w)
y = backpack(k-1,w-wk) + bk
return (max(x, y))
endif
endif
end

Use: backpack(n, W)
73
 Backpacking

• Divide and Conquer Algorithm (5)

• Complexity assessment
• Let C(n) be the worst case complexity
• From the algorithm, we have the recurrence relation
c n0
C ( n)  
 maxC (n  1),2C (n  1)   d n0
c n0

2C (n  1)  d n0
where c and d are constants

• So the complexity of the algorithm is O(2n )

– Exponential function!

74
 Backpacking

• Dynamic programming algorithm (1)

• Use the array v[0..n,0..W] to store the solutions of the subproblems
• v[k,w] is the maximum total value of the backpack whose weight does
not exceed w when using only objects 1…k
• Initially
v[0,w] = 0 for all w
v[k,0] = 0 for all k
• Then v[k,w] will be calculated according to v[k-1,w] or v[k-1,w-wk]

75
 Backpacking

• Dynamic programming algorithm (2)

backpack (n, W)
begin
for k from 0 to n do v[k,0] = 0 endfor
for w from 0 to W do v[0,w] = 0 endfor
for k from 1 to n do
for w from 1 to W do
if (wk  w) then //can use object k
v[k,w] = max(v[k-1,w], v[k-1,w-wk] + bk)
else //wk > w
v[k,w] = v[k-1,w] // do not use object k
endif
endfor
endfor
end

76
 Backpacking

• Dynamic programming algorithm (3)

backpack (n, W)
begin
for k from 0 to n do v[k,0] = 0 endfor
for w from 0 to W do v[0,w] = 0 endfor
for k from 1 to n do
for w from 1 to W do
if (wk  w) then //can use object k
if (bk + v[k-1,w-wk ] > v[k-1,w]) then
v[k,w] = bk + v[k-1,w-wk ] // use object k
else
v[k,w] = v[k-1,w] // do not use object k
endif
else //w k > w
v[k,w] = v[k-1,w] // do not use object k
endif
endfor
endfor
end
77
 Backpacking

• Dynamic programming algorithm (4)

• Complexity assessment
• Algorithm to calculate nxW element array using two nested loops
• Running time O(nW)

• Example (1)
W = 5 (maximum weight the backpack can hold)
n = 4 (4 objects)
The objects have (weight, value) in order:
(2,3), (3,4), (4,5), (5,6)

78
 Backpacking
Example (2)
k 0 1 2 3 4
W
0 0
1 0
2 0
3 0
4 0
5 0

for w = 0 to W do v[0,w] = 0

79
 Backpacking
Example (3)
k 0 1 2 3 4
W
0 0 0 0 0 0
1 0
2 0
3 0
4 0
5 0

for k = 0 to n do v[k,0] = 0

80
 Backpacking
Example (4)
k 0 1 2 3 4 Objects
W
0 0 0 0 0 0
1: (2,3)
k=1 2: (3,4)
1 0 0
bk= 3 3: (4,5)
2 0
wk =2 4: (5,6)
3 0
4 0 w= 1
5 0 w-wk=-1
if wk <= w then // the object cannot be used
if bk + v[k-1,w-wk ] > v[k-1,w] then
v[k,w] = bk + v[k-1,w-wk ]
else
v[k,w] = v[k-1,w]
else v[k,w] = v[k-1,w] // w k > w, object k is not used 81
 Backpacking
Example (5)
k 0 1 2 3 4 Objects
W
0 0 0 0 0 0 1: (2,3)
1 0 0
k=1 2: (3,4)
bk= 3 3: (4,5)
2 0 3
wk =2 4: (5,6)
3 0
4 0 w= 2
5 0 w-wk=0
if wk <= w then // the object cannot be used
if bk + v[k-1,w-wk ] > v[k-1,w] then
v[k,w] = bk + v[k-1,w-wk ]
else
v[k,w] = v[k-1,w]
else v[k,w] = v[k-1,w] // wk > w, object k is not used 82
 Backpacking
Example (6)
k 0 1 2 3 4 Objects
W
0 0 0 0 0 0
1: (2,3)
k=1 2: (3,4)
1 0 0
bk= 3 3: (4,5)
2 0 3
wk =2 4: (5,6)
3 0 3
4 0 w= 3
5 0 w-wk =1
if wk <= w then // the object cannot be used
if bk + v[k-1,w-wk ] > v[k-1,w] then
v[k,w] = bk + v[k-1,w-wk ]
else
v[k,w] = v[k-1,w]
else v[k,w] = v[k-1,w] // wk > w, item k is not used 83
 Backpacking
Example (7)
k 0 1 2 3 4 Objects
W
0 0 0 0 0 0
1: (2,3)
k=1 2: (3,4)
1 0 0
bk= 3 3: (4,5)
2 0 3
wk =2 4: (5,6)
3 0 3
4 0 3 w= 4
5 0 w-wk =2
if wk <= w then // the object cannot be used
if bk + v[k-1,w-wk ] > v[k-1,w] then
v[k,w] = bk + v[k-1,w-wk ]
else
v[k,w] = v[k-1,w]
else v[k,w] = v[k-1,w] // wk > w, object k is not used 84
 Backpacking
Example (8)
k 0 1 2 3 4 Objects
W
0 0 0 0 0 0
1: (2,3)
k=1 2: (3,4)
1 0 0
bk = 3 3: (4,5)
2 0 3
wk =2 4: (5,6)
3 0 3
4 0 3 w= 5
5 0 3 w-wk =2
if wk <= w then // the object cannot be used
if bk + v[k-1,w-wk ] > v[k-1,w] then
v[k,w] = bk + v[k-1,w-wk ]
else
v[k,w] = v[k-1,w]
else v[k,w] = v[k-1,w] // wk > w, object k is not used 85
 Backpacking
Example (9)
k 0 1 2 3 4 Objects
W
0 0 0 0 0 0
1: (2,3)
k=2 2: (3,4)
1 0 0 0
bk = 4 3: (4,5)
2 0 3
wk =3 4: (5,6)
3 0 3
4 0 3 w= 1
5 0 3 w-wk=-2
if wk <= w then // the object cannot be used
if bk + v[k-1,w-w k ] > v[k-1,w] then
v[k,w] = bk + v[k-1,w-wk ]
else
v[k,w] = v[k-1,w]
else v[k,w] = v[k-1,w] // w k > w, object k is not used 86
 Backpacking
Example (10)
k 0 1 2 3 4 Objects
W
0 0 0 0 0 0
1: (2,3)
k=2 2: (3,4)
1 0 0 0
bk = 4 3: (4,5)
2 0 3 3
wk =3 4: (5,6)
3 0 3
4 0 3 w= 2
5 0 3 w-wk=-1
if wk <= w then // the object cannot be used
if bk + v[k-1,w-w k ] > v[k-1,w] then
v[k,w] = bk + v[k-1,w-wk ]
else
v[k,w] = v[k-1,w]
else v[k,w] = v[k-1,w] // w k > w, object k is not used 87
 Backpacking
Example (11)
k 0 1 2 3 4 Objects
W
0 0 0 0 0 0
1: (2,3)
k=2 2: (3,4)
1 0 0 0
bk = 4 3: (4,5)
2 0 3 3
wk =3 4: (5,6)
3 0 3 4
4 0 3 w= 3
5 0 3 w-wk =0
if wk <= w then // the object cannot be used
if bk + v[k-1,w-wk ] > v[k-1,w] then
v[k,w] = b k + v[k-1,w-w k ]
else
v[k,w] = v[k-1,w]
else v[k,w] = v[k-1,w] // wk > w, object k is not used 88
 Backpacking
Example (12)
k 0 1 2 3 4 Objects
W
0 0 0 0 0 0
1: (2,3)
k=2 2: (3,4)
1 0 0 0
bk = 4 3: (4,5)
2 0 3 3
wk =3 4: (5,6)
3 0 3 4
4 0 3 4 w= 4
5 0 3 w-wk =1
if wk <= w then // the object cannot be used
if bk + v[k-1,w-wk] > v[k-1,w] then
v[k,w] = bk + v[k-1,w-wk]
else
v[k,w] = v[k-1,w]
else v[k,w] = v[k-1,w] // wk > w, object k is not used 89
 Backpacking
Example (13)
k 0 1 2 3 4 Objects
W
0 0 0 0 0 0
1: (2,3)
k=2 2: (3,4)
1 0 0 0
bk = 4 3: (4,5)
2 0 3 3
wk =3 4: (5,6)
3 0 3 4
4 0 3 4 w= 5
5 0 3 7 w-wk =2
if wk <= w then // the object cannot be used
if bk + v[k-1,w-wk ] > v[k-1,w] then
v[k,w] = bk + v[k-1,w-wk ]
else
v[k,w] = v[k-1,w]
else v[k,w] = v[k-1,w] // wk > w, object k is not used 90
 Backpacking
Example (14)
k 0 1 2 3 4 Objects
W
0 0 0 0 0 0
1: (2,3)
k=3 2: (3,4)
1 0 0 0 0
bk = 5 3: (4,5)
2 0 3 3 3
wk =4 4: (5,6)
3 0 3 4 4
4 0 3 4 w= 1..3
5 0 3 7 w-wk <0
if wk <= w then // the object cannot be used
if bk + v[k-1,w-wk ] > v[k-1,w] then
v[k,w] = bk + v[k-1,w-wk ]
else
v[k,w] = v[k-1,w]
else v[k,w] = v[k-1,w] // w k > w, item k is not used 91
 Backpacking
Example (15)
k 0 1 2 3 4 Objects
W
0 0 0 0 0 0
1: (2,3)
k=3 2: (3,4)
1 0 0 0 0
bk = 5 3: (4,5)
2 0 3 3 3
wk =4 4: (5,6)
3 0 3 4 4
4 0 3 4 5 w= 4
5 0 3 7 w-wk =0
if wk <= w then // the object cannot be used
if bk + v[k-1,w-wk ] > v[k-1,w] then
v[k,w] = bk + v[k-1,w-wk ]
else
v[k,w] = v[k-1,w]
else v[k,w] = v[k-1,w] // wk > w, object k is not used 92
 Backpacking
Example (16)
k 0 1 2 3 4 Objects
W
0 0 0 0 0 0
1: (2,3)
k=3 2: (3,4)
1 0 0 0 0
bk = 5 3: (4,5)
2 0 3 3 3
wk=4 4: (5,6)
3 0 3 4 4
4 0 3 4 5 w= 5
5 0 3 7 7 w-wk =1
if wk <= w then // the object cannot be used
if bk + v[k-1,w-wk ] > v[k-1,w] then
v[k,w] = bk + v[k-1,w-wk ]
else
v[k,w] = v[k-1,w]
else v[k,w] = v[k-1,w] // wk > w, object k is not used 93
 Backpacking
Example (17)
k 0 1 2 3 4 Objects
W
0 0 0 0 0 0
1: (2,3)
k=4 2: (3,4)
1 0 0 0 0 0
bk = 6 3: (4,5)
2 0 3 3 3 3
wk =5 4: (5,6)
3 0 3 4 4 4
4 0 3 4 5 5 w= 1..4
5 0 3 7 7 w-wk < 0
if wk <= w then // the object cannot be used
if bk + v[k-1,w-wk ] > v[k-1,w] then
v[k,w] = bk + v[k-1,w-wk ]
else
v[k,w] = v[k-1,w]
else v[k,w] = v[k-1,w] // wk > w, object k is not used 94
 Backpacking
Example (18)
k 0 1 2 3 4 Objects
W
0 0 0 0 0 0
1: (2,3)
k=4 2: (3,4)
1 0 0 0 0 0
bk = 6 3: (4,5)
2 0 3 3 3 3
wk =5 4: (5,6)
3 0 3 4 4 4
4 0 3 4 5 5 w= 5
5 0 3 7 7 7 w-wk =0
if wk <= w then // the object cannot be used
if b + v[k-1,w-wk ] > v[k-1,w] then
v[k,w] = bk + v[k-1,w-wk ]
else
v[k,w] = v[k-1,w]
else v[k,w] = v[k-1,w] // wk > w, object k is not used 95
 Backpacking

• Algorithm backpack only finds the maximum total that the backpack can
hold
• Exercise
• Building the optimal solution
• The objects contained in the backpack
• Illustration k 0 1 2 3 4
W
0 0 0 0 0 0
1 0 0 0 0 0
Used objects: 1, 2
2 0 3 3 3 3
3 0 3 4 4 4
4 0 3 4 5 5
5 0 3 7 7 7
96
 Exercises

• Problem 1
• Fibonacci numbers are defined
F0 = 1, F1 = 1
Fn = Fn-1 + Fn-2
Build dynamic programming algorithm computing Fn

• Problem 2
• Catalan numbers defined
1 n 1
 n 1
T ( n)  

T (i ).T (n  i ) n  1
i 1

Build dynamic programming algorithm computing Tn

97
 Exercises

• Problem 3
• Coin change: Given a set of coin denominations and a target amount, find the
minimum number of coins needed to make up the target amount. If it's not
possible to form the target amount, return −1 (no solution).
• Hint:
• Use an array dp[], where dp[i] represents the minimum number of coins needed to
form amount i.
• For each coin c, update dp[i] as: dp[i]=min(dp[i],dp[i−c]+1).

98
 Explanation

1 n 1
 n 1
P ( n)  

P(k ) P(n  k ) n  2
k 1

• Prove that P(n) = (2n )

• Prove by induction that P(n)  2n-2
• P(n) is true for n  4
• With n  5 n 1
P ( n)   P ( k ) P ( n  k )
k 1
n 1 n 1
 2 k 2
2 nk 2
 2 n  4  (n  1)2 n  4
k 1 k 1

 2 n  2 (do n  5)

• So P(n) = (2n )

99