OK, so now we're continuing from where we left off with our greedy method.
But just like we said in the last lecture, we're going to find a better solution to our optimal change
problem by using dynamic programming.
So let's see how we're going to do that.
First off, let's do a little reminder of what the problem statement is.
So what is the minimum amount of coins needed to make change given a list of denominations in addition
to that?
And we're going to ask what coins are used in that minimum amount kind of like what we did in the greedy
method in the previous lecture.
So in this actual lecture, I'm going to focus more on just the minimum amount of coins rather than
what coins are used to make that combination of the minimum amount of coins.
I'm going to leave that for the code later on.
I'm also going to be going over an example that is a little bit more simplified.
So it's not going to be exactly kind of the example that made our greedy method fail.
So but I will include that example when I do the code so we can see how it actually works with dynamic
programming, unlike the greedy method where it didn't work.
But just for simplicity, I've kind of made it a somewhat trivial example to explain this, so I just
want to put that out as a disclaimer there.
So let's look back at dynamic programming strategies that we went over, so we have a top down method,
which is memorization, that's kind of what we use for the Fibonacci and then we have bottom up, which
we call a tabulation.
So in the first example of Fibonacci, that top down solution, if you remember it had a recursive tree
and we kind of eliminated the redundant recursive calls there where we were solving the same problem
over and over again.
This time we're using a bottom up solution, actually, so we're going to solve this coin optimization
problem with a bottom up solution.
Either way, if that you choose to solve the problem, dynamic programming involves solving all the
sub problems of the initial problem and then using those solutions to the problems to arrive at a final
answer.
So what we're going to do is build a table which you can think of as a vector or an array.
I'm just going to refer to it as the container most of the time, because I'm not sure exactly what
type of container you want to use when you do the code.
So we're going to store the answers to our previous problems in there, and we'll use the stored values
that are the answers to those problems, so problems to compute the next spots in the table.
So let's take a closer look at what we mean by sub problems.
So at this point when I say some problems, you're probably thinking of recursion.
But we can also represent sub problems in dynamic programming without recursion, i.e. using loops with
tabulation, which is what we're going to do for this lecture.
So a key point in solving dynamic programming problems from scratch, like when you get a word problem
and you have to turn it into code and figure out how to solve it, you should actually just focus your
thoughts on the idea of sub problems helping you with your final answer.
Don't focus so much immediately right off the bat on whether you're going to use tabulation or memorization.
Just try and think of Is this problem solvable with dynamic programming?
Does it make sense for me to use dynamic programming?
And if it makes sense, that means the problem.
The problem can probably be broken into sub problems where you could use those answers to the set of
problems to come up with a final solution.
So that is what you should think about some problem answers to come up with a final solution.
That's what you should think about when you're trying to design your strategy before you think about
the nitty gritty details.
So a sub problem just to kind of redefine what that is.
It's when we ask a question.
But to find the answer to that question, we also need to ask some other questions.
So it's a lot like what we do with recursion, where we start off with an initial kind of input path
to it.
And then we keep doing recursive calls where we like half the input or minus one just to arrive at a
base case that will help us answer all of those questions that we set aside with the recursive calls.
So same type of thing, just not using recursion in this example for this lecture.
So let's look at a visual way of kind of explaining this.
This time I'm using an example of our coins are change needed coin optimization problem.
So I have the denominations here.
I have a one coin, a five coin and a 10 coin, respectively.
If you're using US currency, a penny, a nickel and a dime.
And then the change needed is 11.
So I have like this tree structure here.
You don't need to think of it as like a literal like code type of thing with that recursive tree.
But it's kind of related to that.
I'm just using it to explain our sub problem kind of thing we were talking about.
So this root node here also it might be kind of hard to see with so many colors.
I never have any use, but this is a different color than this color.
This is gray and this is white, but it's kind of hard to see.
So these are different colors.
That's what I was aiming for.
So we start off with our change needed that can be represented by this circle or node or whatever you
want to call it up here.
It's like a root node for the tree.
This is our original problem we're trying to solve.
From that point, we can use any one of these coins because 11 is greater than the value of each one
of these coins.
So we could essentially subtract one of these and say that, Hey, I'm going to make my first part of
making change.
I'm going to choose a coin and I can choose any one of these.
So this is me using one coin.
This is me using, Oh, sorry, I only get the fact this is me using a five coin.
This is me using a 10 coin.
So, for example, if I take an 11 and then I use one, then that means that I have 10 right here.
So this is like another sub problem.
If I use one, then this node right here is essentially now me asking, OK, how do I make change for
10 now?
Since 10 is not basically since none of these coins in here are greater than 10, it allows us to use
all three of them from this point.
So you can choose any one of them is what I mean.
So you could use one and that would bring you from 10 to nine.
And you can use five, which would bring you from 10 to five and then you can use 10, which would bring
you from 10 to zero.
Let's take a look at this branch over here.
So if I have 11 and I use 10, that brings me from 11 to one and then I can use one because I can't
use five or 10, right?
If I'm at this node here, I'm essentially asking, how do I make change for one?
I just used a 10 that brought me down to only needing to find change for one.
So how do I change change?
For one, we only have one option because you're not going to use a five coin when you're just wanting
change.
For one, neither are you going to use a 10 coin that's too big.
So let's look at what these mean.
There's some colors here.
I said I was looking to solve.
How do I make the minimum change for one here?
And it's orange.
This is also orange.
And that's because it's the same sub problem.
The colors that I put here correspond to the same sub problem question we're asking about how do we
solve for a specific change needed?
So this is how do we solve for the minimum change for one in orange?
And so is this 10 minus five if we use a five?
Sorry.
11 my bed 11 minus five is six six.
Minus five is one.
It's why we were having this same.
How do I make the minimum change for one here, just like here?
Same with this blue that I already pointed out was six.
It's just like this dark blue here.
And then you have these light blues as well and this red.
So you notice that we have two oranges.
We have two of these light blues and we have two of these reds.
So we're essentially having to solve the same problems multiple times in this tree.
So that's kind of like what we ended up having when we were trying to do the dynamic programming solution
of the Fibonacci thing.
We're trying to get rid of having to redundantly calculate the same sub problems over and over.
I haven't even drawn out this whole tree yet.
You notice that if we were to explore all of the options to get all the way down from 11 to zero, I'd
need to write some more branches in this tree.
And even so, I haven't done all of the.
Even so, with me not having filled out the whole tree, you can already see some repeated calculations.
So that brings us down to this table here.
You notice that it also has a lot of colors here.
I said this Orange was us asking the question for a sub problem, how do we find the minimum change
for one?
Well, you notice that I also have an orange block right here inside of this table.
And I said, how do you solve the minimum change for one?
And we see a one right here.
So like you may have already figured out these colors in this tree with a specific problem attached
to them, correspond with the indices in the colors in this table, except that you notice in the table
there's no repetitions.
They're all different colors.
And that's because every single spot in this table represents its own unique sub problem.
How do I find the change for zero?
How do I find the change for one, how do I find the change for two?
And we're talking about minimum change each time.
So you can already kind of see that this strategy that you're going to use with the table is going to
eliminate a lot of these redundant calculations.
So let's move on and explore this further.
So one thing that we know is that the minimum number of coins for zero change needed is to zero coins.
If somebody asks you, Hey, can you make change for nothing?
And like, OK, well, that's nothing.
I don't need to give you any coins because you don't need any change.
Zero means zero.
So that's something that we know and we can kind of use that as a base case.
I don't mean base case like recursion because we're not really using recursion, but it gives us a point
to build off of so we can solve the rest of our sub problems.
So keep that in mind as we go on.
Like I said, each index in this table represents an amount of change that is needed a sub problem.
So, for example, the purple, the purple at Index seven means that it stores the minimum number of
coins needed to make change for the amount.
Seven.
So we're not only just solving how to make change, we are solving and storing the minimum amount of
coins for this problem at this location here.
And that's the same for each one of these locations.
So the final position in the container is Index 11, which happens to be the original change we needed.
So if you might have already figured out putting two and two together, 11 is actually going to be the
position that holds our final answer because this is same store, the minimum amount of points needed
to make change for 11 right here, which is what we were originally asking in our problem statement.
So unlike the greedy method, rather than immediately choosing the biggest coin and continuing on,
we want to subtract each one of the denominations from our current change needed.
By doing this, we will get a result amount that will be one of our indices on the table.
We can then find the minimum number of coins stored at that index and check to see if we were to add
one more coin to that.
Would it be a better result?
And why?
When I say better result, I mean less than what's already stored at some specific spot.
So basically, we need to cycle through each change needed position zero one to three in our container
and try subtracting each one of our coin denominations one, five and 10 from that change needed amount,
but only if it's less than the change needed amount, of course.
For example, if we have this to here, how do we make change for two?
Well, we're not going to try and give a nickel or a dime because that is greater than the change we're
trying to give back.
So that's what I mean by only if it's less than the change needed amount.
So that's kind of where wordy.
Let's break it down into smaller pieces and use an example.
We're going to start out with zero in the zero change needed position because like we already stated,
if you have no change needed to give, you don't really need to give any coins zero coins.
OK.
So each time we do one of these subtractions, the result of the subtraction will be an amount of change
needed that's already computed in our table.
And therein lies the efficiency of this solution.
We already have computed the sub problems.
You notice it's not skipping any numbers here, so we've computed every possible asking for change amount
up to up to the current one that we will be considering.
So that gives us the ability to look it up and find the minimum amount of coins that were needed for
that smaller amount, the smaller sub problem.
So for example, if I want to know the minimum amount of coins needed to make change for a one change
needed problem, I can look at my coin denominations and see that the only coin I can really use is
a one.
So I'll do one minus one equals zero.
And that makes me want to look at container zero to see what that sub problem was.
I notice that it says zero coins there.
Since I found zero there, and I'm using a one coin to try and make change, I'm going to do zero plus
one.
And remember, this plus one is not because the coin value is one, the plus one is because I'm using
one coin.
So as my coins needed, I'm going to see as the smallest amount of coin so far for my one change needed
problem.
So I want to compare it to what is currently at one.
But wait, there is nothing at one, huh?
So before we go about this, we're going to have to fill these with some initial values.
We need to fill our table with some initial values that we can compare against so we can update what
coin we're going to choose that will result in the smallest amount of coins.
But what shall we put here?
A safe idea is to put a value that is larger than the total possible number of coins we could have for
our original change needed problem.
So that means, like us using 11 pennies for a change 11.
So because of this, we can store any number that is 12 or above.
So I'm just going to put 12.
You can think of it the same way as us needing to put a number here.
That is one more than the size of the container because you notice we've put a solve change problem
for each number all the way up to the original number we were asking about.
Because of that, we need to put something slightly bigger than that, so it gives us the ability to
keep updating and a minimum the first time we update it, we need it to be bigger than any possible
thing we're going to compare against.
So that's why we're going to use 12.
So I'm filling all of these with 12.
So let's check our previous problems.
So if we do zero, which we took from here for our sub problem this year and we add, we add one coin
to that, it equals one.
Then we take a look back at here and we say is one less than 12.
Yes, it is.
So let's update container of one to one.
So that's what we do.
So we're going to do this for every position in the table until we update the whole table with the minimum
number of coins needed for each one of these change needed positions.
Each one of these chains needed some problems since the final position is changing for 11.
Of course, the value there will be our answer, so let's go ahead and step through this process.
Let's go to two now.
So the first coin I'm going to try with two is one, so I'm going to do how I get changed for two.
Well, I'm going to use one.
I'm going to use a penny.
So if I refer to it as U.S. currency, two minus one is one.
So now I'm basically asking the question How do I find the minimum number of coins for one change needed?
Well, let's go to the one change needed position in the table.
What does that say?
Well, it says that there's one is the minimum number of coins.
And you notice that this is an orange block here.
So I've denoted the thing that I'm bringing up here in orange.
So it says that the minimum number of coins to make change for one is one.
So I use that and then I'm also adding the one coin that I'm using right now.
Remember, it's not about the value, it's about the fact that I'm adding one coin.
That's what this gray one is.
One plus one is two.
Now let's go back and see if that's less than this right here, which is stored here.
It is two is less than 12.
So let's change this value to two.
So another thing I want to point out is that I kind of ran out of colors and I'm using red to denote
the current denomination that I am on as we cycle through these.
It has nothing to do with the red in this box here.
So I just wanted to make sure that you're not associating this red with this box here, even though
this is orange right here.
Do not associate the red in this original down arrow thing where I'm looking at the index I'm currently
on with this box, it's actually just the coin we're subtracting initially.
Just wanted to point that out.
So we would normally cycle through the rest of these, but since we're asking for change for two, we
don't really want to try any other coins because like we said, why would we use if we're trying to
find the minimum number of coins for to change needed?
We're not going to use a coin that's bigger than the amount of change that we're trying to give.
So for that reason, we just moved to three.
Let's start out and then left most again, so let's look at one.
So three minus one is two.
Well, how do we go to that's the problem.
How what is the minimum number of coins for change to needed?
Let's go over here.
We assess that.
It's two.
So let's add our coin, our one coin to two.
That gives us three coins.
Three is less than 12.
So let's update this value to three.
And let's keep going on, because just like three, five and 10 are greater than three, so we wouldn't
use those coins so we can move on to the next problem.
Four minus one is three.
So let's look at what we have stored for three.
Well, it says that three coins had the minimum.
So we do three plus our current coin that we're trying out or that we already gave.
You can think of it that way.
Like, I handed someone.
One, Penny, when they were asking for for change and now the only problem I need to solve is how do
I give them change for three, I still need to give in three changed and that's why I went over here
to the three to find out that answer.
And then I basically added the one coin to it so I could go update this.
And that's what we're going to do for is less than 12.
So we're going to update this to four.
Now we get to five.
So five minus one is four.
We go check out our four.
So a forest stored here for plus our current coin is five.
Five is less than 12.
So it's updated to five.
Unlike the previous problems, we're not going to be done when we were just considering one.
Now we're going to have to look at five, because five is not greater than five, it's equal to five.
We can still use five.
If we need to give five change, then I can just use a nickel.
I can just use a five coin.
So let's do that.
Five minus five is zero.
And kind of pointlessly in reality, wouldn't really need to look at this.
But now I got to ask, Well, how many coins do I need if I'm trying to make change for zero?
So you go over here and you're like, Well, I need zero coins.
So let's add the five coin that we just gave to this person, and that means that we gave them one coin.
Therefore, since one is less than five, the minimum amount of change and coin side, the minimum amount
of coins to use for a giving change for five is going to be one.
We can't really use 10 because we're only asking for change for five, so that's going to lead us to
move on.
Hopefully, you can see a pattern here.
I'm going to play out an animation for the rest of the table being filled out, but what's probably
good, you trying to see if you can fill out the table yourself first?
It'll be a really good practice exercise for understanding this problem.
So go ahead and pass a video and see if you can do that.
And then afterwards, I can walk through the rest.
OK, so let's walk through this animation.
You noticed this chess change to two up here in the nation's I'm going to refer to which coin I'm trying
to use.
I'm not going to show the rest of the arrows when I refer to the seven problems.
I'm just going to update the value to the minimum number of coins.
So we go to five because we can still use five, but it remains the same.
We go to seven, that goes to three.
We try five, it remains the same.
We're going to move to eight next.
Eight turns to four.
That's the minimum.
I go to five.
It remains the same four using five.
Same minimum number of coins.
I go to nine.
It goes down to five.
I use five.
It remains the same.
I go to 10.
That gives me six is a minimum.
I use five that goes down to two.
So if I was to use five, 10 minus five brings me to the five.
I take this one here and I add one that basically gives me two.
And that was less so.
I updated it.
Now, at this point, though, I can actually use my 10 coin because it's not greater than 10.
So if I was to use 10, if I do 10 minus 10, that gives me zero.
If I had over two zero, I noticed that I was zero coins is the minimum for that.
So if I add the 10 coins that I just gave the dime, referring back to you as current currency, I give
someone a dime.
I don't need any other coins since I came over here zero.
So zero plus one is one.
And so now I would update this to a minimum of one coin because I can just give a dime for the change
for 10.
Now we move over to our final one, so it changes to two when I use Penny because Penny brings me to
10 and 10, only has one and one plus one is two.
If I go to five, that would actually be three, I believe.
But since three is greater than two, it's not less than we're not going to update it.
We're going to keep our minimum.
And then I can use 10 and 10 is also two, because if I subtract 10 from 11, it brings me to one and
one said the minimum was one to one plus one is two.
It's the same as when we used the one point.
OK, so this is actually our answer here.
We just look at the index that is the original number that was being asked to make change of.
And that gives us the minimum number of coins.
Of course, we finished updating the whole table, we have our final answer.
It takes a minimum number of two coins to make change for 11, which was a 10 in a one or a one and
a 10, whatever way you want to think about it.
OK, so now we have to write some code.
So I'm going to go ahead and in the video now and then I will have a separate video for the code.
And like I said, I will be going over not only how to do the minimum number of coins and solve for
that, but also show you how to keep track of the coins that were used to make that minimum number of
coins.
In addition to that, I will show the method the sorry, also the example that the greedy method failed
to do the optimal solution for so we can see how our dynamic programming solution can actually solve
for that and come up with the correct solution.
So we'll do this example that we did in this lecture, and then I will include that other examples as
well.
With that, I'll see you in the next election.