Dynamic

Programming
Created by –
Ayan Memon (221120107029)
Outline
▪ Introduction to Dynamic Programming
▪ The Principle of Optimality
▪ Problem Solving using Dynamic Programming
▪ Calculating the Binomial Coefficient
▪ Making Change Problem
Introduction to Dynamic Programming
Introduction to Dynamic Programming
 Dynamic programming (usually referred to as DP) was first invented by Richard Bellman in
1957, as a method of solution to solve optimization problem. Later on technique was widely
used to solve many such problems.

4
Introduction to Dynamic Programming
 Dynamic programming is a technique that breaks the problems into
sub-problems, and saves the result for future purposes so that we
do not need to compute the result again.
 The subproblems are optimized to optimize the overall solution is
known as optimal substructure property (Principle of Optimality).
 The main use of dynamic programming is to solve optimization
problems.
 Here, optimization problems mean that when we are trying to find
out the minimum or the maximum solution of a problem.
 The dynamic programming guarantees to find the optimal solution
of a problem if the solution exists.
 The definition of dynamic programming says that it is a technique
for solving a complex problem by first breaking into a collection of
simpler subproblems, solving each subproblem just once, and then
storing their solutions to avoid repetitive computations.
5
How Does Dynamic Programming (DP) Work?
 Identify Subproblems: Divide the main problem into smaller, independent subproblems.
 Store Solutions: Solve each subproblem and store the solution in a table or array.
 Build Up Solutions: Use the stored solutions to build up the solution to the main problem.
 Avoid Redundancy: By storing solutions, DP ensures that each subproblem is solved only once,
reducing computation time.

6
Approaches of Dynamic Programming (DP)
 Dynamic programming can be achieved using two approaches:

1. Top-Down Approach (Memoization):

 In the top-down approach, also known as memoization, we keep the solution recursive and add
a memoization table to avoid repeated calls of same subproblems.
 Before making any recursive call, we first check if the memoization table already has solution for it.
 After the recursive call is over, we store the solution in the memoization table.

2. Bottom-Up Approach (Tabulation):

 In the bottom-up approach, also known as tabulation, we start with the smallest subproblems
and gradually build up to the final solution.
 We write an iterative solution (avoid recursion overhead) and build the solution in bottom-up manner.
 We use a dp table where we first fill the solution for base cases and then fill the remaining entries of the
table using recursive formula.
 We only use recursive formula on table entries and do not make recursive calls.
7
When to Use Dynamic Programming (DP)?
 Dynamic programming is an optimization technique used when solving problems that consists
of the following characteristics:

1. Optimal Substructure:
 Optimal substructure means that we combine the optimal results of subproblems to achieve
the optimal result of the bigger problem.
 Example: Consider the problem of finding the minimum cost path in a weighted graph from a source node to
a destination node.

2. Overlapping Subproblems:
 The same subproblems are solved repeatedly in different parts of the problem.
 Example: Consider the problem of computing the Fibonacci series. To compute the Fibonacci number at
index n, we need to compute the Fibonacci numbers at indices n-1 and n-2. This means that the subproblem
of computing the Fibonacci number at index n-1 is used twice in the solution to the larger problem of
computing the Fibonacci number at index n.
8
Example of Dynamic Programming (DP)
 Problem: Calculate the 5th Fibonacci number (𝐹(5))
 The Fibonacci sequence is: 0, 1, 1, 2, 3, 5, 8, 13, 21, …

 Recursive Formula: F(n) = F(n-1) + F(n-2)

 Base Case: F(0) = 0 & F(1) = 1

 𝐹(0) = 0,
 𝐹(1) = 1,
 𝐹(2) = 𝐹(1) + 𝐹(0) = 1,
 𝐹(3) = 𝐹(2) + 𝐹(1) = 2,
 𝐹(4) = 𝐹(3) + 𝐹(2) = 3,
 𝐹(5) = 𝐹(4) + 𝐹(3) = 5
9
Divide and Conquer Approach
 Process:
➢In this approach, the problem is broken into smaller subproblems recursively, but no
intermediate results are stored, so the same subproblems are recalculated multiple times.

 Example Calculation for F(5):

• To calculate F(5), you need F(4) and F(3).
• To calculate F(4), you again need F(3) and F(2).
• This keeps repeating, recalculating values like F(3) and F(2) multiple times.
 Subproblem Redundancy:
• F(3) is calculated twice.
• F(2) is calculated three times.
 Result:
 This approach leads to redundant calculations and is inefficient for larger inputs, as the same values are
recalculated multiple times.

10
Dynamic Programming Approach
 Recursive Formula: F(n) = F(n-1) + F(n-2) 1
 Base Case: F(0) = 0 & F(1) = 1
n 0 1 2 3 4 5
2
F(n) 0 1 1 2 3 5

 Subproblems: F(0), F(1), F(2), F(3), … 3

 Store Solutions: Create a table to store the
values of F(n) as they are calculated. 4
 Build Up Solutions: For F(n), look up F(n-1)
and F(n-2) in the table and add them.
5 6
 Avoid Redundancy: The table ensures that
each subproblem (e.g., F(2)) is solved only
once.
11
Dynamic Programming Approach
 Process:
➢Dynamic Programming solves subproblems once and stores their results, so they don’t need to
be recalculated. This saves time and avoids redundancy.

 Example Calculation for F(5):

• First, calculate and store F(0) = 0 and F(1) = 1.
• Then, use these stored values to calculate F(2) = 1, F(3) = 2, and F(4) = 3 in sequence.
• Finally, use the stored F(4) and F(3) to calculate F(5) = 5.
 No Redundancy:
• Each subproblem, like F(3) and F(2), is calculated only once and reused when needed.
 Result:
• Dynamic Programming avoids redundant calculations, making the process much faster, especially for larger
inputs.

12
Advantages & Disadvantages of Dynamic Programming
 Advantages:
 Optimal Solutions: Always provides the best solution for problems with overlapping subproblems and
optimal substructure.
 Reduces Redundancy: Saves time by reusing solutions to smaller subproblems.
 Faster than Recursion: Converts problems that would take too long with recursion into faster solutions.
 Wide Application: Can solve many optimization problems like Knapsack, LCS, etc.

 Disadvantages:
 Memory Usage: Needs extra memory to store solutions, which can be inefficient for large problems.
 Not for All Problems: Only works if the problem has overlapping subproblems and optimal substructure.
 Complex to Implement: Writing DP solutions can be tricky and require careful planning.
 Overkill for Small Problems: For small problems, simpler algorithms may be faster and easier.

13
The Principle of Optimality
The Principle of Optimality
 Definition: The solution to the overall problem can be constructed optimally using the
solutions to its subproblems.
 Let's understand the optimality through an example.

15
The Principle of Optimality
 Naïve Greedy Approach:
• Let F(x) be the minimum distance required to reach J from a node X.
2 + 4 + 3 + 4 = 13

Source Destinatio
n

16
The Principle of Optimality
 Optimal Substructure & Dynamic Programming Approach:
• Let F(x) be the minimum distance required to reach J from a node X.

F(J) = 0

F(I) = 4 1 F(H) = 3
F(H) = 3

F(J) = 0

Source Destination

F(I) = 4

17
Optimal Substructure & Dynamic Programming Approach:
F(E) = min { 1+F(H), 4+F(I) } F(F) = min { 6+F(H), 3+F(I) } F(G) = min { 3+F(H), 3+F(I) }
= min {4, 8} = min {9, 7} = min {6, 7}
=4 =7 =6

F(J) = 0

F(I) = 4 1 F(H) = 3
F(H) = 3

F(G) = 6
F(F) = 7 F(J) = 0
F(E) = 4
Source Destination

F(I) = 4

18
Optimal Substructure & Dynamic Programming Approach:
F(B) = min { 7+F(E), 4+F(F), 6+F(G) } F(C) = min{ 3+F(E), 2+F(F), 4+F(G)} F(D) = min{ 4+F(E), 1+F(F), 5+F(G)}
= min {11, 11, 12} = min{7, 9, 10} = min{8, 8, 11}
= 11 =7 =8

F(J) = 0

F(I) = 4 1 F(H) = 3
F(H) = 3

F(G) = 6
F(F) = 7 F(J) = 0
F(E) = 4
Source Destination
F(D) = 8
F(C) = 7
F(B) = 11
F(I) = 4

19
Optimal Substructure & Dynamic Programming Approach:
F(A) = min{ 2+F(B), 4+F(C), 3+F(D)}
= min{13, 11, 11}
= 11

F(J) = 0

F(I) = 4 1 F(H) = 3
F(H) = 3

F(G) = 6
F(F) = 7 F(J) = 0
F(E) = 4
Source Destination
F(D) = 8
F(C) = 7
F(B) = 11
F(I) = 4
F(A) = 11
20
Optimal Substructure & Dynamic Programming Approach:

3 + 1 + 3 + 4 = 11
F(J) = 0

F(I) = 4 1
F(H) = 3

F(G) = 6
F(F) = 7
F(E) = 4
Source Destination
F(D) = 8
F(C) = 7
F(B) = 11

F(A) = 11
21
Optimal Substructure & Dynamic Programming Approach:
 Therefore, we can say that the minimum distance from A to J is 11. Now, we have two ways to
reach from the vertex A to J through vertex D:
 The first way is from vertex A to vertex D, then D to F, F to I and then I to J.
 The second way is from vertex A to vertex D, then D to E, then E to H and then H to J.
 Here, we have built an optimal solution using the sub-solutions to the problem. Therefore, we
can say that the above problem has an optimal substructure.

22
Problem Solving using Dynamic
Programming –
Calculating the Binomial Coefficient
Binomial Coefficient
 A binomial coefficient C(n, k) also gives the number of ways, disregarding order, that k objects
can be chosen from among n objects more formally, the number of k-element subsets (or k-
combinations) of a n-element set.

 The Problem
➢Write a function that takes two parameters n and k and returns the value of Binomial
Coefficient C(n, k). For example, your function should return 6 for n = 4 and k = 2.

1) Optimal Substructure
 The value of C(n, k) can be recursively calculated using the following standard formula for
Binomial Coefficients. (where n > k > 0)
 C(n, k) = C(n-1, k-1) + C(n-1, k)
 C(n, 0) = C(n, n) = 1
24
Binomial Coefficient
2) Overlapping Subproblems
 It should be noted that the above function computes the same subproblems again and again.
For large values of n, there will be many common subproblems.
 Since the same subproblems are called again, this problem has the Overlapping Subproblems
property. So the Binomial Coefficient problem has both properties of a dynamic programming
problem. Like other typical Dynamic Programming(DP) problems, re-computations of the same
subproblems can be avoided by constructing a temporary 2D-array C[][].
C(4,2)

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

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

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

25
Binomial Coefficient
 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

𝑛 𝑛! 4 4!
𝐶 𝑛, 𝑘 = 𝑘
= 𝐶 4, 2 = 2
= =6
𝑘! 𝑛−𝑘 ! 2! 4−2 !

 Specifically, the binomial coefficient 𝐶(𝑛, 𝑘) counts the number of ways to form an unordered
collection of 𝑘 items chosen from a collection of 𝒏 distinct items.

26
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)

27
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)
28
Pascal’s Triangle
 There is a convenient way to remember the pattern for binomial coefficients. By arranging the
coefficients in a triangular pattern, you obtain the following array, which is called Pascal’s
Triangle. This triangle is named after the famous French mathematician Blaise Pascal (1623–
1662).

29
Problem Solving using Dynamic
Programming –
Making Change Problem
Making Change Problem
 Example: You have to give someone 88.85 ₹. You have to give less coins as much as possible.

31
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 c[i][0] = 0 𝑓𝑜𝑟 0 < 𝑖 ≤ 𝑛
Repeat step-2 to step-4 for the remaining matrix values
Optimal
Step-2: If 𝑖 = 1 then 𝑐[𝑖][𝑗] = 1 + 𝑐[1][𝑗 − 𝑑1 ] Sub-structure

Step-3: If 𝑗 < 𝑑𝑖 then 𝑐[𝑖][𝑗] = 𝑐[𝑖 − 1][𝑗]

Step-4: Otherwise 𝑐[𝑖][𝑗] = 𝑚𝑖𝑛(𝑐[𝑖 − 1][𝑗], 1 + 𝑐[𝑖][𝑗 − 𝑑𝑖 ])

32
Make Change Problem – Dynamic Programming Solution
 Denominations: 𝑑1 = 1, 𝑑2 = 4, 𝑑3 = 6. Make a change of Rs. 8.

Step-1: Make 𝑐[𝑖][0] = 0 𝑓𝑜𝑟 0 < 𝑖 ≤ 𝑛

Step-2: If 𝑖 = 1 then 𝑐[𝑖][𝑗] = 1 + 𝑐[1][𝑗 − 𝑑1 ], here 𝑑1 = 1
Step-3: If 𝑗 < 𝑑𝑖 then 𝑐[𝑖][𝑗] = 𝑐[𝑖 − 1][𝑗]
Step-4: Otherwise 𝑐[𝑖][𝑗] = 𝑚𝑖𝑛(𝑐 𝑖 − 1 𝑗 , 1 + 𝑐 𝑖 𝑗 − 𝑑𝑖 )

𝑗 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][4], 1 + 𝑐[2][1])
𝑚𝑖𝑛(𝑐[1][5], 𝑐[2][0]) = 𝑚𝑖𝑛(5,1
min(4,1 + 0)
1) = min(4,1)
𝑚𝑖𝑛(5,2)
= 21
=
33
Make Change Problem – Dynamic Programming Solution
 Denominations: 𝑑1 = 1, 𝑑2 = 4, 𝑑3 = 6. Make a change of Rs. 8.

Step-1: Make 𝑐[𝑖][0] = 0 𝑓𝑜𝑟 0 < 𝑖 ≤ 𝑛

Step-2: If 𝑖 = 1 then 𝑐[𝑖][𝑗] = 1 + 𝑐[1][𝑗 − 𝑑1 ], here 𝑑1 = 1
Step-3: If 𝑗 < 𝑑𝑖 then 𝑐[𝑖][𝑗] = 𝑐[𝑖 − 1][𝑗]
Step-4: Otherwise 𝑐[𝑖][𝑗] = 𝑚𝑖𝑛(𝑐 𝑖 − 1 𝑗 , 1 + 𝑐 𝑖 𝑗 − 𝑑𝑖 )

𝑗 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

34
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] 𝑐[𝑖][𝑗] = 𝑚𝑖𝑛(𝑐[𝑖 − 1][𝑗], 𝟏 + 𝒄[𝒊][𝒋 − 𝒅𝒊 ])
▪ 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
35
Questions asked about this topic in GTU Exams
1. What is principal of optimality? Explain its use in Dynamic Programming Method. W20 3M
2. What is Principle of Optimality? Explain its use in Dynamic Programming Method. S21 4M
3. What is Principle of Optimality? Explain its use in Dynamic Programming Method. W21 3M
4. What is Principle of Optimality? Explain its use in Dynamic Programming Method. S22 3M
5. What is Principle of Optimality? Explain its use in Dynamic Programming Method. S24 3M
6. Define principal of optimality. Explain its use in Dynamic Programming Method. W24 4M
7. Explain principle of optimality with suitable example. S23 3M
8. Explain Optimal Substructure and Overlapping sub problems with suitable example. S21 3M
9. Explain Over-lapping Sub-problem with respect to dynamic programming. W22 3M
10. When can we say that a problem exhibits the property of Optimal Sub-structure? W22 3M
11. Explain advantages and disadvantages of dynamic programming. S23 4M
12. Enlist the advantages and disadvantages of dynamic programming. W24 4M
36
Questions asked about this topic in GTU Exams
13. Explain Binomial Coefficient algorithm using dynamic programming. W21 4M
14. Explain Binomial Coefficient algorithm using dynamic programming. S24 4M
15. Find out the NCR (5/3) Using Dynamic Method. W23 3M
16. Given the denominations: d1=1, d2=4, d3=6. Calculate for making change of Rs. 8 using
dynamic programming. S23 7M
17. Given coins of denominations 2, 3 and 4 with amount to be pay is 5. Find optimal no. of coins
and sequence of coins used to pay given amount using dynamic method. W23 4M

37
References taken from
1. ChatGPT
2. GeeksforGeeks
3. Javatpoint
4. ADA Technical
5. Darshan Study Materials
6. Wikipedia

38
Thank You!