Minimum number of coins | Coin Change Problem using dynamic programming

In this video, we will find minimum number of coins that make a given sum using Dynamic programming.
Dynamic programming coin change problems are quite popular among computer science students.

The more popular is the coin change problem in which we need to find the number of ways that make a given sum when coins of few denominations are given.

The problem solved in this video using dynamic programming is a variation of the one described above.

So,here's the description of the problem -

We're given 3 coins. The coin denominations are 1,3 and 5.
The sum given is 11

We need to find the minimum number of coins to make change of 11.

Following are the possibilities that will help you understand this DP problem better.

1. 11 coins of 1 will give you 11
2. 3 coins of 3 and 2 coins of 1 will give you 11
3. 2 coins of coin denominations 5 and 1 coin of denomination 1 will also give you 11.

Out of these 3, the best answer to this minimum no of coins problem comes out as 3 because it is the least of all.

Likewise, there can be many possibilities and we will find the most optimized one in our solution using one of the best computer programming techniques which is DP.

This problem finds its application where a cashier job is to save the coins of lower denominations and has to use his skills of finding minimum number of coins that add up to a given amount of many which needs to be paid to the customer.

[Daily_Dose_Of_Life]

i not understand how you formed the 2nd table, can you explain it

[maralazizi]

Thank you so much for the great explanation!! It helped me to understand DP a lot!!

[akhilsraj]

681st subscriber lucky to find you !!!

[anuruddhasingh]

It's like a really amazing style of teaching

[hemanthpidugu]

superb explanation bro... it would be helpful if you code for the same problem at the end of the video