As mentioned in the end of the video, it's much more intuitive to go backwards (i.e. start from the values that first would get memoized). I found a solution that can be easily understood and also has similar runtime (measured the runtime in us with large values and on average it's between 10-20% slower, but I believe it's a good trade-off for better readability): 1. The amount has to be greater than zero and the coin index must be valid (note that we reverse the coins array and start with the lowest denomination). 2. Check for the cached ways as shown in the video via a hashmap. 3. Iterate from the lowest denomination (i.e. 0) until the current index (i.e. coins.length for the first stack frame). 4. If the current coin is 1, then increment the ways and continue the looping without going to the next step. (there is only one way to split with 1s) 5. If the current coin is a divisor for the current amount, then increment ways and go to the next step. (i.e. the current amount is splittable also using only one type of coin) 6. Decrement the current amount with the value of the current coin and loop until the remaining amount is negative. 7. In this inner loop you must call the function recursively with the remaining amount and the current coin index (the one from the outer loop) such that you will get the ways to split the remaining amount with the lesser denominations (i.e. all denominations up until the current index).
How do you come up with elegant solutions like this off the top of your head? I understand why it works when stepping through it but... it looks like you begin with thinking about base-conditions for stopping the recursion loop and returning the smallest possible answer (you didn't here but you usually do).. it's just difficult to extrapolate and break-down how you come up with this solution because it seems like a chicken/egg scenario where the pieces all depend on eachother and you need to know them all at once.. hopefully it will come overtime and practice..
Hi... i have about 2 yrs of experience writing code and still can't understand this. I'm in freshmen year though but i have been doing this since the last 2 years. And trust me... these types of challenges bring back some severe trauma in me. Edit: and after watching this atleast 20 times, i still don't truly get it.
Ultimate Sin what i like to do though.. is give my brain a paradigm to initially approach the problem and then map the solution that i created to the original one. Requires a hell lot of time but helpful for beginners. Sadly, though it all boils down to a good iq but we all need to learn to be optimistic about the worst of things if we want to succeed.
seriously looks so easy the way she came up with the solution, i really didnt understand had to watch multiple youtubers explaining it and still trying to understand it honestly.
try these problem on project euler the idea is that first pre-compute smaller coin changes using DP say 1,5 if u hav 1,5,10,15,20,25 .Then if u already computed these ways when u break down money into larger denominations,it comes as arr[i]=arr[i]+arr[i-coins[j]],where i->val of rupees and j ->iterator
Thanks @5hari I had the same question. It also looks to me like we're going to keep calling makeChange with remaining == money since we're not incrementing amountWithCoin until after the recursive calls, meaning it amountWithCOin remains == 0? I keep getting ways = 0 when I run the code. Please help
@@wtogbey Even I was thinking the same, till I noticed the ordering of lines 23 and 24. If we see carefully the amountOfCoint is incremented only after calculating the ways for the that coin index.
@@geraldatanga But, what are M and N? Your answer seems too easy to say, without backing it up. Making change for $2.05 when having P, N, D, Q, HD is pretty lengthy. Can you please clarify? Thanks!
@@WafflerMark hey! Im also struggling through dp but when he says time complexity is O(m*n) that means while solving dp problem you need to fill a table for memoization with table having dimension m*n m-rows n-cols and diff values of m might represent money u have (suppose u passing. Arr{1,2,3} 1,2,3 are coin denominations you have. And col will range from 0 to 4 (suppose 4is the total sum u want feom the denominations). This is the reason tc is O(m*n). Hopefully u understood it better than before:)
That is called "memoization". It is the practice of sacrificing memory to store values for the sake of not having to compute a value again. Say you have some complex function foo that returns an int that takes five minutes to run. If your algorithm uses foo a lot, rather than computing foo(4) every time, you can just store foo(4) after running it once and then you can just look the value up the next time you need it.
@@abishekkachroo938 The index into the hashmap is the parameter to the expensive operation, while the value stored at the index is the result of the expensive operation.
O(M * N) time, and O(N) space. N is the money amount, and M is the number of coins. Basically, you need a for loop to iterate over each coin, and for each coin, you need another for loop that iterates over the amount of money that is given. This second for loop is to keep constructing the memoization data structure(she used a hashmap, but you can also use an array). In her case, instead of using 2 for loops, she used a while loop, and recursion.
Would have been nice to see an example where hashmap with key ONLY money (and not money + "-" + index) fails. Actually, would have been incredibly helpful. Also, you can do "String key = money + "-" + couns[index]" since the index doesn't really matter (the coin at hand does, which is inferred by index).
Could you speak a bit slower please? In all those tutorial videos I have watched, this was the first time I opened the subtitles :) Thank you for the video by the way :)
Dumb question: number of ways to make change for zero cents is One. Why is that? If I had no money, then how can I make change for it. Just trying to understand the intuition here.
Speaking in terms in the real world, that really sounds a pretty bizarre situation: someone suddenly asking you a change, for 0 money. But if we think in a more programming way it makes more sense: imagine receiving an input of 0, we would return an empty set. The empty set is a valid return, no money were given, so we return a set containing no coins, the transaction is valid because nobody were given more money than the other part, so that counts as a way. But now think in a situation were we are given an amount where all the coins we have are greater than that amount. We can't return an empty set. That means we are returning 0 money, but we received an amount greater than 0, if we return an empty set we would be stealing money from the other part, so there is no way to give a change, so the number of ways is 0 in that last situation.
Anyone tried this solution out and worked ? I'm implementing this in Python and it's just doesn't compute the ways the way it's supposed to, and it's been throwing some errors
The question on HackerRank states that coin is a value between 1 and 50. So basically it say's it can be 49 or 13. I hate when one time you supposed to make assumptions to real world and other time have tests failed and find out that "you should have been reading more carefully".
I had this same question. The only way to make 0 money is not use any coins. That in itself is a valid way to give 0 money. Thats one way to think of it. Another way to think of it is that you are passing the remainder or your initial amount minus some coin value to the next function. Well, when you pass 0 to the next function, in the case of 1 - 1 (a penny - a penny) you have found a valid combo and need to return 1 since all the coins you have used so far "fits"
Please do not assume that everyone using this lives in the United States of America. Please try to make your videos understandable to the global audience, because currently it is just gibberish with quarters, nickels, dimes and what not.
Seriously, what is with this channel and recursion! Recursion is generally discouraged in code bases bc it adds unnecessary complexity. Also, it is slower than non-recursive code by some x. It's generally just a way to pretend to be "extra" smart.
Often, recursion is far simpler than iteration. And it isn't slower if it is tail-recursive (that is, the compiler will translate it to iteration anyway).
For people international
penny = 1
nickel = 5
dime = 10
quarter = 25
half dollar .= 50
dollar = 100
Thank you! :-)
thank you buddy
thank you so much
I wish she didn't got through the solutions so quick and actually explained each line in detail...
As mentioned in the end of the video, it's much more intuitive to go backwards (i.e. start from the values that first would get memoized). I found a solution that can be easily understood and also has similar runtime (measured the runtime in us with large values and on average it's between 10-20% slower, but I believe it's a good trade-off for better readability):
1. The amount has to be greater than zero and the coin index must be valid (note that we reverse the coins array and start with the lowest denomination).
2. Check for the cached ways as shown in the video via a hashmap.
3. Iterate from the lowest denomination (i.e. 0) until the current index (i.e. coins.length for the first stack frame).
4. If the current coin is 1, then increment the ways and continue the looping without going to the next step. (there is only one way to split with 1s)
5. If the current coin is a divisor for the current amount, then increment ways and go to the next step. (i.e. the current amount is splittable also using only one type of coin)
6. Decrement the current amount with the value of the current coin and loop until the remaining amount is negative.
7. In this inner loop you must call the function recursively with the remaining amount and the current coin index (the one from the outer loop) such that you will get the ways to split the remaining amount with the lesser denominations (i.e. all denominations up until the current index).
How do you come up with elegant solutions like this off the top of your head? I understand why it works when stepping through it but... it looks like you begin with thinking about base-conditions for stopping the recursion loop and returning the smallest possible answer (you didn't here but you usually do).. it's just difficult to extrapolate and break-down how you come up with this solution because it seems like a chicken/egg scenario where the pieces all depend on eachother and you need to know them all at once.. hopefully it will come overtime and practice..
Everyone memorizes. It's not obvious. Don't worry. These are all well known solutions
Hi... i have about 2 yrs of experience writing code and still can't understand this. I'm in freshmen year though but i have been doing this since the last 2 years.
And trust me... these types of challenges bring back some severe trauma in me.
Edit: and after watching this atleast 20 times, i still don't truly get it.
Ultimate Sin what i like to do though.. is give my brain a paradigm to initially approach the problem and then map the solution that i created to the original one.
Requires a hell lot of time but helpful for beginners. Sadly, though it all boils down to a good iq but we all need to learn to be optimistic about the worst of things if we want to succeed.
seriously looks so easy the way she came up with the solution, i really didnt understand had to watch multiple youtubers explaining it and still trying to understand it honestly.
try these problem on project euler the idea is that first pre-compute smaller coin changes using DP say 1,5 if u hav 1,5,10,15,20,25 .Then if u already computed these ways when u break down money into larger denominations,it comes as arr[i]=arr[i]+arr[i-coins[j]],where i->val of rupees and j ->iterator
good video, change the font next time and perhaps introduce the coins to those that are international so we can better understand the video.
i think your code do not consider the same index again , if not , how it will ??? explain
Same index coin is considered by the while loop. Recursion handles the current amount in the while loop with the rest of the coins.
Thanks @5hari I had the same question. It also looks to me like we're going to keep calling makeChange with remaining == money since we're not incrementing amountWithCoin until after the recursive calls, meaning it amountWithCOin remains == 0? I keep getting ways = 0 when I run the code. Please help
@@wtogbey Even I was thinking the same, till I noticed the ordering of lines 23 and 24. If we see carefully the amountOfCoint is incremented only after calculating the ways for the that coin index.
What is the Big O notation of the non-DP and DP solutions?
Space O(N) and Time : O(M * N )
@@geraldatanga But, what are M and N? Your answer seems too easy to say, without backing it up. Making change for $2.05 when having P, N, D, Q, HD is pretty lengthy. Can you please clarify? Thanks!
@@WafflerMark hey! Im also struggling through dp but when he says time complexity is O(m*n) that means while solving dp problem you need to fill a table for memoization with table having dimension m*n m-rows n-cols and diff values of m might represent money u have (suppose u passing. Arr{1,2,3} 1,2,3 are coin denominations you have. And col will range from 0 to 4 (suppose 4is the total sum u want feom the denominations). This is the reason tc is O(m*n). Hopefully u understood it better than before:)
O(M * N) time, and O(N) space. N is the money amount, and M is the number of coins.
what is quarter at 0:42??
Quarter is $.25!
I am still confused as to why we need to store the money and index into a hashmap
That is called "memoization". It is the practice of sacrificing memory to store values for the sake of not having to compute a value again. Say you have some complex function foo that returns an int that takes five minutes to run. If your algorithm uses foo a lot, rather than computing foo(4) every time, you can just store foo(4) after running it once and then you can just look the value up the next time you need it.
@@ChristianRoyUtah Can you please whats the use of index here and what value is placed in this variable.
@@abishekkachroo938 The index into the hashmap is the parameter to the expensive operation, while the value stored at the index is the result of the expensive operation.
I get the recursion part but i don't get the memoize stuff like how these map (store) works and why the value of map is a increment variable :(
Hi, check min 1:59
What is the time complexity of this solution?
I have no idea how to guess it.
O(M * N) time, and O(N) space. N is the money amount, and M is the number of coins. Basically, you need a for loop to iterate over each coin, and for each coin, you need another for loop that iterates over the amount of money that is given. This second for loop is to keep constructing the memoization data structure(she used a hashmap, but you can also use an array). In her case, instead of using 2 for loops, she used a while loop, and recursion.
cant we do this iteratively with simple array storing previous results?
Yes
It would have been better if you could talk about the time and space complexity of the solution.
Did I just hear "make out" !? 0:37
is it not posible to solve it without recursion ?
Great video!
Would have been nice to see an example where hashmap with key ONLY money (and not money + "-" + index) fails.
Actually, would have been incredibly helpful.
Also, you can do "String key = money + "-" + couns[index]" since the index doesn't really matter (the coin at hand does, which is inferred by index).
Could you speak a bit slower please? In all those tutorial videos I have watched, this was the first time I opened the subtitles :)
Thank you for the video by the way :)
I played it as 0.75x and she uses bad variable names. coins, money, amount, its confusing after few seconds at 4:10
I guess it is her character, what to do :)
Can anyone tell me about its recurrence relation ???
Hajra Naqvi well. It gives the recurrence t(n)=t(n-1)+O(1) on the coins array
Dumb question: number of ways to make change for zero cents is One. Why is that? If I had no money, then how can I make change for it. Just trying to understand the intuition here.
There is one way to give you no money, namely by not giving you any money.
Speaking in terms in the real world, that really sounds a pretty bizarre situation: someone suddenly asking you a change, for 0 money. But if we think in a more programming way it makes more sense: imagine receiving an input of 0, we would return an empty set. The empty set is a valid return, no money were given, so we return a set containing no coins, the transaction is valid because nobody were given more money than the other part, so that counts as a way. But now think in a situation were we are given an amount where all the coins we have are greater than that amount. We can't return an empty set. That means we are returning 0 money, but we received an amount greater than 0, if we return an empty set we would be stealing money from the other part, so there is no way to give a change, so the number of ways is 0 in that last situation.
@@Ouaueaio that makes a lot of sense. Thanks a lot. This helps. I will apply this thought process for other Dp problems. You made my day!
Is the runtime for this solution linear?
Anyone tried this solution out and worked ? I'm implementing this in Python and it's just doesn't compute the ways the way it's supposed to, and it's been throwing some errors
Looks like there is a mistake in the lines inside the while loop
By far the best explanation!
No probably not. Could have been much better if she walked the code through an example.
I think this solution is kinda cool but very unintuitive to me. i always lose the track in the halfway thru reading it.
The question on HackerRank states that coin is a value between 1 and 50. So basically it say's it can be 49 or 13. I hate when one time you supposed to make assumptions to real world and other time have tests failed and find out that "you should have been reading more carefully".
Use quarters or either 25's to be consistent. You are basically making this more complicated.
Thank you for these. :)
increase font size plz
Thanks so much for your video. It was really helpful!
how many ways to make 0 money => 1 way ? hows that ?
use 0 coins each.
I had this same question. The only way to make 0 money is not use any coins. That in itself is a valid way to give 0 money. Thats one way to think of it. Another way to think of it is that you are passing the remainder or your initial amount minus some coin value to the next function. Well, when you pass 0 to the next function, in the case of 1 - 1 (a penny - a penny) you have found a valid combo and need to return 1 since all the coins you have used so far "fits"
The DP classic problem.
Please do not assume that everyone using this lives in the United States of America. Please try to make your videos understandable to the global audience, because currently it is just gibberish with quarters, nickels, dimes and what not.
Please do not assume that this video is meant for people other than Americans.
FUCK OFF THEN
the dynamic programming algorithm for this problem works for any denomination of change, it doesn't have to be {50,25,10,5,1}
exactly
can somebodyy please give the code
This code is wrong
Seriously, what is with this channel and recursion! Recursion is generally discouraged in code bases bc it adds unnecessary complexity. Also, it is slower than non-recursive code by some x. It's generally just a way to pretend to be "extra" smart.
Often, recursion is far simpler than iteration. And it isn't slower if it is tail-recursive (that is, the compiler will translate it to iteration anyway).
recursion can be faster depending on the algo/language since it will be compiled into a simple "jump" instruction in assembly