Coin change using dp

Presentation on the algorithm of Coinchange problems solution using Dynamic programming. Anyone interested in Dynamic Programming or problem-solving can be benefitted from this. This describes the problems with the greedy approach and the advantages of DP approach with examples.

1. Coin Change using DP

2. Introduction What is dp , The coin change problem, Greedy approach boundaries.

3. Lets Start with a quote!

4. What is DP? DYNAMIC PROGRAMMING: Dynamic programming is a method for solving a complex problem by 1. Breaking it down into a collection of simpler sub problems, 2. Solving each of those sub problems just once and 3. Storing their solutions . sub problem   memoization

5. COIN CHANGE PROBLEM. Given a value whole N, if we want to make change for N with coins, and we have infinite supply of each of S = { S1, S2, .. , Sm } valued coins, how many ways can we make the change? Find the Fewest Coins: Greedy approach: Given 30 cents, and coins {1, 5, 10, 25} Here is what a casher will do: always go with coins of highest value first.   Step: 1. Choose the coin with highest value 25 •  1 quarter 25 valued coin given. Step: 2. Now we have 5 cents left •  one 5 valued coin given.

6. Problem With Greedy approach. Another example: Coins Set = {1, 3, 4, 5 } 7 cents Greedy solution: –  3 coins: one 5 + two 1   Optimal solution: –  2 coins: one 3 + one 4 So we need different solution.

7. Dynamic Programming approach to solve coin change. The algorithm

8. Code. c/C++

9. Code. c/C++