Total Unique Ways To Make Change - Dynamic Programming ("Coin Change 2" on LeetCode)

in today's video well this isn't really today's video because I actually recorded this whole video I got deleted off my hard drive accidentally and now I'm actually in a huge pain because I have to reteach this but we are going to do the total unique ways to make change problem so what is this question asking us it is asking us given an amount and a certain amount of coins one two and five coins or we could just gather two coin given an amount we need to say how many unique ways are there to make change for this amount so 4 td amounts 5 if you give me a 1 2 and a 5 point they're going to be 4 unique ways I can just use the 5 I can use a 2 2 and a 1 I can use a 2 and three ones and I could use five ones if I have n amounts three and I just have the two coin am I going to be able to make change no there will be 0 unique ways to make change so how are we going to do this problem yes maybe is done in the programming to solve this question what we are going to have to do is we are going to at each stage we are going to consider a certain coin and see how it changes the total amount of ways that we can make change this is very similar to the zero-one knapsack problem and you will see what I mean when we go through this dynamic programming table and I will show you these subproblems and I want you to know these subproblems and not memorize the patterns of how we fill the table out so let's look at that right now every single dynamic programming video should start out with the explanation of these subproblems it's not about the table behind me it is about the subproblems and how they relate to each other so what does this mean what does that sell me that cell is the subproblem if i need to make change for one and i only have the coin 1 how many total ways are there to make change this salad means i need to make change for the amounts 3 and i only have the coins 1 and 2 and notice every row represents the addition of another coin this row represents a deal one point this row represents adding the two coin this row represents adding the five coin if I put a dot right there if I have the amount one and I have the one two and five coin how many total ways are there to make change and then finally the original question that we asked if I have an amount of five I need to make change for and I have the one two and five coin how many total ways are there to make change we are going to be answering six times four we are going to be asking 24 questions twenty-four questions to answer just one question which is our ultimate goal which is the goal at the end of the table here is how we start our table if I have a zero no matter what coins you give me I'm going to be able to make change one way which is to do nothing and again I have zero it does not matter what coins you give me you could just have the one you could have the one in the two you could have the one two and the five and it does not matter there will be one way to make change using no coins okay so that makes sense so what if I have no coins at all and I need to make change for one then I will have zero ways to make change if I need to make a change for the amount to and I have no coins how many ways can I make change zero ways and then it's the same thing any amount you give me if I have no coins there's no ways I can make change so now the answer to this cell is we're adding the one point so we have two choices use the one point or do not use the one point so here is how the relationship forms the relationship is if I do not choose the one point our subproblem is make change for the amount of one and we only have the one quarter if I do not use be one my amount stays the same but my subproblem drops through and I have no coins so if I don't use the one point I drop down a row and I have no coins but I'm still solving for the amount one if I do use the one it changes my amount but I stay in the row where I can use the one coin so I subtract one from 1 which is zero but I stay in this road so not using the one point using the one coin what I add those two possibilities I get to where I'm sitting at so this cell is one plus a zero if I do use the one coin then there is one way I can make change if I do not use the one point then there are zero ways I can make change so when I am at this position I have those two choices and the addition of those two choices gives me the total ways when I need to make change at this cell let's ask ourselves if I only have the one coin and I need to make change for two then I subtract one from here and then I go here within the same row if this is if I do choose the one coin so I did choose the one coin so there's one unique way to make change if I do choose the one point if I don't choose the one coin then there are zero unique ways to make change because I just can't make change if I have no coins so 1 plus 0 is 1 and again 3 minus 1 I do choose it I don't choose it I do choose it I don't choose it I just go up a road because I'm not considering it every wrote we consider the an additional coin I'm not considering one so I jump up to the 0 and if I do consider I do my amount minus the coin amount 3 minus 1 lands me at 2 I use the coin so I subtract by its amount but I still am in the row where that coin is considered because I just used it so 1 + 0 1 so now again don't use the coin 0 do use the coin 4 minus 1 is 3 3 the answer is 1 at that subproblem so 1 plus 0 is 1 and now if we don't use the coin it's 0 if we do use the coin it is 5 minus 1 is 4 and then we stay in the same row so it becomes 1 plus 0 which is 1 so think about this if we just have the one coin how do I make change for 5 I do 5 1 coins if I just have the one coin and I make chase for 2 that is 2 1 points each of these are 1 unique paths so do you see how this kind of intuitively makes sense and when we build these sub-problem answers we're going to have a correct answer down here so now I'm considering the two points this is a big jump this is why this problem is very similar to the zero-one knapsack problem we're now considering the two point we already considered the one coin we're considering the two point now what I do is can I even use the two point when I have an amount one I can't even use the two point so I can't vote one minus two I'm gonna go negative so here all I can do is not use the 2 coin so I just don't use it so it becomes 1 plus 0 because we just call a 0 so it becomes 1 and that becomes our answer so now when we're at 2 we can use the 2 point so if we don't use the 2 point we get home totally unique ways of 1 if we do use the 2 point it becomes 2 minus 2 which is 0 and we stay in the road because the 2 point is still considered but it's subtracted from our amounts because we used it so we did 2 minus 2 brought us to 0 in the same row and now we have 1 1 plus 1 is 2 if I have a 1 in the 2 point there are two unique ways to make change for it a 1 and a 1 and just the 2 point that answer makes sense so now if we're at 3 don't use the 2 point we get 1 if we do use the 2 point 3 minus 2 is 1 and now we stay in the same room 1 plus 1 is 2 and now here don't use the 2 point we get 1 do use the 2 point 4 minus 2 is 2 stay in the same row we get 2 so now to plus 1 is 3 if we need to make change for the amount for and I have a 1 in the 2 coin there are 3 ways to do that I use 2 two points I use 2 and then 2 1 coins or I just use for one coins three unique ways it's making sense so far so now don't use the 2 coin I have one unique way if I do use the 2 point 5 minus 2 is 3 we have two unique ways and then now 2 plus 1 is 3 and now if we are in our final row we are approaching our final sub-problem if we're at 1 and weird considering five point the five coin has jumped into the picture now so now we're considering the five point can I even use the five point when I'm making change for one can I even use it when I'm making change for two can I even use it when I'm making change for three I can't even consider the five point so what happens I can't consider the choice of using it I can go 1 minus 5 thats negative so I considered only the choice I'm not using it so this becomes 1 this becomes 2 this becomes 2 this becomes 3 why because up to 4 we still can't use the 5 point but what happens at 5 we have our choice opened up to us to use the 5 point if I do not use the 5 point there are 3 unique ways if I do use the 5 point 5 minus 5 is 0 stay in the same row because 5 is considered in this row so we have one unique way if we do use the 5 we have 3 unique ways if we don't use the 5 the addition of those is the unique ways if we have one 2 in 5 for the amount of 5 so 3 plus 1 is 4 and that is our answer there are 4 unique ways to make change for 5 given the coins one two and five and each iterative step every road we considered another coin we considered another coin we considered another coin at the end we knew what the total unique ways are when we consider all of the coins and that is what dynamic programming is about we built our answers up through the relationships between the subproblems we saw how they related and we built up to our global answer here which is 4 so that is how this problem works so a lot ask about the intuition behind this so a lot of these problems intuition can drive the way you solve them but sometimes it's just remembering these patterns remembering the zero-one knapsack type problems that is the key to this problem so let's look at time and space complexity and so now the time and space complexities for this problem we are going to be computing the answer to a times C subproblems so that is the time we are going to spend solving subproblems as for a space we will be storing a t plus 1 times c plus 1 subproblems so our space complexity is just a times C and remember it is the amount and C is the number of coins that we are given we also can do this in a space but I wanted to keep it this base complexity for this walkthrough so that we can see how we change the coin we consider in each step and this is very similar to the zero-one knapsack problem which I highly encourage you to watch that was this question if you like this video if this was a clear explanation hit the like button and subscribe to the channel I hope to do videos like this every day to help others in the software engineering interview so this [Music]

Channel: Back To Back SWE

Views: 121,552

Keywords: total unique ways to make change, ways to make change, total ways to generate change, make change problem, total ways to make change problem, dynamic programming, memoization, Back To Back SWE, Software Engineering, computer science, programming, programming interviews, coding interviews, coding questions, algorithms, algorithmic thinking, Google internship, Facebook internship, software engineering internship, swe internship, big n companies

Id: DJ4a7cmjZY0

Length: 11min 42sec (702 seconds)

Published: Sun Jan 20 2019