Coin Change Problem

[00:00:00]
>> All right, so we're gonna do one more problem, and this problem is super interesting, but I need a little bit of audience participation. I want four values between 1 and 10.
>> 7.
>> All right, that's one. We got one. Next one. Go, John.
>> 3.
>> Wait, what?

[00:00:15]
>> 3.
>> 3, I thought you said t. I was like, that's not even a value.
>> 8.
>> 8, my goodness, this is fantastic. All right, one more, go.
>> 9.
>> 9. I really hate your values you've chosen. I should not have done audience participation. You guys are just the worst.

[00:00:31]
So we're gonna do a thing called the maximum coin change problem, meaning given some number, how many different ways can we make change with these coins? We have chosen perhaps the world's worst denominations for coins, but we're gonna do it, all right? So I'm gonna take these values and move them down.

[00:00:50]
3, let's see. Let's go like this 3, 7, 8, 9. This is where dynamic programming really made sense to me. All right, so let's pretend we wanna make change for, let's do 15. All right, we need to make change for the number 15. Here's our denominations. If we had to make change for 0, how many different ways could we make it for 3?

[00:01:19]
>> 0.
>> 1, we had no coins and we've successfully at it had the sum. 1, how about 7? Same thing, all right, 1. Okay, fantastic. 8, fantastic. 9, fantastic. 1, okay, we got this. I'm gonna draw a nice little line this way, really long. That was so satisfying.

[00:01:48]
All right, now I'm gonna do this, I'm gonna go 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, no, I ran out a room, 11, 12, 13, 14, 15. Okay, we had to kinda tighten it up a little bit. Just tighten it up a little bit. All right, so I'm gonna have to draw a lot of lines.

[00:02:17]
Because if you solved this without knowing the dynamic Programming solution, you'd effectively have to do a series of for loops for every single change type in your coin system. So if you had 21 different coins, you'd have to have a 21 deep for loop, just checking every possibility at all times.

[00:02:34]
And every time you make a change, you recompute a bunch of values. Well, right now we know one value, which is very simple. We know for a fact that if we had to provide a change of 0, there's one way to do it easy. All right, we're gonna start with our first one right here.

[00:02:52]
We're only gonna consider this change. It doesn't matter. Let's pretend we had a coin of 3. How many different ways can we make change for 1
>> 0.
>> 0, all right? You can't even provide it. It's a 0. It's just not even possible, all right? How about 2?

[00:03:08]
Can we do it with 2? No, we cannot. This is where it gets interesting, 3. Can we do it with 3? So technically, you can think of it two different ways. If it is a module of the coin = 0, all right? So whatever our n value is, or technically our i-th value, if our i-th value modulo the currency equals 0, we can just draw a 1 right here.

[00:03:34]
But another way to think about it is we can make change for this if we take the magnitude of our current change and walk back that amount and see if we could make change for that previous one. Meaning if we can make change for 3, it also means if we added 3 more, we could make change for 6.

[00:03:56]
If we had 6, we know for a fact that if we added the coin size, which is 3 to 6, we could also make change one way for 9. Meaning there's one way we can make change here. There's one way we can make change here. There's one way we can make change here.

[00:04:11]
There is no other possibilities. That is it. So, at 3, we could walk back. The size of our coin say, hey, could I make change at this spot? I can make change at that spot, which means I'm divisible here, I can also make change at this spot. So 4, no.

[00:04:30]
5, well technically, check right here, no. 5, no. 6, yes, because we got a 1 right here. 1, 7, no, 8, no 9, yes we can, holy cow. 10, no 11 [SOUND], 12, yes, 13, no, 14, no, 15, yes. Okay, so we're starting to see a bit of a pattern here.

[00:04:56]
All right, now let's pretend we have two coins inside of our change list. Well, we're gonna do one extra thing here. We can make the different amount of changes here based on two conditions. How many ways we were able to make change at this spot for our previous coin, and how many ways we can make just change based on bar coin size minus back?

[00:05:22]
So right now, can we go 7 back? No, we can't. That's negative 6. You're giving me money at that point. So that 0. How many ways do we make change in our previous solution? 0. So we can do it 0 amount of ways at this point. What about 2?

[00:05:37]
Well, up here we just couldn't. Back here, we're off the board, that's a 0. Right here, at 3, how many different ways can we make change with a 3 and a 7? One way, because we have the 3, we bring up that 1, try to go back here, it's gone.

[00:05:54]
Therefore, 0,therefore, there's one way to make change here. Do it again. Notice that we used a previous value. Again, previous values are used to calculate future values. Again, 4, that's 0 + 0, 0, 5, 0 + 0, 0, 6, use the previous value. There's one way to make change for 6 with 2 coins, 3 and 7, which is two 3s.

[00:06:17]
That's it. There's no other solution. There's no other way we can make change at this point. Erase that, get the hell out of here. Plus 0, 1. Now this is where things get interesting. Now we add the previous values, different ways to make change here, 0 plus. We can now make change at this point, 1.

[00:06:35]
Look at that. It's starting to happen, which means at 7, with this type of tender, we can make a unique change value of just 7, and that is it. All right, let's keep on going. So I'm gonna start going right here. We go over 1. I got 0 up top plus 0 right here, go over 1.

[00:06:54]
We got 0, we got 1 up top and we got 0 right here. Now, this is interesting in the sense that at 10, we have 0 top we can't make anything there, but we have one right here. So what happens right there? Well, if you think about it, you can make a 3 and a 7, and that is it.

[00:07:15]
So by using our previous 3, we know for a fact we can make a single piece of change right here. If we remove that 7 out of it, we can make that change right there. So therefore, we have a 1 right here. Okay, fantastic, did I forget to run a 0?

[00:07:30]
I did, let's do it again. Let's go right here up. My goodness, way too far back. We've got 0, 0, 0. Now we got, we can make 12. Notice that there's no way to take 12- 7 and use a 3. We just can't do that. Therefore, we get a +0.

[00:07:48]
That's a 1. Fantastic. So now we got a 0 from up top plus a 1 back here. A 6, which makes sense. Again, there we go. Because 13 is gonna be 3, 3, 7 to make change. We were able to make change like that. Only singular way we can do that.

[00:08:06]
14 is going to be where were we? 14- 7 is 7, so therefore, we have 1 right here. Well, we have a 0 up top plus 1 right here, 1. Now we go to right here, 8. We have a 1 up top plus a 0 right here 1, okay?

[00:08:21]
So there we go we're starting to make momentum here. Now let's do an 8. Again, I told you guys picked just the worst numbers. Think if you would have had a smaller number here we'd have this thing growing it'd be crazy but instead we won't. All right, previous solution we've already calculated out we already know that a 3 and 7 can make 0 forms of change right here.

[00:08:40]
And an 8 can't be used. It's just 0. We already know this, all right? We do it again, all right? 0, We do it again. 1,0,0,1,1 unique point, all right? Because now we're at an 8. If we go back, we can use the 1 right here. Therefore, we have 0 from up to top plus a 1 from the 0 spot.

[00:09:03]
Now we're at a 1. Now we go right here. We have a 1+0, 1. We go right here. We have 1+0. Man, we're so close to hitting a 2. I can just feel it in my bones. It's gonna happen at some point. Again, we have a 1 but we have a 0 top.

[00:09:21]
Come on, just make it happen. All right, so now we have a 1 up top and 0 from over here. 1. We have a 1 up top plus a 0 from over here. Now we have a 1 up top plus a 1 from over here. So let's think about this while we're here, all right?

[00:09:36]
There's two ways to make change at 14. Let's think about how we would do that with all three little 10ds right here. First off, we can make change with 7, 7, all right? What is 14- 8?
>> 6.
>> 6.
>> 8 + 2 threes is the only other way we can make change.

[00:09:56]
And we were able to do that because we already knew for a fact at a 6, we already knew that we could make change once here. So therefore, we can use the offset to be able to calculate right in. At 14, we can make it into a 6, therefore, how many different ways can we make change with the 6?

[00:10:11]
We already know that answer, boom, goes the dynamite, awesome, things are going really good now. Now we get to here, we even got a 2, look at it, it's a 2 with the world's dumbest change count. So things are looking good. Look at that. You can't even make change for most of your problems, all right?

[00:10:23]
Any of your problems, it doesn't even work out, all right? We go to 15, so we gotta go all the way back to 15- 8, 7 and then this one, so we got a 1+ 1, 2. Now we could calculate out those two different ways to make change, but we just aren't going to do that.

[00:10:39]
So now we're gonna go to 9, 0, 0, 1,0, 0, 1,1,1. Interesting point. Now we have 1 from up top plus a 1 back here. Now we got our first 2. Where is the 2? We got 3, 3s or one, 9. That's the only possible possibilities right there.

[00:10:59]
Okay, now again we have 1 from up top 0 from right here. We got 1. Boom go over again. 1 from top, 0 from over here. We got 1. We got 1 from up top plus 1 from over here. That's a 2. Hey, we got a 2. Now we got a 0 from over here, 1 from up top.

[00:11:16]
Got 1. We got a 2, 0, 2. And now we got a 2 + 1, a 3. Our first 3. We actually got 3 different ways to make change here. If you think about it, 9- 15 is a 6, so we at least have 9 + two 3s.

[00:11:30]
We have five 3s. And what's the other way? I'm trying to think of what's the other possibility here.
>> 7 + 8.
>> 7 + 8, all right? Yeah, 7 + 8, there you go. And a 7 + 8. So there's our three different ways we can make change.

[00:11:44]
So this is what dynamic programming is supposed to be, where you build past solutions, or you use the easiest case to build the next step. You don't have to recompute the same thing over and over again. Because if we really were to write this out in for loops, we'd have to be like our biggest change.

[00:12:03]
We'd have to have i = 0, and we'd have to step by our biggest change, which would be like i + = 9. And we'd have to sum them up and do it over and over again, seeing how many times can we hit 0 on our way down.

[00:12:17]
Which would be just like, yeah, super inefficient because we just be calculating 3 over and over again. We already knew that answer. So there you go. This is dynamic programming. I think this is super fun. I love this stuff. I wish I was better at it, but I like it's very difficult to become good at this one.

[00:12:33]
And every now and then when you get the chance to use it, especially like either in our interview or your job, it just feels so good. I recently got to do a problem in which I had to use a linked list and all these ways to calculate out time.

[00:12:44]
But it turns out all I had to do was just turn it into a singular number. And so even at Netflix, I one time was able to use a dynamic programming problem to solve a real world problem. And it was absolutely fantastic because it was way too slow beforehand and then became just like a constant time for everything.

[00:12:58]
Very fantastic, absolutely love it. Hopefully this all made sense. Hopefully this shows you the value of dynamic programming because it is very unusual, but it's super cool. And there's tons of different ways to solve stuff. We just aren't doing those tons of different ways. And I'm not gonna do any more problems because at this point they're all pretty wild.

[00:13:13]
And once you see the answer, you're like, that's simple. But to come up with a solutions. This is ridiculous. It's ridiculous.
>> Does memorization relate to dynamic programming?
>> In a sense, we're memorizing. I mean, that's what we're doing is we're remembering the previous answer, so when you get the next one, it's a memo.

[00:13:31]
We just look into the past for it. Now, when it comes to react, and you use memo, that's slightly different. Though it's the same concept. It's the same idea. You're just trying to remember what came before you, therefore you can just use the same value again.