Unit 4

Dynamic Programming
 Introduction
• Dynamic Programming is invented by a U.S. Mathematician Richard
Bellman in 1950.
• In the word dynamic programming the word programming
stands for planning and it does not mean by computer
programming.
– Dynamic programming is technique for solving problems with
overlapping sub problems.
– In this method each sub problem is solved only once. The result of each
sub-problem is recorded in a table from which we can obtain a solution
to the original problem.
 Difference between Divide and Conquer and
Dynamic Programming
Divide and Conquer Dynamic Programming
Divide-and-conquer is a top - down method Dynamic Programming is a bottom-up
technique.
In Divide and Conquer the sub problems In Dynamic Programming the sub problems are
are independent of each other. not independent.
Divide and Conquer does more work on the Dynamic Programming solves the sub problem
sub problems. only once and then stores it in table.
Has more time consumption. Has less time consumption.
Divide and Conquer splits its input at Dynamic Programming spilt its input at every
specific deterministic points usually in the possible split points rather than at a particular
middle. point. After trying all split points it determines
which split point is optimal.
Problem solving using dynamic programming
• Calculating the binomial coefficient
• Making change problem
• Assembly line scheduling
• Knapsack problem
• Shortest path
• Matrix chain multiplication
 Calculating the binomial coefficient
• Calculating the binomial coefficient
– Consider the problem of calculating the binomial coefficient

Suppose 0 <= k <= n. If we calculate (nk) directly by

function C(n, k)
If k = 0 or k = n then return 1
else return C(n -1, k - 1) +C(n -1, k)
many of the values C(i, j), i < n, j < k, are calculated over and over.
For example, the algorithm calculates C(5,3) as the sum of
C(4,2) and C(4,3).
• This algorithm is sure to be in
0 1 2 3 4 5 … k-1 k
0 1

1 1 1 Pascal’s Triangle
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
5 1 5 10 10 5 1
....
n-1
n
 Making change (2)
To solve this problem by dynamic programming, we set up a table c[1. ..n, 0.. N], with
one row for each available denomination and one column for each amount from 0
units to N units.

⚫ In this table c[i, j] will be the minimum number of coins required to pay an amount of j
units, 0 <= j <= N, using only coins of denominations 1 to i, 1 <= i <= n.

⚫ The solution to the instance is therefore given by c [n, N] if all

we want to know is how many coins are needed.

⚫ To fill in the table, note first that c [ i, 0] is zero for every value of i. After this
initialization, the table can be filled either row by row from left to right, or column by
column from top to bottom.
Algorithm
 Example
For example, suppose we live where there are coins for 1, 4 and 6 units

Amount : 0 1 2 3 4 5 6 7 8
d1 = 1 0 1 2 3 4 5 6 7 8
d2 = 4 0 1 2 3 1 2 3 4 2
d3 = 6 0 1 2 3 1 2 1 2 2
Last row-Last Column C[n , N] = 2
It indicates that any 2 coins are required to pay 8 units. But it does not give idea about which
coins.
 To find which coins are required :
⚫ If c[i, j]= c [i -1, j], no coins of denomination i are necessary, and we
move up to c[i - 1,j] to see what to do next;
if c[i , j] = 1 + c[i , j - di], then we hand over one coin of denomination i, worth di, and move
left to c[i, j - di] to see what to do next.
If c[i -1, j] and 1 + c[i, j - di] are both equal to c[i, j], we may choose either course of action.
Continuing in this way, we eventually arrive back at c[0, 0], and now there remains nothing to
pay.

Amount : 0 1 2 3 4 5 6 7 8
d1 = 1 0 1 2 3 4 5 6 7 8
d2 = 4 0 1 2 3 1 2 3 4 2
d3 = 6 0 1 2 3 1 2 1 2 2
Hand over first Coin = 4 Hand over Second Coin = 4
Analysis
⚫ Analysis of the algorithm is straightforward. To see how many coins are
needed to make change for N units when n different denominations are
available, the algorithm has to fill up an n x (N + 1) array, so the
execution time is in ϴ(nN).

⚫ Tosee which coins should be used, the search back from c [n, N] to c [0,
0] makes n- 1 steps to the row above (corresponding to not using a coin
of the current denomination) and c [n, N] steps to the left
(corresponding to handing over a coin). Since each of these steps can
be made in constant time, the total time required is in ϴ(n + c[n,N]).
Example
⚫ Given coins of denominations 2, 4 and 5 with amount to be pay is 7. find
optimum number of coins and sequence of coins used to pay given amount
using dynamic method.

d1= 2 , d2 = 4 , d3 = 5. (GTU Summer-2013 Marks-7)

0 1 2 3 4 5 6 7

d1= 2
0 ∞ 1 ∞ 2 ∞ 3 ∞

0 ∞ 1 ∞ 1 ∞ 2 ∞
d2= 4
0 ∞ 1 ∞ 1 1 2 2
d3= 5
0/1 Knapsack Problem
(Using Dynamic Programming)
 0/1 Knapsack Problem

⚫ For i = 1, 2,..., n, suppose that object i has a positive weight wi and a positive value vi. The
knapsack can carry a weight not exceeding W. Our aim is again to fill the knapsack in a way
that maximizes the value of the included objects, while respecting the capacity constraint.
⚫ This time, however, we suppose that the objects may not be broken into smaller pieces, so
we may decide either to take an object or to leave it behind, but we may not take a
fraction of an object.
⚫ In symbol

⚫ where vi > 0, wi > 0 and xi ϵ {0, 1} for 1 <= i <= n.

 Cont . . .
⚫ To solve the problem by dynamic programming, we set up a table
V[1. .n, 0.. W], with one row for each available object, and one column for each weight from 0 to W.

⚫ In the table, V[i, j] will be the maximum value of the objects we can transport if the weight limit is j, 0
<= j <= W, and if we only include objects numbered from 1 to i, 1 <= i <= n. The solution of the instance
can therefore be found in V[n, W].

⚫ fill in the entries in the table using the general rule

V[i, j]= max(V[i - 1, j], V[i - 1, j - wi]+vi).

⚫ Initially we define V[0, j] = 0 as well as V[i, 0] = 0 when j >= 0 and i >=0, and
we define V [ i, j ] to be - ∞ for all i when j < 0.

⚫ Example :

W=11 1 2 3 4 5
Weight 1 2 5 6 7
Values 1 6 18 22 28
 ⚫ fill in the entries in the table using the general rule
V[i, j]= max(V[i - 1, j], V[i - 1, j - wi]+vi).
⚫ Initially we define V[0, j] = 0 as well as V[i, 0] = 0 when j >= 0 and i >=0, and we define V [ i, j ] to be - ∞
for all i when j < 0.
Example
W=11 1 2 3 4 5
Weight 1 2 5 6 7
Values 1 6 18 22 28

Amount : 0 1 2 3 4 5 6 7 8 9 10 11
w1=1 , v1= 1 0 1 1 1 1 1 1 1 1 1 1 1
w2=2 , v2= 6 0 1 6 7 7 7 7 7 7 7 7 7
w3=5 , v3=18 0 1 6 7 7 18 19 24 25 25 25 25

w4=6 , v4=22 0 1 6 7 7 18 22 24 28 29 29 40
w5=7 , v5=28 0 1 6 7 7 18 22 28 29 34 35 40
 ⚫ fill in the entries in the table using the general rule
V[i, j]= max(V[i - 1, j], V[i - 1, j - wi]+vi).
⚫ Initially we define V[0, j] = 0 as well as V[i, 0] = 0 when j >= 0 and i >=0, and we define V [ i, j ] to be - ∞
for all i when j < 0.
Example
W=11 1 2 3 4 5
W4 = 6 , v4=22 Weight 1 2 5 6 7
W3 = 5 , v3=18 Values 1 6 18 22 28

Amount : 0 1 2 3 4 5 6 7 8 9 10 11
w1=1 , v1= 1 0 1 1 1 1 1 1 1 1 1 1 1
w2=2 , v2= 6 0 1 6 7 7 7 7 7 7 7 7 7
w3=5 , v3=18 0 1 6 7 7 18 19 24 25 25 25 25

w4=6 , v4=22 0 1 6 7 7 18 22 24 28 29 29 40
w5=7 , v5=28 0 1 6 7 7 18 22 28 29 34 35 40
⚫ Which object we have to choose for optimal solution?
Same concept we can use what we have discussed in Making
change(2).

Ex. W = 11
Here value at last row and last column is 40
The value above 40 is also 40, means both are same so just
move up.
Again repeat above step, but here 40 and above value of 40 is not same so
perform below operation and move left.
11-6 = 5
move on column 5 with same row, so value is 18 now 18 + 22 = 40
this value is same as last value 40. so return that object no-4

Repeat above steps until first element of table.

Matrix Chain Multiplication
(Using Dynamic Programming)
 Matrix Chain Multiplication
⚫ Recall that the product C of a p x q matrix A and a q x r matrix B is the p x r
matrix given by

⚫ Algorithmically, we can express this as

for i  1 to p do
for j  1 to r do
C[i , j] 0
for k - 1 to q do
C[i , j]  C[i , j]+A[i , k]B[k , j]

⚫ from which it is clear that a total of pqr scalar multiplications are required to
calculate the matrix product using this algorithm.
Suppose now we want to calculate the product of more than two matrices. Matrix
multiplication is associative, so we can compute the matrix product
M = M1 M2 . . . Mn
in a number of ways, which all give the same answer:
M = (... ((M1 M2) M3 ) . . . Mn)
= (Ml (M2 (M3 . . . (Mn-1 Mn) . . . )))
= (. . . ((Ml M2 ) (M3 M4 )) . . . ), and so on.

⚫ The choice of a method of computation can have a considerable influence on

the time required. Suppose, for example, that we want to calculate the product
ABCD of four matrices, where A is 13 x 5, B is 5 x 89, C is 89 x 3, and D is 3
x 34. To measure the efficiency of the different methods, we count the number
of scalar multiplications involved.
 Chain of matrices
A is 13 x 5
B is 5 x 89
C is 89 x 3
D is 3 x 34
There are five essentially different ways
((AB)C)D 10582
(AB) (CD) 54201
(A(BC))D 2856
A((BC)D) 4055
A(B(CD)) 26418

For instance, using M = ((AB)C)D, we calculate successively

AB = 13 x 5 x 89 = 5785 multiplications (size of Matrix 13x89) (AB) C = 13 x 89 x 3 = 3471
multiplications ( Size of Matrix 13 x 3)
((AB)C)D = 13 x 3 x 34 = 1326 multiplications (Size of Matrix 13 x 34)
For a total of 10582 scalar multiplications.
The most efficient method is almost 19 times faster than the slowest.
 Dynamic Programming :
Suppose the dimensions of the matrices are given by a vector d[0.. n] such that the
matrix Mi, 1 <= i <= n, is of dimension di-1 x di. We build the table Mij diagonal by
diagonal: diagonal s contains the elements mij such that j - i = s.

Summing up, we fill the table mij using the following rules for s = 0,1..., n-
1.
Example
To apply this to the example, we want to calculate the product ABCD of four matrices,
where A is 13 x 5,
B is 5 x 89,
C is 89 x 3, and
D is 3 x 34.
0 1 2 3 4
The vector d is therefore 13 5 89 3 34

Here total matrices are 4. So setup 4x4 matrix.

0 S3

0 S2

0
0 S1
Cont..
⚫ For s = 1,

we have d= 0 1 2 3 4
13 5 89 3 34
m12 = d0 * d1 * d2 = 13 * 5 * 89 = 5785,
m23 = d1 * d2 * d3 = 5 * 89 * 3 = 1335,
m34 = d2 * d3 *d4 = 89 * 3 * 34=
9078.
0 5785
S3
0 1335
0 9078
0 S2
Cont..
⚫ Next, for s = 2 we obtain

0 5785 1530 S3
k=1
1845
0 1335 k=3 S2

0 9078 S1

0 S0
The complete array m is :

0 5785 1530 2856 S3 S 1 2 3 4

k=1 k=3
1 1 1 1 3
1845
0 1335 k=3
S2 2 2 2 3
9078 3 3 3
0 4 4
0 S1
 S 1 2 3 4

Develop s table using

1 1 1 1 3
s[i][j] = k 2 2 2 3
3 3 3
4 4
Algorithm display_matrix_order(s , i , j)
{
if( i = j ) then
print(“ A” i)
else
{
print “ ( ”
display_matrix_order( s , i , s[ i , j ] )
display_matrix_order( s , s[ i , j ] + 1 , j )
print “ ) ”
}
}
Using above algorithm we get the matrix chain order as (A1(A2A3))
A4
 1,4

1,3 4,4

1,1 2,3

2,2 3,3

(( A1 ( A2 A3 ) ) A4)
Example
Matrix Dimension
A1 5x4
A2 4x6
A3 6x2
A4 2x7

M 1 2 3 4 S 1 2 3 4
1 0 120 88 158 1 1 1 1 3
2 0 48 104 2 2 2 3
3 0 84 3 3 3
4 0 4 4
Longest Common Subsequence (LCS)
(Using Dynamic Programming)
 Longest Common Subsequence (LCS)
⚫ Problem Statement :
◦ Given two sequences, find the length of longest subsequence
present in both of them.
◦ A subsequence is a sequence that appears in the same relative order, but not
necessarily contiguous.

Example :
Find LCS for input Sequences X=“ABCDGH” and Y= “AEDFHR”.

Common subsequence from both is :

A AD
ADH 
Largest Common
subsequence
 length = 3
⚫ Q - Find length of Largest Common Subsequence (LCS) for input strings
“AGGTAB” and “GXTXAYB”.

Answer :
A AB GT
GTA
GTAB
 Largest Common
Subsequence
 length = 4

So it is very difficult to identify all the possible Common Sub Sequence.

So Use Dynamic Programming to find LCS.

Suppose we have one matrix c[m][n], m is length of first sequence a and m is length of second
sequence b. Fill this matrix using following algorithm.

Initially first row and first column will be 0.

Algorithm
for(i = 1 to m)
{ for(j = 1 to n)
{ if (ai = = bj)
then c[ i , j ] = c[ i - 1, j - 1] + 1
d[i , j] = “ ”;
else if (c[ i - 1, j ] >= c[ i , j - 1] )
then c[ i , j ] = c[ i - 1, j]
d[i , j] = “ ”;
else
c[ i , j ] = c[ i , j-1]
d[i , j] = “

”;
Example
⚫ Given two sequences of characters A = <X, Y , Z , Y ,T , X , Y>
B = <Y, T , Z , X , Y , X> obtain LCS.

Y T Z X Y X
0 0 0 0 0 0 0

X 0 0 0 0 1 1 1
Y 0 1 1 1 1 2 2

Z 0 1 1 2 2 2 2

Y 0 1 1 2 2 3 3
T 0 1 2 2 2 3 3
X 0 1 2 2 3 3 4
Y 0 1 2 2 3 4 4
So, Length of longest Common Sub Sequence = 4
 Steps to find the Common Subsequence
Y T Z X Y X
0 0 0 0 0 0 0

X 0 0 0 0 1 1 1
Y 0 1 1 1 1 2 2

Z 0 2
1 1 2 2 2

Y 0 1 1 2 2 3 3
T 0 1 2 2 2 3 3
X 0 1 2 2 3 3 4
Y 0 1 2 2 3 4 4

⚫ Lengthof LCS is = 4
⚫ Sequence of LCS = YZ YX
 Example (GTU Dec.2010 and Winter-2014 Marks-07)
⚫ Explain how to find out longest common subsequence of two strings using
dynamic programming.
S1 = abbacdcba S2 = bcdbbcaac

Prof.Amit G. Maru
Gyanmanjari Institute of Tech. Bhavnagar
 Example (GTU Dec.2010 and Winter-2018 Marks-07)

Find out LCS of A={K,A,N,D,L,A,P} and B = {A,N,D,L}

A N D L

K 0 0 0 0
A 1 1 1 1

N 1 2 2 2

D 1 2 3 3

L 1 2 3 4
A 1 2 3 4
P 1 2 3 4
Prof.Amit G. Maru
Gyanmanjari Institute of Tech. Bhavnagar
 Shortest Path
• The all pair shortest path is the problem of determining
shortest path distances between every pair of vertices in a
given graph.
• The use of this algorithm is in routing problems.
 Floyd-Warshall algorithm
• Let G = (N, A) be a directed graph; N is the set of nodes and A is the set
of edges. Each edge has an associated non-negative length. We want to
calculate the length of the shortest path between each pair of nodes.
• We construct a matrix D that gives the length of the shortest path
between each pair of nodes.
• Steps :
– The algorithm initializes L to D, that is, to the direct distances between nodes.
– It then does n iterations. After iteration k, D gives the length of the shortest
paths that only use nodes in { 1, 2, . . ., k } as intermediate nodes.
– After n iterations, D therefore gives the length of the shortest paths using any of
the nodes in N as an intermediate node, which is the result we want.
Example

Matrix to identify
Direct distances
the shortest path
between nodes.
D 1 2 3 4 Q 1 2 3 4

1 1 1 1 1
1 0 5 ∞ ∞ 2 2 2 2 2
2 50 0 15 5
3 3 3 3 3
3 30 ∞ 0 15
4 4 4 4 4
4 15 ∞ 5 0
 D 1 2 3 4 Q 1 2 3 4

1 0 5 ∞ ∞ 1 1 1 1 1
2 50 0 15 5 2 2 2 2 2
3 30 ∞ 0 15 3 3 3 3 3
4 15 ∞ 5 0 4 4 4 4 4

⚫ When k = 1 (if node 1 is intermediate node)

D 1 2 3 4 Q 1 2 3 4

∞ ∞ 1 1 1 1 1
1 0 5
2 50 0 15 5 2 2 2 2 2
3 30 35 0 15 3 3 1 3 3
4 15 20 5 0 4 4 1 4 4

4  1 = 15
1 1 =0 2  1 = 50 3  1 = 30
4  1  1 = 15
2 2 =0 3 2 =∞ 4 2 =∞
1 2 =5
2  1  2 = 55 3  1  2 = 35 4  1  2 = 20
1 3 =∞ 2  3 = 15 3 3 =0 4 3 =5
413=∞
3  4 = 15
1 4 =∞ 2 4 =5 4 4 =0
313=∞
 D 1 2 3 4 Q 1 2 3 4

1 0 5 ∞ ∞ 1 1 1 1 1
2 50 0 15 5 2 2 2 2 2
3 30 35 0 15 3 3 1 3 3
4 15 20 5 0 4 4 1 4 4

⚫ When k = 2 (if node 2 is intermediate node)

D 1 2 3 4 Q 1 2 3 4
1 1 1 2 2
1 0 5 20 10
2 50 0 15 5 2 2 2 2 2
3 30 35 0 15 3 3 1 3 3
4 15 20 5 0 4 4 1 4 4

1 1 =0 3  1 = 30 4  1 = 15
2  1 = 50
1  2  1 = 55 3  2  1 = 85 4  2  1 = 70

1 2 =5 2 2 =0 3  2 = 35 4  2 = 20

1 3 =∞ 2  3 = 15 3 3 =0 4 3 =5
1  2  3 = 20 4  2  3 = 35
1 4 =∞ 3  4 = 15
2 4 =5 4 4 =0
1  2  4 = 10 3  2  4 = 40
⚫ When k = 3 (if node 3 is intermediate node)

D 1 2 3 4 Q 1 2 3 4

1 0 5 20 10 1 1 1 2 2
2 45 0 15 5 2 3 2 2 2
3 30 35 0 15 3 3 1 3 3
4 15 20 5 0 4 4 1 4 4

⚫ When k = 4 (if node 4 is intermediate node)

D 1 2 3 4 Q 1 2 3 4
1 1 1 4 2
1 0 5 15 10
2 20 0 10 5 2 4 2 4 2
3 30 35 0 15 3 3 1 3 3
4 15 20 5 0 4 4 1 4 4
 How to find the path

D 1 2 3 4 Q 1 2 3 4
1 1 1 4 2
1 0 5 15 10
2 20 0 10 5 2 4 2 4 2
3 30 35 0 15 3 3 1 3 3
4 15 20 5 0 4 4 1 4 4

Find shortest distance and path from 1 to 3

Shortest distance is = 15
Shortest Path is = 1 2 4 3
Floyd's algorithm
 Analysis
As we have seen in Floyd’s algorithm, three loops are used
k outer loop
i loop for rows and j loop for column

So, it is obvious that this algorithm takes a time in ϴ(n3 ). Hence, t(n) ϵ

ϴ(n3 )

Prof.Amit G. Maru Gyanmanjari Institute of Tech. Bhavnagar

Thank You