The Change Making Problem - Fewest Coins To Make Change Dynamic Programming
HTML-код
- Опубликовано: 12 янв 2019
- Code & Problem Statement @ backtobackswe.com/platform/co...
Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
Examples:
1
Input:: coins = [1, 2, 5], amount = 11
Output 3
2
Input: coins = [2], amount = 3
Output: -1
Approach 1 (Brute Force)
We can generate all sets of coin frequencies that end up summing to the total amount given the coins that we granted and then take the sequence with the least coins in it.
This is not only harder to implement, but it entails an automatic exponential amount of work to compute all the sets of coin frequencies to only take the best answer (the set with the least coins) from.
Approach 2 (Top Down Dynamic Programming)
Example:
Input:: coins = [1, 2, 5], amount = 11
Output 3
The answer to the subproblem for amount 11 is the same thing as the MINIMUM of the answers to the sub problems with each currency deduced from the original sub problem (11) PLUS ONE since we are acting as if each coin we subtract from 11 is the last coin used to make change.
Not all paths will yield an answer, some will yield an optimal answer.
Complexities (Top Down)
A is the amount to make change for.
n is the total denominations avaliable to make change with.
Time: O( A * n )
For each amount we will approximately be doing n work in trying to deduct each denomination from the current sub problem
Our recursive tree will at maximum have a depth of S (worst case if each call deducts 1 at each call).
Space: O( A )
We answer and store a total of A subproblems in our dynamic programming table to get to our globally optimum answer.
Approach 3 (Bottom Up Dynamic Programming)
Example:
Input:: coins = [1, 2, 5], amount = 11
Output 3
We can also create a dynamic programming table going from the bottom up to the amount we want an answer for.
Complexities (Bottom Up)
A is the amount to make change for.
n is the total denominations avaliable to make change with.
Time: O( A * n )
For each amount we will potentially try each of the denominations (there are n of them).
Space: O( A )
We answer and store a total of A subproblems in our dynamic programming table to get to our globally optimum answer.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech 
Наука
Table of Contents:
Me Talking (Uninteresting) 0:00 - 0:19
The Problem Introduction 0:19 - 1:48
Top Down Recursion Walkthrough 1:48 - 7:43
Bottom Up Iterative Walkthrough 7:43 - 20:18
Time Complexity 20:18 - 21:42
Space Complexity 21:42 - 22:19
Wrap Up 22:19 - 22:52
The code for this problem is in the description.
tushar roy part?
@@nguyentranconghuy6965 yeah
Bro I don't think your approach works for input coin = [2] and amount 3 in your bottom up approach. 2 is less than 3 so dp[3-2]=dp[1] which is 0 plus 1 is 1. which is false.
Won't greedy itself give a solution for this problem? Why use DP here?
@@anandartwork I was thinking about this as well
The Tushar Roy clips in between 😂😂
yeah, I'm geekin'
@@BackToBackSWE I can't watch Tushar anymore.... You are actually enjoyable to watch
this guy is literally the best at explaining algorithms on all of youtube lmao. no other vids compare haha
great to hear.
truth
@@bryanlozano8905 I definitely love watching them. The enthusiasm is catching!
NeetCode, Abdul Bari and Tech Dose are outstanding at explaining algorithms as well
Wow: U did the calculations till the end, instead of saying "and so on". +1
Good explanation. ;)
thx
If he wouldn't have done that, I think I wouldn't have understood it :D
@@RicardoBuquet nice
That does make it clearer, Kudos!
+1. this is remind me of studying mathematical proof, it skip some steps by saying like "it's obvious", but I did not get it.
Dude this is legit the best video i have found by far on DP. Please keep making these on hard-to-grasp CS concepts (maybe do rabin-karp/other string matching algos next lol). The other youtubers dont explain at the level you do, they make too many assumptions about what is obvious, or their accent makes the video hard-to-comprehend
YES. YES. YES. YOU SEE THE VISION NOW?? haha.
Yeah this is exactly how I felt when my head was in the dirt learning dp.
I was always pissed off.
Like...I need not say more. What you said is why I grind out these videos.
That is the vision. A channel of hundreds of videos with CRYSTAL clear explanations.
A lofty goal, but better to shoot for the moon and to land amongst the....you know the quote :)
Edit: Future Ben is reading this comment haha (version 9/2/2019 me), I made this comment when I was crazy and no one watched the channel. Precontext.
Back To Back SWE love your videos! Keep up with your good work!
Just reread this comment and I sound crazy lol
@@BackToBackSWE but we love you
@@wizziesfan wassup
12:24 "1+1 =2" I felt that.
what lol
perfect explanation dude, the Tushar part was gold lmao
I know, I was getting silly :)
Dude, this is the best explanation for Dynamic Programming on RUclips.
Please keep going!
nice, thx
"We have tried all our coins and the winner is 5"
"I have tried all other videos and the winner is U"...
best explanation bro.. thanks alottttt....
thx
I have watched a lot of videos on youtube trying to find a good explanation for this, but none comes close to this video. For someone just learning to program, I will say this guy is an excellent teacher.
thanks for the kind comment.
This is the most clear explanation that i have ever heard!
thanks a lot.
sure
I have no words to thank you. You are really awesome!! This question I am trying to understand from 3 days. But you had cleared in just 20 mins.
Teaching is an art and you are a great artist.
Thanks for being so patient explaining how the values are put in every cell!
sure
God bless you mate. I was trying to understand the solution from the leetcode explanation for hours and from the guy in your video at the beginning as well. You have a talent to teach complex things in understandable way. Keep up the good work
haha thx...mate
I really appreciate his style of explanation. He repeats himself, a lot. Probably it is because of this we are able to grasp the concepts. He is really filling the gaps left out by other creators.
Hey there man, I want to thank you for the effort and time you spent making this pure information brilliance available for free. Best of luck and wishes in your future endeavors. You are helping us out a lot :)
Man, I love your energy and you are making this make so much sense! I hope you are doing well.
yes and thx
And it finally clicked in my brain, THANK YOU! Subscribed!
THAT IS AWESOME. This is why I do this. I hope you have more moments like that.
Really well explained ! Thank you so much I've been trying to wrap my mind around my lecturer's explanation but your way of explaining is way clearer!
ye
Dude this is legit the best video i have found by far on DP.
Best explanation ever. I have watched many but this is great.
thx
Amazing effort!! I wasted my whole day in understanding this. Wish I could see that at first!! Amazing explanation.
nice
This is THE BEST explanation for dynamic programming I have ever seen. I appreciate how you focused on the intuition behind the technique and solved the problem to its completion rather than just saying "And so on..."
thanks
This video is the best tutorial I've seen online, thank you so much for your clear explanation, you're an amazing teacher!
thx
Thank you for tracing the entire solution when you were doing the bottom up approach. It made it much more understandable.
sure
Very well explained. Great energy and amazing presentation skills. Keep up the good work Benyam. You might have lost first 3 interviews, but, your videos might have helped others crack their interviews in some way. Be proud of it. Thanks for your effort in making these videos.
sure
This is totally the best Dynamic Programming video I've ever seen. Dude, you rock!
no u
This is the most clear explanation for this problem! Now it's clear for me why all those operations and how they work together.
God bless this dude! OMG!!!! I feel I am gonna kill my interview with Microsoft!
lol, good luck!!
Tushar Roy wants to know your location!!!🤣🤣
hahahahahahahahahahah, best comment ever!
Lmao I’m geeked
Whats the story behind this? Just curious!
@@BackToBackSWE only an Indian can give such comments. 😆
The way you explained was amazing, period. I tried to watch to other videos for the explanation, but the idea clicked easily with your approach! also kudos to the entire walk through till the last iteration!
Thanks! keep posting such awesome stuff!
Thanks and thanks and ok
Hands down best video on the subject. Thank you
Dude I love u xD , My exam is in 2 days and i have been trying to solve this question for hours and I almost got depressed cuz i couldn't solve it. u made it clear and simple and easy to understand , couldn't ask for a better explanation. Honestly I wish my college had lecturers like u, I swear im not kidding . thank u so much for this video , Subbed :D
It is nothing. Thanks for watching.
Hey!!
which course are u studing now?
@@BadBoy-hm3vk hey
@@BackToBackSWE hey!! can you pls tell me that what i want to do after my bca.i m just confused about what to do either go for a 2 year work experience or 2 year masters and i also have a dream to be good in algorithms and machine learning.does doing mca is enough or i need to do go for higher studies?.
@@BadBoy-hm3vk Honestly not sure. I'm a 2nd year in college as of the writing of this comment. Ask r/cscareerquestions. They have good advice.
I'm clapping with all my might!
Great Job!
Side note: I was caught on that Face swap.. funny as hell! ahahaha XD
haha and thanks and sorry - old video, had few watchers
Thank you so much, you're the best, you made it so easy to understand while many others use unnecessarily confusing denominations. Now everything makes sense!
I have searched a lot of tutorials about the change making problem and I can say that your VDO explanation is the best.
ay, cool
You are so underrated:")
haha thx
Someone please buy this gentleman a beer because God knows he deserves it. Thank you!
I am only 20...oh wait no im 21 now lol
This is the best video on this problem. Thank you so much!
Easily the best DP explanation on youtube. Bless you brother
Follow-up: Return the actual coins.
Hahaha. No no no.
Follow-up: Solve Leetcode 999..."The Protein Folding Problem"
Im lost with +1
*(
Edited: I got it!!
WOW this channel is amazing : )
Comeback of the century
Juan2003gtr
Imagine the +1 as an action
The Coins[1,2,5]
Say you need to give someone change for 2 cents. You have 1 coins, 2 coins and 5 coins ( you trying to find the least amounts of ways to give change)
Only way you can give change for 2 cents is 1 coins and 2 coins.
(Remember an action is like +1 )
1 coin + 1 coin = 2 cents
1 coin (action) + 1 coin(action) = 2 cents
Add the actions: 1 action + 1 action = 2 actions. It took 2 actions to get 2 cents for using 1 coins.
2 coin = 2 cents
2 coin(action) = 2 cents
Add the actions: +1 action = 1 action ( same as 0+1 = 1) It took only 1 action to get 2 cents, the 2 coin.
We know now that the 2 coin took less actions to get 2 cents. But how does the program language know that in code form?
Subtract each coin from the number 2, what ever number it is, it should already know the least amount to give change for that number you subtract to.
The 1 coin:
2 - 1 coin = 1 (the number )
To get change for number 1 the least, is the 1 coin. So the number 1 already has an action the 1 coin(+1).
Add another 1 coin to get the number 2, which is other action (+1)
(+1) + (+1) = 2 actions (Same as 1 coin + 1 coin = 2 cents)
So The 1 coin took 2 (actions) to get 2 cents
The 2 coin:
2 - 2 coin = 0 (the number)
To get 0 it takes no action to get zero, so it’s zero. Add the 2 coin, which is 1 action (+1)
0 + 1 = 1 action ( same as 2 coin = 2 cents)
So the 2 coin is 1 (action) to get 2 cents
Now compare the actions for 1 coin and 2 coin.
Which is less 1 or 2?
1 (the 2 coin)
Hope that helps😀
Love your video! The though process is nicely described.
This was hands down the best explanation I’ve seen on this problem
How can you be this good at explaining to students when you are a student yourself? I need to know your path Sir! Can't be the regular 20 year old college student
cuz im a student
lmao at the Tushar clips!
hehe
You make code visualizes into our head like a movie.Its like we are watching some coding based movie which is so exciting and interesting that we just go into recursion and get the best.Thanks a lot for such a deep explanation.Keep posting more videos these are quite useful.
ha nice
Thank you from the bottom of my heart, Your talking style and teaching are really awesome and energetic.
Thanks - means alot
what c++ is to c , is what this channel is to Tushar Roy :). P.S : Tushar Roy is a great channel
fascinating observation
why does he talk like he's teaching 5 year olds lmao good content tho
I'm in a library so had to talk quietly. This was early when I didn't have a microphone and like 2 people watched lol
Back To Back SWE 😂😂 all love dude. Ur content is actually fire
you are great bro, the thing which I am not getting from past 5 days has been deliberately and easily explained by you in just 23 minutes,god is seeing all your good work, be happy and be successful in your career.
nice
This channel is a life savior!
Many thanks and keep up with the good work :D
sure
the 16 dislikes are from tuschar roy. 😂😂
haha chill
@@BackToBackSWE now Tushar has urged his subscribers to do 5 dislikes more
When I did this problem, I imagined it as a bfs graph problem, where I have to traverse from the requested amount to 0. Each node has a neighbor that is itself - ci. as long as that value is >= 0. You can then solve this with simple BFS. Once you find 0, you have the shortest path. I see in LC, this is faster than DP. I don't understand why no one considers this method. The visited set prevents you from doing redundant work. I think BFS is the way to go... forget DP people!
thanks for sharing - im replying to comments super fast so can't proof-read the approach presented
I think the problem is that the memory grows too fast at every level
Keep up the good work.. No words to this awesome work!! We need more teachers like u 🙏
In my algorithms class , and this saved my life. Thank you for this . DP isn't as scary as it was made to seem !
Wait are you really expected to solve something like this in a interview without having heard of the solution before? i can't imagine a lot of people would come with an algorithm like that in their mind
It is a famous problem
@@BackToBackSWE i was new to dynamic programming and slowly I understand thsoe problems 😍
Man, your explanation is so good! Thanks for making this video!
Fantastic, dude. You made me understand the code even without writing a single line. Thank you.
Best explanation of this problem, thank you!
This is the clearest explanation of the concept by far. Great work!
OMG this is the best video I've ever watched for dp!! So clear and detailed!! Thank you bro!!
You have the talent to mentor complex things so easefully that nobody does it better.
thanks
Awesome explanation! Thank you so much!
Thank you for the video man!!! This is the best channel for learning algo concepts and basics!
I was having a hard time to understand! Now I get it. Great explanation!
nice
Thank you for this explanation. I needed this for part of an actual production system.
sure
Great explanation!
Making this in-depth videos will help people understand easier the concepts in no time.
Thanks! This is one of the problem I cover on the site I'm making: twitter.com/thebigoguide
Thanks a lot for this lucid explanation, i was struggling to understand this since along time and now its much more clear
sure
Thank you sir! Your explanations are incredible!
this was amazingly helpful, thank you!
you're amazing! best explanation I've found.
Thx for the help! Big hug from Portugal!
Writing code becomes easier when I can understand the approach...really appreciate your explanation...Thanks a ton!!!
nice sure
Thank you so much!
Great explanation!!
Concise and informative ❤❤
Bro you explain very well! Thanks a lot!
Bro, this is the best explanation I have even seen..thank you for walking through all steps in the bottom-top algorithm..now I do understand how this works..
nice. happy you are enlightened haha
This is great, best on RUclips for Dynamic programming. thanks!
thx
best explanation I found for this problem. Great job!
thanks
Thank you so much! You've helped me understand so many of these problems
nice
You're the best one explaining DP clearly :)
After watching video after video, I was able to solve this problem without looking at the code based only on your description. Well done, thank you
Best explanation so far! Never understood this problem this clear.
nice
Hats off to you for explaining in a very simplistic manner.
thanks
Wonderful video and very verbose explanations. I can't believe you actually worked through each of the cases for the bottom-up approach. Most people would've done the first few and said "and so on" and filled up the remainder of the table. Thank you for the video.
The visual helps so much in understanding the problem. Thank you so much!!
sure
finally a good explanation , great job
Blows my mind every time I watch your videos.
nice.
Subscribed. This is better than any teaching I've had from any of the video lectures at university. Love your exhaustive approach. The repetition really helps get the idea through!
Thank you, glad you liked it 😀
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends 😀
As you said in the video, understanding the tree did help. Helped me understand what I was doing wrong and got me straight to the accepted solution.
you helped me understand dynamic programming. thank you
My whole concept of DP just became clear. Thanks a lot :)
nice
Good job, man. I had a friend struggling with this and I couldn’t explain worth shit. I looked for vids and yours was the best I found.
my god. thank you for actually going through the whole thing. i didn't actually grasp the bottom up approach until you hit 3 or 4. most teachers would've stopped at 2 and said "you get the pattern".
great teacher.
I was confused at first when looking at the array but going through the problem helped a lot. Thanks for the great explanation.
I was struggling with this until you showed me "The CHANGE Making Problem". U are a life changer. Thanks
sure
One of the best explanations on the topic of dp. Bravo!
thx
Thank you my dear friend for such a lucid, clear and crisp explanation of DP , The way you taught to identify the hidden sub-problem which is the crux of DP , I appreciate your hard work. My sincere thanks to you!!!
Sure
Great Explanation! This is the best channel!!
Thank you. We have a long way to go. I want everyone to get offers.
Thanks for this awesome explanation, the bottom up step by step explanation worth gold!
thanks