Analysis and Design of Algorithms (ADA)

GTU # 3150703

Unit-4
Dynamic Programming

Dr. Gopi Sanghani

Computer Engineering Department
Darshan Institute of Engineering & Technology, Rajkot
gopi.sanghani@darshan.ac.in
9825621471
 Outline
Looping
 Introduction
 The Principle of optimality
 Problem Solving using Dynamic Programming – Calculating the
Binomial Coefficient
 Making Change Problem
 Knapsack Problem
 Assembly Line-Scheduling
 All Points Shortest Path
 Matrix Chain Multiplication
 Longest Common Subsequence
Introduction
Introduction  A box contains 4 stones worth $1400, $3000,
$4200 and $7100. They weigh 20, 50, 60 and
100 grams respectively.
 Your bag can only hold 110 grams.

 Greedy Approach

1400 3000 4200 7100

20 50 60 100
70 60 70 71

 The greedy algorithm selects the best

candidate with the highest profit, i.e., stone
worth $7100.

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 4

Introduction  A box contains 4 stones worth $1400, $3000,
$4200 and $7100. They weigh 20, 50, 60 and
100 grams respectively.
 Your bag can only hold 110 grams.

 But, the optimal choice would be to select the

two stones worth $3000 and $4200.

 Their combined weight is 110 grams, which

means they will fit into your bag and you will
get a profit of $7200.

 If there are 100 stones, how to efficiently find

the optimal answer?

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 5

The Principle of Optimality
 A dynamic-programming algorithm solves every sub-problem just once and then saves its
answer in a table.
 It avoids the work of re-computing the answer every time the sub problem is encountered.
 The dynamic programming algorithm obtains the solution using principle of optimality.
 The principle of optimality states that “in an optimal sequence of decisions or choices, each
subsequence must also be optimal.
 If it is not possible to apply the principle of optimality then it is almost impossible to obtain
the solution using the dynamic programming approach.

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 6

Binomial Coefficient
Introduction
  If you want to make a 2-person committee from a group of four people. How many different
combinations are possible?
 The number of ways to do this is given by .

Consider 4 people A, B, C, D. Now the different combinations for making a committee

of 2 persons from these 4 are;

A, B A, C A, D C, D B, D B, C

   

 Specifically, the binomial coefficient  counts the number of ways to form an unordered

collection of  items chosen from a collection of  distinct items.

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 8

Binomial Coefficient
 The definition of binomial coefficient is given as:

  ¿ 𝟏 𝒊𝒇 𝒌 =𝟎 𝒐𝒓 𝒌 =𝒏

() 𝒌
{
𝒏 = ¿ 𝒏 − 𝟏 + 𝒏 − 𝟏 𝒊𝒇 𝟎<𝒌 < 𝒏
(
𝒌 −𝟏 𝒌 )(
¿ 𝟎 𝑶𝒕𝒉𝒆𝒓𝒘𝒊𝒔𝒆
)

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

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 9

Binomial Coefficient
0 1 2 3 4 5 .. k
0 1
1 1 + 1
2 1 + 2 + 1
3 1 + 3 + 3 + 1 PASCAL’s
TRIANGLE
4 1 4 6 4 1
..
n
function C(n, k)
if k=0 or k=n then return 1
else return C(n-1, k-1) + C(n-1, k)
Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 10
Generalized Solution using Dynamic Programming
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 in a bottom-up fashion.
4. Construct an optimal solution from the computed information.

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 11

Make a Change Problem
Make Change Problem – Dynamic Programming Solution
 We need to generate a table 𝑐[𝑛][𝑁], where
1. 𝑛 = number of denominations
2. 𝑁= amount for which you need to make a change.

 
To generate table 𝒄[𝒊][𝒋] use following steps:
Step-1: Make 𝑓𝑜𝑟
Repeat step-2 to step-4 for the remaining matrix values
Optimal
Step-2: If then Sub-structure

Step-3: If then
Step-4: Otherwise

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 13

Make Change Problem – Dynamic Programming Solution
  Denominations: . Make a change of Rs. .
 Step-1:Make
Step-2: If then here
Step-3: If then
Step-4: Otherwise

𝑗
 
Amount
0 1 2 3 4 5 6 7 8
 𝒊=𝟏 0 1 2 3 4 5 6 7 8
 𝒊=𝟐 0 1 2 3 1 2
 𝒊=𝟑 0
min ⁡( 𝑐[1][5],
𝑚𝑖𝑛(𝑐
  1+𝑐[2][0])=min
[1][4 ], 1+𝑐 ⁡(4,1+0)=min ⁡(4,1)=1
[2][1])=𝑚𝑖𝑛(5,1+1)=𝑚𝑖𝑛(5,2)=2
Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 14
Make Change Problem – Dynamic Programming Solution
  Denominations: . Make a change of Rs. .
 Step-1:Make
Step-2: If then here
Step-3: If then
Step-4: Otherwise

𝑗
 
Amount
0 1 2 3 4 5 6 7 8
 𝒊=𝟏 0 1 2 3 4 5 6 7 8
 𝒊=𝟐 0 1 2 3 1 2 3 4 2
 𝒊=𝟑 0 1 2 3 1 2 1 2 2

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 15

Make Change Problem – Dynamic Programming Solution
 We can also find the coins to be included in the solution set as follows:
1. Start looking at c[3, 8] = c[2, 8] ⟹ So, not to include a coin with denomination 6.
2. Next go to c[2,8] ≠ c[1, 8] but c[2,8] = 1 + c[2,4]  )
 So, include a coin with denomination 4
3. Now, got to c[2,4] ≠ c[1,4] but c[2,4] = 1+ c[2,0]
 So, again include a coin with denomination 4
4. Go to c[2,0] = c[1,0] and stop.
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
0 1 2 3 1 2 3 4 2
0 1 2 3 1 2 1 2 2
Solution contains 2 coins with denomination 4
Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 16
0/1 Knapsack Problem
0/1 Knapsack Problem - Dynamic Programming Solution
  We need to generate table
1. where,
2.

 
To generate table use following steps:
Step-1: Make
Step-2: if then

Step-3: if then

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 18

0/1 Knapsack Problem - Dynamic Programming Solution
  Solve the following knapsack problem using dynamic programming technique.

1. and

Object
11 66 18
18 22
22 28
28
11 22 55 66 77

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 19

0/1 Knapsack Problem - Dynamic Programming Solution

if then
else

  𝒋 Knapsack Capacity
weight & value 0 1 2 3 4 5 6 7 8 9 10 11
0 1 1 1 1
0 1 6 7 7
0 1 6 7 7
0 1 6 7 7
0 1 6 7 7

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 20

0/1 Knapsack Problem - Dynamic Programming Solution

  
So,
So,
if then
else

  𝒋 Knapsack Capacity
weight & value 0 1 2 3 4 5 6 7 8 9 10 11
0 1 1 1 1 1 1 1 1 1 1 1
0 1 6 7 7 7 7 7 7 7 7 7
0 1 6 7 7 18 19 24 25 25 25 25
0 1 6 7 7 18 22 24 28 29 29 40
0 1 6 7 7 18 22 28 29 34 35 40

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 21

0/1 Knapsack Problem - Dynamic Programming Solution
 We can also find the objects to be carried in the knapsack as follows,
1. Start looking at V[5, 11] = V[4, 11] ⟹ So not to include object 5
2. Next go to V[4, 11] ≠ V[3, 11] but V[4, 11] = V[3,11-w4]+v4 = V[3, 5]+22 So include object 4
3. Now go to V[3,5] ≠ V[2,5] but V[3,5] = V[2,5-w3]+v3 = V[2,0]+18 So include object 3
4. Now V[2,0] = V[1, 0] and V[1,0] = V[0,0] ⟹ So objects 2 and 1 are not included.
𝑉  [𝑖][ 𝑗]=max ⁡(𝑉 [𝑖−1][ 𝑗],𝑽 [𝒊 −𝟏][ 𝒋− 𝒘 𝒊]+𝒗 𝒊)

weight & value 0 1 2 3 4 5 6 7 8 9 10 11

0 1 1 1 1 1 1 1 1 1 1 1
0 1 6 7 7 7 7 7 7 7 7 7
0 1 6 7 7 18 19 24 25 25 25 25
0 1 6 7 7 18 22 24 28 29 29 40
0 1 6 7 7 18 22 28 29 34 35 40
Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 22
Assembly Line Scheduling
Introduction
  An automobile chassis enters each assembly line, has parts added to it at a number of
stations, and a finished auto exits at the end of the line.
 There are two assembly lines, numbered .
 Each assembly line has stations, numbered

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 24

Introduction
  We denote the station on line by
 The station on line performs the same function as the station on line
 Corresponding stations and perform the same function but can take different amounts of time
and .

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 25

Introduction
  Entry times are: and ; exit times are: and
 After going through a station, a chassis can either:
 stay on same line at no cost, or
 transfer to other line: cost after is for

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 26

Assembly Line Scheduling - Example
 Using dynamic programming technique, find the fastest time to get through the entire factory
for the following:

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 27

Optimal Substructure
Step
   1:
 : the fastest time to get through the entire factory
 : the fastest time to get from the starting point through station .
 Base case: (getting through station )

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 28

Assembly Line Scheduling – Dynamic Programming Solution
 General Case: 𝑗 = 2, 3, …,𝑛 and 𝑖 = 1, 2 - Recursive solution

f *  min( f1[n]  x1 , f 2 [n]  x2 )

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 29

Assembly Line Scheduling – Dynamic Programming Solution

j=1 j=2 j=3 j=4 j=5 j=6

9 20 24 32 35
12 16 22 25 30 37
 

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 30

Assembly Line Scheduling – Dynamic Programming Solution

j=1 j=2 j=3 j=4 j=5 j=6

9 18 20 24 32 35
12 16 22 25 30 37
 

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 31

Assembly Line Scheduling – Dynamic Programming Solution

j=1 j=2 j=3 j=4 j=5 j=6

9 18 20 24 32 35
12 16 22 25 30 37

𝑀𝑖𝑛(18+3
  , 16+1+3)=min ( 21 ,20 )=¿ 20 ¿
Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 32
Assembly Line Scheduling – Dynamic Programming Solution

j=1 j=2 j=3 j=4 j=5 j=6

9 18 20 24 32 35
12 16 22 25 30 37
 𝑓 ∗ =𝑚𝑖𝑛 ( 𝑓 [ 𝑛 ] + 𝑥 , 𝑓 [ 𝑛 ] + 𝑥 )
1 1 2 2
  ∗
𝒇 =𝒎𝒊𝒏 ⁡( 𝟑𝟓+𝟑 , 𝟑𝟕+𝟐)=𝟑𝟖
Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 33
All Pair Shortest Path – Floyd’s
Algorithm
Introduction
  Given a directed, connected weighted graph for each edge , a weight is associated with each
edge.
 The all pairs of shortest paths problem is to find a shortest path from to for every pair of
vertices and in .
 Floyd’s algorithm is used to find all pair shortest path problem from a given weighted graph.
 As a result of this algorithm, it will generate a matrix, which will represent the minimum
distance from any node to all other nodes in the graph.
 At first, the output matrix is same as given cost matrix of the graph.
 As the algorithm proceeds, the output matrix will be updated with each vertex as an
intermediate vertex.
 The time complexity of this algorithm is , where is the number of vertices in the graph.

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 35

Floyd Algorithm - Example

15 Step: 2 Calculate the distance between each node

1 4 with node 1 as an intermediate node.
30 5
5 50 5 15
  1 2 3 4
1
D1 =
2 15 3 2
3
Step: 1 Initialization
4
  1 2 3 4
1
D0 = For node 2
2
3
4
No change

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 36

Floyd Algorithm - Example

15 Step: 2 Calculate the distance between each node

1 4 with node 1 as an intermediate node.
30 5
5 50 5 15
  1 2 3 4
1
D1 =
2 15 3 2

Step: 1 Initialization 3 𝟑𝟓
 
4
  1 2 3 4
1
D0 = For node 3
2
3
4

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 37

Floyd Algorithm - Example

15 Step: 2 Calculate the distance between each node

1 4 with node 1 as an intermediate node.
30 5
5 50 5 15
  1 2 3 4
1
D1 =
2 15 3 2
3
Step: 1 Initialization
4 𝟐𝟎
 

  1 2 3 4
1
D0 = For node 4
2
3
4

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 38

Floyd Algorithm - Example

15 Step: 3 Calculate the distance between each node

1 4 with node 2 as an intermediate node.
30 5
5 50 5 15
  1 2 3 4
1
D2 = 𝟐𝟎
  𝟏𝟎
 
2 15 3 2
3
Step: 1 Initialization
4
  1 2 3 4
1
D0 = For node 1
2
3
4
No change for Node 3 & 4
Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 39
Floyd Algorithm - Example

15 Step: 4 Calculate the distance between each node

1 4 with node 3 as an intermediate node.
30 5
5 50 5 15
  1 2 3 4
1
D3 =
2 15 3 2
3
Step: 1 Initialization
4
  1 2 3 4
1
D0 = For node 1
2
3
4
No change

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 40

Floyd Algorithm - Example

15 Step: 4 Calculate the distance between each node

1 4 with node 3 as an intermediate node.
30 5
5 50 5 15
  1 2 3 4
1
D3 =
2 15 3 2 𝟒𝟓
 
3
Step: 1 Initialization
4
  1 2 3 4
1
D0 = For node 2
2
3
4
No change for Node 4

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 41

Floyd Algorithm - Example

15 Step: 5 Calculate the distance between each node

1 4 with node 4 as an intermediate node.
30 5
5 50 5 15
  1 2 3 4
D4 =
2 3
1 𝟏𝟓
 
15 2
3
Step: 1 Initialization
4
  1 2 3 4
1
D0 = For node 1
2
3
4

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 42

Floyd Algorithm - Example

15 Step: 5 Calculate the distance between each node

1 4 with node 4 as an intermediate node.
30 5
5 50 5 15
  1 2 3 4
1
D4 =
2 15 3 2 𝟐𝟎
  𝟏𝟎
 
3
Step: 1 Initialization
4
  1 2 3 4
1
D0 = For node 2
2
3
4
No change for Node 3

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 43

Floyd Algorithm - Example

15 Step: 5 Calculate the distance between each node

1 4 with node 4 as an intermediate node.
30 5
5 50 5 15
  1 2 3 4
1
D4 =
2 15 3 2
3
Step: 1 Initialization
4
  1 2 3 4
1
D0 =
2 Final Solution
3
4

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 44

Floyd’s Algorithm
function Floyd(L[1..n, 1..n]):array [1..n, 1..n]
array D[1..n, 1..n]
D ← L
for k ← 1 to n do
for i ← 1 to n do
for j ← 1 to n do
D[i,j] ← min(D[i,j], D[i,k]+ D[k,j])
return D

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 45

Chain Matrix Multiplication
Introduction
 
  Let matrix and matrix are two given matrices for multiplication.
 The resultant matrix and

 So,
 
Where, and

 Suppose, matrix and matrix are given.

 The product and the dimension of matrix is
 The total number of scalar multiplications required will be,
 
𝒑∗𝒒 ∗𝒓=𝟐∗𝟑∗ 𝟐=𝟏𝟐

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 47

Matrix Chain Multiplication
  Now, we want to calculate the product of more than two matrices. Matrix multiplication is
associative.
 The product of four matrices can be fully parenthesized in distinct ways.

1
Dimension of

Dimension of

Dimension of
  10582
Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 48
Matrix Chain Multiplication
  Now, we want to calculate the product of more than two matrices. Matrix multiplication is
associative.
 The product of four matrices can be fully parenthesized in distinct ways.

1
Dimension of
2
3
Dimension of
4
5 Dimension of
  54201
Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 49
Matrix Chain Multiplication using Dynamic Programming
  Matrix table stores the cost of multiplications.

 
To generate use following steps:
Step-1: if then
Step-2: if then
Step-3: if then

𝑴[𝒊][ 𝒋]=𝒎𝒊𝒏⁡( 𝑴[𝒊][𝒌]+𝑴[𝒌+𝟏][ 𝒋]+𝑷 𝒊−𝟏 ∙ 𝑷𝒌 ∙𝑷 𝒋 )𝒘𝒊𝒕𝒉𝒊≤𝒌< 𝒋

 

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 50

Matrix Chain Multiplication using Dynamic Programming
  Here dimensions are,
 There would be matrices ),and

    Step-2:
Step-1: if if then
then
  [3][4 ]=𝑃012∗∗𝑃So,
𝑀 [1][2]=𝑃
[2][3]=𝑃 𝑃123∗∗𝑃𝑃234=5
=6∗∗462∗
=4 ∗∗2=48
6=120
7=84

1 2 3 4
1 0 120
2 -- 0 48
3 -- -- 0 84
4 -- -- -- 0

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 51

Matrix Chain Multiplication using Dynamic Programming
  Here dimensions are,  

 
step 3:

1 2 3 4
1 0 120 88
2 -- 0 48
3 -- -- 0 84
4 -- -- -- 0

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 52

Matrix Chain Multiplication using Dynamic Programming
  Here dimensions are,  

 
step 3:

1 2 3 4
1 0 120 88
2 -- 0 48 104
3 -- -- 0 84
4 -- -- -- 0

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 53

Matrix Chain Multiplication using Dynamic Programming
  Here dimensions are,  

 
step 3:

1 2 3 4
1 0 120 88 158
2 -- 0 48 104
3 -- -- 0 84
4 -- -- -- 0

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 54

Matrix Chain Multiplication using Dynamic Programming
 How to parenthesize matrices?  

A B C D

1 2 3 4
1 0 120 88 158
2 -- 0 48 104
3 -- -- 0 84
4 -- -- -- 0

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 55

Matrix Chain Multiplication using Dynamic Programming
 How to parenthesize matrices?  

A B C D

1 2 3 4
1 0 120 88 158
2 -- 0 48 104
3 -- -- 0 84
4 -- -- -- 0

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 56

Matrix Chain Multiplication using Dynamic Programming
  Here dimensions are,
 There would be matrices ),and

A B C D

158

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 57

Longest Common Subsequence
Introduction
  A subsequence is a sequence that appears in the same relative order, but not necessarily
contiguous.
 Given two sequences and we say that a sequence is a common subsequence of and if is a
subsequence of both and .
 E.g., if and then is a subsequence.
 Use dynamic programming technique to find the longest common subsequence (LCS).

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 59

LCS – Optimal Sub-structure
  We need to generate table
where length of string and length of string .
 
To generate table use following steps:
Step-1: Make and
Step-2: if then
Step-3: else ,

Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 60

LCS – Dynamic Programming Solution
 
else max(,

0 0 0 0 0 0 0 0
0 0 1 1 1 1 1 1
0 0 1 1 1 2 2 2
0 0 1 2 2 2 2 2
0 1 1 2 2 2 3 3
0 1 2 2 3 3 3 4
0 1 2 2 3 3 4 4
Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 61
LCS – Dynamic Programming Solution
 
else max(,

0 0 0 0 0 0 0 0
0 0 1 1 1 1 1 1
0 0 1 1 1 2 2 2
0 0 1 2 2 2 2 2
0 1 1 2 2 2 3 3
0 1 2 2 3 3 3 4
0 1 2 2 3 3 4 4
Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 62
LCS – Dynamic Programming Solution
 
else max(,

0 0 0 0 0 0 0 0
0 0 1 1 1 1 1 1
0 0 1 1 1 2 2 2
0 0 1 2 2 2 2 2
0 1 1 2 2 2 3 3
0 1 2 2 3 3 3 4
0 1 2 2 3 3 4 4
Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 63
LCS – Dynamic Programming Solution
 
and and LCS =

0 0 0 0 0 0 0 0
0 0 1 1 1 1 1 1
0 0 1 1 1 2 2 2
0 0 1 2 2 2 2 2
0 1 1 2 2 2 3 3
0 1 2 2 3 3 3 4
0 1 2 2 3 3 4 4
Dr. Gopi Sanghani #3150703 (ADA)  Unit 4 – Dynamic Programming 64
Thank You!