Module 05:

Dynamic Programming
 Module Outline:
1. Fundamentals of Dynamic programming based
solution approach
2. 0/1 Knapsack
3. Shortest path using Floyd Warshall
4. Matrix Chain Multiplication
5. Coinage problem
6. Longest common subsequence
7. Longest increasing sequence
8. String editing
 Dynamic Programming (DP)
• Like divide-and-conquer, solve problem by combining
the solutions to sub-problems.
• Differences between divide-and-conquer and DP:
– Solving sub-problems independently and recursively, (so
same sub(sub)problems solved repeatedly)
– Sub-problems are dependent, i.e., sub-problems share
sub-sub-problems, every sub(sub)problem solved just once,
solutions to sub(sub)problems are stored in a table and
used for solving higher level sub-problems.
• Differences between Greedy and DP :
Greedy method have a local choice of the sub-problems
whereas DP would solve the all sub-problems and then select
one that would lead to an optimal solution i.e., at every step
we take a decision(principle of optimality)

3
 Example:
Definition of Fibonacci series for n:
F(n) = F(n-1) + F(n-2), with F(0) = F(1) = 1.
The first several are:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,…
 See CLRS Problem 4-4 for a

Candidate algorithm walkthrough of how fast the

Fibonacci numbers grow!

• def Fibonacci(n):
– if n == 0 or n == 1:
• return 1
– return Fibonacci(n-1) + Fibonacci(n-2)

5
 What’s going on? That’s a lot of
Consider Fib(8) repeated
computation!

6 7

4 5 5 6

2 3 3 4 3 4 4 5

0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4

1 2 etc
0 1 1 2
0 1 0 1 1 2 0 1 0 1 0 1 1 2
6
0 1 0 1 0 1 0 1
Maybe this would be better:
8 def fasterFibonacci(n):
• F = [1, 1, None, None, …, None ]
• \\ F has length n + 1
• for i = 2, …, n:
7
• F[i] = F[i-1] + F[i-2]
• return F[n]

6 Much better running time!

1
7
0
 Properties of DP:
1. Optimal sub-structure: Optimal solutions to
sub-problems can be used to find the optimal
solution of the original problem.
Ex: Fibonacci: F(i) for i≤n, F(i+1) = F(i)+ F(i -1)
2. Overlapping sub-problems: The subproblems
show up again and again
Ex: Fibonacci: Both F[i+1] and F[i+2] directly
use F[i] and lots of different F[i+x] indirectly
use F[i].
 Typical steps of DP
• Characterize the structure of an optimal
solution.
• Recursively define the value of an optimal
solution.
• Compute the value of an optimal solution.
• Compute an optimal solution from
computed/stored information.

9
 Memorization
• Idea:
– Each entry in table initially contains a value indicating
the entry has yet to be filled in.
– When a subproblem is first encountered, its solution
needs to be solved and then is stored in the
corresponding entry of the table.
– If the subproblem is encountered again in the future,
just look up the table to take the value.

10
0/1 Knapsack Problem
 0-1 Knapsack problem
• Given a knapsack with maximum capacity W,
and a set S consisting of n items
• Each item i has some weight wi and benefit
value bi (all wi , bi and W are integer values)
• Problem: How to pack the knapsack to achieve
maximum total value of packed items?
0-1 Knapsack problem: a picture
 0/1 Knapsack Problem
Optimization criteria is to maximize the
benefit value while maintaining the knapsack
weight less than or equal to its capacity
Optimal Substructure of 0/1 Knapsack
problem

If items are labeled 1..n, then a

subproblem would be to find an optimal
solution for Sk = {items labeled 1, 2, .. k}
 Recursive Formula for
subproblems

Recursive formula for subproblems:

It means, that the best subset of Sk that has total

weight w is:
1. the best subset of Sk-1 that has total weight w, or
2. the best subset of Sk-1 that has total weight w-wk plus
the item k
 Recursive Formula for
subproblems

The best subset of Sk that has the total weight w,

either contains item k or not.
• First case: wk>w. Item k can’t be part of the solution,
since if it was, the total weight would be > w, which is
unacceptable.
• Second case: wk <= w. Then the item k can be in the
solution, and we choose the case with greater value.
 0-1 Knapsack Algorithm
for w = 0 to W
B[0,w] = 0
for i = 1 to n
B[i,0] = 0
for i = 1 to n
for w = 0 to W
if wi <= w // item i can be part of the solution
if bi + B[i-1,w-wi] > B[i-1,w]
B[i,w] = bi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
else B[i,w] = B[i-1,w] // wi > w

running time of this algorithm = O(W*n)

 Example
Let’s run our algorithm on
the
following data:
n = 4 (# of elements)
W = 5 (max weight)

Elements (weight, benefit):

(2,3), (3,4), (4,5), (5,6)
Elements (weight, benefit):
(2,3), (3,4), (4,5), (5,6)
Elements (weight, benefit):
(2,3), (3,4), (4,5), (5,6)
Elements (weight, benefit):
(2,3), (3,4), (4,5), (5,6)
Elements (weight, benefit):
(2,3), (3,4), (4,5), (5,6)
Elements (weight, benefit):
(2,3), (3,4), (4,5), (5,6)
Elements (weight, benefit):
(2,3), (3,4), (4,5), (5,6)
Elements (weight, benefit):
(2,3), (3,4), (4,5), (5,6)
Elements (weight, benefit):
(2,3), (3,4), (4,5), (5,6)
Elements (weight, benefit):
(2,3), (3,4), (4,5), (5,6)
Elements (weight, benefit):
(2,3), (3,4), (4,5), (5,6)

0
Elements (weight, benefit):
(2,3), (3,4), (4,5), (5,6)
Elements (weight, benefit):
(2,3), (3,4), (4,5), (5,6)
Elements (weight, benefit):
(2,3), (3,4), (4,5), (5,6)
Elements (weight, benefit):
(2,3), (3,4), (4,5), (5,6)
Elements (weight, benefit):
(2,3), (3,4), (4,5), (5,6)
Elements (weight, benefit):
(2,3), (3,4), (4,5), (5,6)
Elements (weight, benefit):
(2,3), (3,4), (4,5), (5,6)
 Finding the Items
Let i=n and k=W
if B[i,k] != B[i-1,k] then
mark the ith item as in the knapsack
i = i -1,
k = k - wi
else
i = i -1 // Assume the ith item is not in
the knapsack
Finding the Items
Finding the Items
Finding the Items
 Finding the Items

if B[i,k] != B[i-1,k] then

mark the ith item as in the knapsack
i = i -1,
k = k - wi
 Finding the Items

if B[i,k] != B[i-1,k] then

mark the ith item as in the knapsack
i = i -1,
k = k - wi
Finding the Items
Finding the Items
 All pairs shortest path through
Floyd-Warshall algorithm
• The problem: find the shortest path between every pair of vertices of a graph
• The graph: may contain negative edges but no negative cycles

• A representation: a weight matrix where

W(i,j)=“weight of edge”
W(i,j)=0 if i=j.
W(i,j)=∞ if there is no edge between i and j.

• Note: we have shown principle of optimality applies to shortest path problems

 The subproblems

• Let D(k)[i,j]=weight of a shortest path from vi

to vj using only vertices from {v1,v2,…,vk} as
intermediate vertices in the path
– D(0)=W
– D(n)=D which is the goal matrix

• How do we compute D(k) from D(k-1) ?

 The Recursive Definition:
Case 1: A shortest path from vi to vj restricted to using only vertices from
{v1,v2,…,vk} as intermediate vertices does not use vk.
Then D(k)[i,j]= D(k-1)[i,j].
Case 2: A shortest path from vi to vj restricted to using only vertices from
{v1,v2,…,vk} as intermediate vertices does use vk.
Then D(k)[i,j]= D(k-1)[i,k]+ D(k-1)[k,j].

Shortest path using intermediate vertices

{V1, . . . Vk }

Vk

Vj
Vi

Shortest Path using intermediate vertices { V1, . . . Vk -1 }

 The recursive definition
• Since
D(k)[i,j]= D(k-1)[i,j] or
D(k)[i,j]= D(k-1)[i,k]+ D(k-1)[k,j].
We conclude:
D(k)[i,j]= min{ D(k-1)[i,j], D(k-1)[i,k]+ D(k-1)[k,j] }.
Shortest path using intermediate vertices
{V1, . . . Vk } Vk

Vj
Vi

Shortest Path using intermediate vertices { V1, . . . Vk -1 }

 The pointer array P

• Used to enable finding a shortest path

• Initially the array contains 0

• Each time that a shorter path from i to j is found the k that

provided the minimum is saved (highest index node on the
path from i to j)

• To print the intermediate nodes on the shortest path a

recursive procedure that print the shortest paths from i and
k, and from k to j can be used
 Floyd's Algorithm Using n+1 D
matrices
Floyd//Computes shortest distance between all pairs of //nodes,
and saves P to enable finding shortest paths
1. D0 ← W // initialize D array to W [ ]
2. P ← 0 // initialize P array to [0]
3. for k ← 1 to n
4. do for i ← 1 to n
5. do for j ← 1 to n
6. if (Dk-1[ i, j ] > Dk-1 [ i, k ] + Dk-1 [ k, j ] )
7. then Dk[ i, j ] ← Dk-1 [ i, k ] + Dk-1 [ k, j ]
8. P[ i, j ] ← k;
9. else Dk[ i, j ] ← Dk-1 [ i, j ]
 Example
1 2 3
1 0 4 5
W = D0 =
2 2 0 ∞
1 5
3 ∞ -3 0
4 2 3
1 2 3
-3 1 0 0 0
2
P= 2 0 0 0
3 0 0 0
 1 1 2 3
5 D0 =
3
1 0 4 5 k=1
4 2 2
-3
2 0 ∞ Vertex 1 can be
2 3 ∞ -3 0
intermediate node
1 2 3

1
1 0 4 5 D1[2,3] = min( D0[2,3], D0[2,1]+D0[1,3] )
D =
2 2 0 7
= min (∝, 7)
=7
3 ∞ -3 0

1 2 3
D1[3,2] = min( D0[3,2], D0[3,1]+D0[1,2] )
1 0 0 0 = min (-3,∝)
P= 2 0 0 1 = -3
3 0 0 0
 1 D1 =
1 2 3 k=2
5 1 0 4 5
4 2 3 2 2 0 7 Vertices 1, 2
2
-3

1 2
3

3
∞ -3 0
can be
2
D =
1 0 4 5 intermediate
2 2 0 7
3 -1 -3 0
D2[1,3] = min( D1[1,3], D1[1,2]+D1[2,3] )
1 2 3 = min (5, 4+7)
1 0 0 0 =5
P= 2 0 0 1
3 2 0 0
D2[3,1] = min( D1[3,1], D1[3,2]+D1[2,1] )
= min (∝, -3+2)
= -1
 k=3
1 5 D2 =
1
1
0
2
4
3
5
Vertices 1, 2,
4 2
-3
3
2 2 0 7 3 can be
2 3 -1 -3 0

1 2 3
intermediate
1 0 2 5
3
D = D3[1,2] = min(D2[1,2], D2[1,3]+D2[3,2] )
2 2 0 7 = min (4, 5+(-3))
3 -1 -3 0 =2

1 2 3
1 D3[2,1] = min(D2[2,1], D2[2,3]+D2[3,1] )
0 3 0
= min (2, 7+ (-1))
P= 2 0 0 1 =2
3 2 0 0
 Matrix Chain Multiplication(MCM)
Problem Statement : Given a sequence of matrices, find the
most efficient way to multiply these matrices
The problem is to decide the sequence of the matrix
multiplications and not to just perform multiplication

Optimization Problem ????

.
least number of multiplication ???

Precondition for Matrix Multiplication

AXB=C
Compatibility of matrices for
multiplication??
Cost of multiplying the matrices??
 Example: Matrix Multiplication

Total no. Of multiplications = 2 X2X 3=

12
No. of multiplications
Total no. Of
for getting each
elements
element
 Multiplication when sequence of
matrices are involved
• A5x4 X B4x6 X C6x2 X D2x7 can be done in 5 possible
ways as matrix multiplication is associative
and all will give the same end result
• (A X B) X (C x D)
• ((A X B )X C)) X D
• (A X (B X C)) x D
• A X ((B X C) x D))
• A X (B X (C x D))
 Example
• Given the multiplication chain
A40x20 X B20x60 X C60x50
(A40x20 X B20 x60 )X C60x50 requires 40x 60x20 + 40x50x60
= 48000 + 120000 = 168000 multiplications
A40x20 X ( B20 x60 X C60x50) requires 40x50x20 + 20x50x60 =
40000 + 60000 =100000 multiplications
• A10x100, B100x5, C5x50
– If ((A ×B) ×C), 10 ×100 ×5 +10 ×5 ×50 =7500
– If (A ×(B ×C)), 10 ×100 ×50+100 ×5 ×50=75000
Cost of matrix multiplication is the number of scalar multiplication
(Different order of use of parenthesis will require different
58
number of scalar multiplications)
 MCM DP—order of matrix computations
m(1,1) m(1,2) m(1,3) m(1,4) m(1,5) m(1,6)
m(2,2) m(2,3) m(2,4) m(2,5) m(2,6)
m(3,3) m(3,4) m(3,5) m(3,6)
m(4,4) m(4,5) m(4,6)
m(5,5) m(5,6)
m(6,6)

59
 MCM DP Steps
• Constructing a parenthesization order for
the optimal solution.
– Since s[1..n,1..n] is computed, and s[i,j] is the
split position for AiAi+1…Aj , i.e, Ai…As[i,j] and
As[i,j] +1…Aj , thus, the parenthesization order
can be obtained from s[1..n,1..n] recursively,
beginning from s[k,k] for k=1 to n.

60
 A Recursive Algorithm for Matrix-Chain Multiplication
RECURSIVE-MATRIX-CHAIN(p,i,j) (called with(p,1,n))
1. if i=j then return 0
2. m[i,j]←∞
3. for k←i to j-1
4. do q← RECURSIVE-MATRIX-CHAIN(p,i,k)+
RECURSIVE-MATRIX-CHAIN(p,k+1,j)+p p p
i-1 k j
5. if q< m[i,j] then m[i,j] ←q
6. return m[i,j]

61
62
 C[1,2]

Cost
Matrix

k Matrix

C[1,2] = min{(C[1,1] + C[1,2] + 3 x 2 x 4}

= 24 [for k =1]
63
 C[1,2]

Cost
Matrix

k Matrix

C[1,2] = min{(C(1,1] + C[2,2] + 3 x 2 x 4}

= 24 [for k =1]
64
 C[2,3]

Cost
Matrix

k Matrix k

C[2,3] = min{(C(2,2] + C[3,3] + 2 x 4 x 2}

= 16 [for k =2]
65
Cost
Matrix C[3,4]

k Matrix
k

C[3,4] = min{(C(3,3] + C[4,4] + 4 x 2 x 5}

= 40 [for k =3]
66
 C[1,3]
Cost
Matrix

k=1
k Matrix

k=2
k=1

C[1,3] = min{(C(1,1] + C[2,3] + 3 x 2 x 2, C(1,2] +

C[3,3] + 3 x 4 x 2 }
=min(16 + 12, 24 + 24)
=min(28,48) 67
= 28 [for k =1]
C[2,4]=????
k=???

68
 1 2 3 4
1 0 24 28
2 0 16 36
3 0 40 C[2,4]
4 0
Cost
Matrix

k=3
k Matrix

C[2,4] = min{(………………}

69
 Recursion tree for the computation of
RECURSIVE-MATRIX-CHAIN(C,1,4)
C[1,4]= min [( C[1,1] + C[2,4] +d0 x d1 x d4]), C[1,2] + C[3,4] +d0 x d2 x d4]), C[1,3] +
C[4,4] +d0 x d3 x d4]))
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

70
 Final Matrix Entries

Cost
Matrix

1 2 3 4

k Matrix 1 1 1 3
2 2 3
3 3
4

71
 Cost of MCM
No of scalar Multiplications= 58
Using Cost matrix

Parenthesization :
Using k matrix
From 1 -4 use parenthesis at 3
((A1 x A2 x A3) x (A4))

From 1 -3 use parenthesis at 1

(A1) x (A2 x A3)) x (A4) 72
 Running Time for MCM
• #overall subproblems × #choices.
– O(n2) × O(n) = O(n3)
• The cost =costs of solving subproblems + cost of
making choice.
– choice cost is di-1dkdj.

73
 Making Change
• Given j, what’s the fewest coins required to make j in
change?
• Example:
– m = 4 different denominations of coins.
– Values d = [1 2 4 7]
• Compute how many coins needed to make change
for value j: coins(d,j)
• Does greedy work with d?
 DP Coins
• Given n types of coins (unlimited supplies)
• Make c in change.
• What’s min. # of coins required?
• Formulated as a DP problem.
 DP Coins
• Given n types of coins (unlimited supplies)
• Make j in change.
• What’s min. # of coins required?
• Formulated as a DP problem.
• i is the number of coin types remaining.
 Making Change
Given j, what’s the fewest “coins” required to make j in change?
j
Amount 0 1 2 3 4 5 6 7

i 1 0 1 2 3 4 5 6 7

c[i,j] = min. number of “coins” to make j change with coins 1..i.

 Making Change
j
Amount 0 1 2 3 4 5 6 7

i 1 0 1 2 3 4 5 6 7

c[i,j] = min. number of coins to make j change with coins 1..i.

 Making Change
j
Amount 0 1 2 3 4 5 6 7

i 1 0 1 2 3 4 5 6 7

2 0 1 ???

How does one compute c[2,2]?

 Making Change
j
Amount 0 1 2 3 4 5 6 7

i senine=1 0 1 2 3 4 5 6 7

seon=2 0 1 1

shum=4
+1
limnah=7

How does one compute c[2,2]?

 Making Change
j
Amount 0 1 2 3 4 5 6 7

i senine=1 0 1 2 3 4 5 6 7

seon=2 0 1 1 2

shum=4
+1
limnah=7

How does one compute c[2,2]?

 Making Change
j
Amount 0 1 2 3 4 5 6 7

i senine=1 0 1 2 3 4 5 6 7

seon=2 0 1 1 2 2

shum=4
+1
limnah=7
 Making Change
j
Amount 0 1 2 3 4 5 6 7

i senine=1 0 1 2 3 4 5 6 7

seon=2 0 1 1 2 2 3

shum=4
+1
limnah=7
 Making Change
j
Amount 0 1 2 3 4 5 6 7

i senine=1 0 1 2 3 4 5 6 7

seon=2 0 1 1 2 2 3

shum=4
+1
limnah=7
 Making Change
j
Amount 0 1 2 3 4 5 6 7

i 1 0 1 2 3 4 5 6 7

2 0 1 1 2 2 3 3 4

4 0 1 1 2 1 2 2 3

7 0 1 1 2 1 2 2 1
 Extracting a Solution
j
Amount 0 1 2 3 4 5 6 7

i 1 0 1 2 3 4 5 6 7

2 0 1 1 2 2 3 3 4

4 0 1 1 2 1 2 2 3

7 0 1 1 2 1 2 2 1

c[4,7]=c[4,7-7]+1,
so include a 7
Move to c[4,7-7].
 Extracting a Solution
j
Amount 0 1 2 3 4 5 6 7

i senine=1 0 1 2 3 4 5 6 7

seon=2 0 1 1 2 2 3 3 4

shum=4 0 1 2 3 1 2 2 3

limnah=7 0 1 2 3 1 2 2 1

c[4,0] = c[4-1,0] c[4,7]=c[4,7-7]+1,

Do nothing. so include a limnah
Move up. Move to c[4,7-7].
 Extracting a Solution
j
Amount 0 1 2 3 4 5 6 7

i 1 0 1 2 3 4 5 6 7

2 0 1 1 2 2 3 3 4

4 0 1 c[4,0]
2 = 3c[4-1,0]
1 2 2 3
Do nothing.
7 0 1 2 3 1 2 2 1
Move up.
i=n (no. of denominations)
k=required denomination c[4,7]=c[4,7-7]+1,
while(i>0)
{If c[i,k]==1+c[i,k-di]
so include a 7
denomArray[p]=di; Move to c[4,7-7].
k=k-di;}
i=i-1;
 Extracting a Solution
j
Amount 0 1 2 3 4 5 6 7

i 1 0 1 2 3 4 5 6 7

2 0 1 1 2 2 3 3 4

4 0 1 2 2 1 2 2 3

7 0 1 2 2 1 2 2 1
 Extracting a Solution
j
Amount 0 1 2 3 4 5 6 7

i 1 0 1 2 3 4 5 6 7

2 0 1 1 2 2 3 3 4

4 0 1 2 2 1 2 2 3

7 0 1 2 2 1 2 2 1

i=n (no. of denominations)

k=required denomination
while(i>0)
{If c[i,k]==1+c[i,k-di]
denomArray[p++]=di;
k=k-di;}
i=i-1;
 Extracting a Solution
j
Amount 0 1 2 3 4 5 6 7

i 1 0 1 2 3 4 5 6 7

2 0 1 1 2 2 3 3 4

4 0 1 2 2 1 2 2 3

7 0 1 2 2 1 2 2 1
 Algorithm in Pseudo-code
function coins(d, N)
Input: Array d[1..n] specifies the coinage;
N is the number of units for which to make change
Output: Minimum number of coins needed to make change for N units using coins from d

array c[1..n,0..N]
for i=1 to n do
c[i,0] = 0

for i=1 to n do
for j=1 to N do
if i=1 and j<d[i] then
c[i,j] = +infinity
else if i=1 then
c[i,j] = 1+c[1,j-d[1]]
else if j<d[i] then
c[i,j] = c[i-1,j]
else
c[i,j] = min(c[i-1,j],1+c[i,j-d[i]])
return c[n,N]

Time Complexity == O(N*n)

 Longest Common Subsequence (LCS)
• DNA analysis, two DNA string comparison.
• DNA string: a sequence of symbols A,C,G,T.
– S=ACCGGTCGAGCTTCGAAT
• Subsequence (of X): is X with some symbols left out.
– Z=CGTC is a subsequence of X=ACGCTAC.
• Common subsequence Z (of X and Y): a subsequence of X and also a
subsequence of Y.
– Z=CGA is a common subsequence of both X=ACGCTAC and
Y=CTGACA.
• Longest Common Subsequence (LCS): the longest one of common
subsequences.
– Z' =CGCA is the LCS of the above X and Y.
• LCS problem: given X=<x1, x2,…, xm> and Y=<y1, y2,…, yn>, find their
LCS.

93
LCS Intuitive Solution –brute force
• List all possible subsequences of X,
check whether they are also
subsequences of Y, keep the
longer one each time.
• Each subsequence corresponds to
a subset of the indices {1,2,…,m},
there are 2m. So exponential.

94
 LCS DP –step 1: Optimal Substructure
• Characterize optimal substructure of LCS.
• Theorem 15.1:
• Let X=<x1, x2,…, xm> (= Xm) and Y=<y1, y2,…,yn> (= Yn) and
Z=<z1, z2,…, zk> (= Zk) be any LCS of X and Y,
– 1. if xm= yn, then zk= xm= yn implies Zk-1 is the LCS of
Xm-1 and Yn-1.
– 2. if xm≠ yn, then zk ≠ xm implies Zk-1 is the LCS of Xm-1
and Yn.
– 3. if xm≠ yn, then zk ≠ yn implies Zk-1 is the LCS of Xm
and Yn-1.

95
 LCS DP –step 2:Recursive Solution
• What the theorem says:
– If xm= yn, find LCS of Xm-1 and Yn-1, then append xm.
– If xm ≠ yn, find LCS of Xm-1 and Yn and LCS of Xm and
Yn-1, take the longer one.
• Overlapping substructure:
– Both LCS of Xm-1 and Yn and LCS of Xm and Yn-1 will
need to solve LCS of Xm-1 and Yn-1.
• c[i,j] is the length of LCS of Xi and Yj .

c[i,j]= 0 if i=0, or j=0

c[i-1,j-1]+1 if i,j>0 and xi= yj,
max{c[i-1,j], c[i,j-1]} if i,j>0 and xi ≠ yj,

96
 LCS DP-- step 3:Computing the Length
of LCS
• c[0..m,0..n], where c[i,j] is defined as
above.
– c[m,n] is the answer (length of LCS).
• b[1..m,1..n], where b[i,j] points to the
table entry corresponding to the optimal
subproblem solution chosen when
computing c[i,j].
– From b[m,n] backward to find the LCS.

97
LCS DP Algorithm

98
LCS DP –step 4: Constructing LCS

99
LCS computation example

100
 References
1. Introduction to Algorithms, 3rd Edition (The
MIT Press) 3rd Edition
by Thomas H. Cormen, Charles E.
Leiserson, Ronald L. Rivest , Clifford Stein
(Presented Examples and Pseudo codes are
according to ref. 1)

101