OK, so now it's time to move on to the code portion of this dynamic programming tone coin problem.
So let's go ahead and get started.
I basically already made a little new project here called Coin ODP, and I just have an empty main file
with a main function kind of skeleton here.
And I included a vector as well as, I assume, because I'm going to use a vector is my container for
my table.
So I'll get right to it.
I'm on foot using namespace for this.
And then.
In addition to the function that's going to be like men coins function that does the entire algorithm.
I'm also going to make a helper because I do know from our last lecture that we had a part of the algorithm
where we kind of needed to update the minimum value.
So we had to make a comparison to see which one was bigger, right?
We basically, if we came up with the smaller minimum number of coins, then we would replace what was
in a current position stored at whatever was stored in the current position.
With that new minimum value.
So that means I'm going to want like a min function.
You don't have to, but I'm going to do it just to kind of break the code up a little bit so that a
return an integer.
I'm just going to call it man do.
And A and and B.
So of course, we're going to have our main coins function.
You could make it return just an integer or something, but I'm actually just going to make it void
and going to print my minimum number of coins inside of the function.
So I'll make it void men coins and I'm going to pass it my the vector of coins, and then I'm also going
to make an end, which is the original change needed.
Cool.
So let's go ahead and implement these functions.
The men will be easy.
I'm actually just going to do it with a ternary, so I'm going to the return and basically a less than
B than a otherwise b.
So that's pretty simple there.
All it does is find the minimum of the two in return, the minimum.
So let's see now I'm going to do mine in coins and I will do this vector and coins and change needed.
And hopefully this is big enough for us to see an increase that size a little bit.
So what's the kind of the first thing that we need?
We should probably make our table right?
Think back to the lecture and think of how our table started out.
It basically had a zero in the 0th position for like that serious problem.
And then the rest were 12th in our example.
And the rest were 12 because it was one more than what the change needed value was.
So with that in mind, let's make our initial table here.
So I'm going to call it table.
I'm going to say change needed is going to be the size plus one, actually.
So change needed plus one will be the size.
And then I'm also going to put change needed plus one as the values that fill it.
And since we don't want that first initial value, the zeroth position to be like, for example, well,
if our changing was 11, we're going to go ahead and update that right away.
So I'm just going to say table of zero is zero.
So hopefully this makes sense.
This is just saying that the size of the table is going to be one more than change needed.
So think of this, for example, if you have change needed.
11, we had an 11th position in the table and if you're starting at zero, that means, you know, the
size is going to be 12.
That's why we're doing change needed +1 for the size and then the values that we're filling this with
is just going to be like if you're thinking of the example, it would be 12 as well, one more than
11.
But of course, we're just adding into this variable amount change needed.
And then our zero position is zero, of course.
So let's think about how to start.
The algorithm was the first thing we kind of did like.
The main overarching process is just looping over all of these sub problems.
And so the sub problems are basically the positions of the table going from zero all the way up to whatever
change needed is.
So I'm going to make this kind of range based loop here.
So four and I go zero, I is less than or equal to change needed because we're going to have a position
for change needed.
Remember, if the change needed is 11, we have an 11th position.
So that's why it's a less than or equal to.
So I want to make this outer loop here.
Then what were we looping over in kind of in between this?
So if each position that we were looking at, we had to also try out each coin as long as it wasn't
too big, right?
So let's loop over our coins.
So I'm actually going to see and do a looping over the items for this.
So I'm going to do for any coin in coins.
You can also do like auto, but I'm just putting the right here.
And basically, we were saying, I think I just said to that we are only going to consider a coin if
it's not greater than the amount that we are currently looking at getting change for.
So that is our eye, right?
Eyes are some problems and are some problems are also like, how do we make change for blink?
So, you know, if I three, it's how do we make change for three?
So as long as the coin is less than or equal to so you can flip this around as long as I is greater
than or equal to coin, then we can basically just update our tables.
So I'm just going to say Table I equals men and think about this right here.
So we're updating that value to the minimum right.
But how did we do that?
Well, what we did first was we subtracted the coin from the current sub problem that we were at right
from the current.
How do we make change for this?
So how do we make change for three?
Well, what we did was we started out with the coin one.
We subtracted one from three.
So and then once we got that answer, which is to then we looked at the two position in the table for
what was stored there and added one to it, right?
That's kind of a mouthful.
Break it down.
So right off the bat, we know we're trying to update where we currently are.
So table is the value stored where we're currently at.
We're at high and we're seeing what is stored here.
Can we take a coin and find a better minimum?
So one of the things we're comparing is Table II.
The next thing is basically we take that position where we subtract that coin from I, right?
We get what's at that position and then we add the coin.
We're considering to it.
We're considering a coin.
So if I, you know, give someone a coin, then I subtract that coin from the total amount and then
I ask myself, OK, how do I make change for this new smaller amount?
I go, Look there in my table for that new, smaller amount.
I get the amount from it.
And then I say, Well, I already gave a coin to this person for the change, so I need to consider
that coin that I gave.
So I do the plus one.
So just trying to connect this back to the previous lecture.
OK, so that is getting annoying with this scroll and probably make this a little bit smaller.
There we go.
So.
OK.
OK, I got Jones down there.
OK, so I need to put a semicolon here, and then so, yeah, that updates into our table.
So that's kind of if you think about the previous lecture, that's kind of all we were really doing.
Right.
So we didn't have to do anything really else besides that, so we're kind of handling everything we
need to hear.
So if we fill out our table just like that, where was our final answer when we're finished filling
out a table?
So if I'm going to go ahead and print this out, so I say.
Fill out and then men.
No coins.
What am I going to print here, so it's going to be stored in our table?
If you remember correctly, like when we had our 11 past as the change needed.
We actually had to look at that 11th position to get our answer right.
So that's what we're going to do.
We're going to print out a table of change needed because that final thing in the vector is storing
our answer.
And I'm just going to put an end line here.
OK, so this is pretty much our whole function here.
So let's go ahead and make a little example.
I'm going to go over the two examples.
One of them is going to be what was in the last lecture.
So we have something like the nominations we're going to call this number one.
It was basically one, five and 10, right?
And we were looking for change 11.
So I'll remember that the other one was like our greedy method, one that failed with the greedy method,
right?
And that's why we wanted to move over to the dynamic programming methods so we could get the real optimal
solution.
So that was something like we had a three, no a one and then an eight and then a nine and then like
a 14.
I think because we were looking for 17 and we said the greening method basically said, Oh, 17, the
best way to do that is 14 and then one and one and one three one.
So that was.
You know, for coins, which was suboptimal, because if we want 17, we could have just taken these
two here.
So we're going to include that so we can see how our dynamic programming method now is fixing that problem
that we had with the great method.
So let's call our function and I'm going to start off with just passing it to number one.
And 11, because that is what we used in the lecture.
Let's go ahead and print this out.
If if everything is correct, remember for change.
11.
We should be only having two coins.
It would be a 10 in a one.
Right.
So right now, we're only solving for the actual minimum number of coins.
Once we check our kind of test these two here, then we will go in and try and add some code that handles
getting the actual coins that we use.
So let's run this.
We should be getting the two here.
OK, so that looks good.
M. Collins is, too.
Let's go ahead and try the names too.
And so this was when we were asking for 17 in the greedy method.
It was doing 14 with three once, which is four coins.
But really what we wanted was the eight and nine, which should be two.
So our answer should also be two for this.
OK, so we also get men coins, too.
Cool.
So let's go in and add some code here.
For us to be able to also record the coins that were being used.
So at first, you might have tried this on your own, and if you succeeded, you know, props to you
for being able to figure that out.
I said it was somewhat trivial, but it's not really that trivial to think about, it's kind of confusing.
But what we need to think of is that recording the minimum number of coins is kind of the same as us
recording the coins that are being used.
We're looking at these sub problems and trying to see well for this sub problem, what was its minimum
number of coins?
And we kept doing that for the whole loop and the whole table that we were building.
So we can pretty much do the same type of thing for the actual coins that were used.
We can say, OK, well, let's see if I go to if I jump somewhere in the table to this previous problem
has been solved.
What were its number of coin or sorry?
What were its specific coins that it used?
And if I have like less coins basically then or I'm actually updating, you know, the value of coins
like I found something that was less.
Then I'm going to want to update, you know, so we're basically going to do the same thing.
We're doing the same exact idea idea of how we're updating the minimum number of coins.
To keep track in another table of the actual coins that we're using.
So that should help us simplify the problem a little bit.
So if we're going to need to keep track of another table, let's go ahead and make that table, so I'm
going to make another vector here.
But instead of making a vector, it's if you think about it, we're keeping track of all the coins that
were used.
To create change for a specific change needed, so that's going to be another vector, so we're going
to basically have to make a vector of vectors so like a 2D vector.
So I'm going to make this vector vectors and then call it cleans used, I think.
And so it's basically going to be doing the same thing.
You can imagine it just like our table, which is a vector of ants, but instead of ants, we're storing
like what coins we're used.
At some given some problem.
Which will be an index, you know?
So how am I going to modify this now?
Well.
One thing that I'm going to need to do is I'm going to have to I can't just make some new vector in
here to keep track of the coins used and then add it like later in the hour, Lou.
So I don't need to add in the out of loop.
So it makes sense with the scope, so it'll recognize it.
So first off here, I'm going to just put this inner vector, which is the actual vector of coins that
we're going to put in a specific index for our coins used.
We're going to be updating this little like inner vector.
So this guy, we're going to be updating that inside of this loop because this is looping over the coins.
So in here we will add the coins that we're keeping track of to it.
And then after this loop is done, so over here, when we're back in the scope of the outer loop, then
we're going to have to add this highlighted vector to our coins used.
And since we're adding it there, we're going to need to declare it here first, because since we're
already referencing it, we basically need to have it like exist already.
It's really because of in here too.
We're going to be able, we're going to be needing to do stuff in here as well.
So I'm going to just declare it right here.
So it's already declared and we call it new vector.
So then what I'm going to do is I'm going to switch this around a little bit so I can minimize the code
because I wanted to call this again and I may need to check another condition.
So basically, what I am going to do is set this to a variable, I want to say end smallest.
Is equal to this.
So I save it in a variable there.
Then what I'm going to do is I'm basically going to say, OK, well, if smallest is not the same.
As what I already had in the table, that just means that it is getting updated right.
In that case, I'm going to basically.
I'm basically going to try and look back at the coins that were used.
At the same problem that I need to look at, so let's let's talk about that a little bit more.
I'm going to go ahead and remove this for now because I just changed it to be recorded in this variable
here.
So this is a condition just saying if we're going to update it, so if the smallest is not Table II,
you notice there's table, I hear that if it was Table II, that means that we didn't find something
that was smaller.
So we're not going to update our current position that we're at.
So what I'm going to do is I'm going to set this inner vector of coins that were used.
To basically this right here is what I'm looking for.
I index, I remember I said it's going to mirror the table that we're using so far, but rather than
storing the min number of coins, we're trying to store all the coins used.
So we're using the same concept.
But what I'm going to do is I'm actually going to try and grab what was there.
So I'm going to say coins used that's like synonymous with our table here, basically for this other
part of the problem.
And then I'm going to use AI minus coin because that is the index that I'm using.
I'm looking at the same sub problem.
A-minus coin.
So I'm basically getting the coins that were used at that previous said problem that we're looking at.
So that was like that three, you know, when we had.
We're currently on three and then we're using the coin one, and we did three minus one is two, and
then we went to the table and looked at.
How to make change for two.
And we grabbed what was there.
That's what I'm doing.
Same thing.
I'm looking at basically, you know, three minus one, if we're using the same example is two and I
go to like how to make change for two.
But we're not in the table anymore, our original table or in this other type of table that stored the
actual coins that were used in a vector.
So I'm setting this new vector equal to the vector that's stored there, that holds the coins that we're
used for, that some problems.
And then what I can do is basically do new vac
dot push back the current coin because we have to consider it right.
So you notice here we're adding one for the number, because this is the coin, we're saying, Hey,
I already gave this coin, so I have to count it.
Same thing here.
I already gave this coin, so I have to record it.
I'm not thinking about the fact that it's just one coin, I care about the actual coin now, so I need
to add it to this.
I got what was at the cell problem, but the fact is is that I already gave out a coin, so we need
to keep track of, Hey, this is part of the solution for this problem or this final problem that we're
at.
I have to use the coin that I just gave in addition to what the answer was for the sub problem.
Hopefully that makes sense, try and break it down.
So either way, regardless of this part, right here we are and you said, you know, if the coin is
less than or equal to I and we already have the smallest here.
We know that it's either going to be the same or it's going to be something smaller.
So it's safe to outside of this check here.
Just go ahead and do Table I.
Is now the smallest, whether it updated or not.
We're just re updating it to me the same thing or updating it to be the actual smaller one if it ended
up being this.
OK, so then like I said, what we have to do is once this inner loop is done, we have to add this
new set of coins, which are the solution.
To our Victor, our original coins use the 2D like the outer dimension dimension of this vector, where
we're keeping track of all the sets of coins that were used for a specific solution.
So that's going to be right here.
I'm going to say coins used, Dot pushed back and then new back because that was the updated coin list
of coins solution for this problem, or it could have been for our final answer.
OK, so now that we updated this, we're keeping track of it, and remember, it's totally mirroring
this table that we've already done.
It might seem a little crazy like what we're doing.
We have this 2D thing, but it's only 2D because rather than keeping track of numbers.
We're keeping track of list of the coins used of the denominations.
So now that we're building that solution as well, we can add another little sea out here.
So I'm going to say see out coins used for this minimum number of coins.
I'm going to have it print on the same line.
I'm going to do a little item based loop again, and I'm just going to say for auto and I kind of do
it different this time just to mix it up and it's going to be coins used.
What's it going to be?
We're totally mirroring our other table, so it's going to be just like this.
The answer is going to be stored at the exact same position as the position it was in our table for
the answer that had just the count.
So we're going to use that same thing, we're going to say change needed.
That's the that's the position that has our answer also in this new this new league table that we're
creating.
So we're going for each one of the coins stored at this last position.
And so I'm just going to say, see out I because we're looking over the actual items and then I'm going
to put a little space here just to separate them so that all print nicely in my actual.
Main coins function.
So let's run this again, let's kind of look back at what our answers were, right?
They were both too.
Let's go ahead and.
Check, we already have this one in here, so we'll check this one out, right?
So the greedy method, let's just I'm just reiterating this, so it really like gets to the point of
like what we're talking about.
So 14 and one and one and one was what really method used, and that was not optimal.
That was for coins.
The optimal solution was these two.
When we ran it last time, we got a successful answer that said that the main point was to that is correct.
But now with verify that the actual coins you used were eight and nine.
So then we can really feel like we did this correctly.
So let's go ahead and run it.
So there we go.
We see that nine in eight with the two coins that we used.
And it says two coins.
So we have seen now that this effectively solved with the greedy method can solve it looked at every
possible solution and that made it realize that there was this better solution of just two coins to
make.
17.
Let's go ahead and test out our other ones.
So we've been an arms one, and our example in the previous lecture was 11.
We already kind of talked about that the minimum number coins is two, but this time what we should
be seeing is a 10 in a one because that is what we would use to make change for 11.
So now that that switch to, let's go ahead and run it.
And there we see our answer, so M. coins as to what are the coins that were used for that solution?
The coins were ten in one.
OK, so hopefully that was pretty interesting for you, dynamic programming is really cool, and this
is just one of many, many problems that can be solved with dynamic programming.
We're going to get into some more after this.
But if you were able to figure this out on your own, then I definitely give you a lot of respect.
If not, it's totally fine.
You know what?
It's a difficult problem, and I hope that now after seeing this solution video, you were able to understand
how we put all this together.
OK, so with that, I'll go ahead and see you in the next lecture.