1
00:00:00,270 --> 00:00:03,840
OK, so now we're continuing from where we left off with our greedy method.

2
00:00:04,410 --> 00:00:10,410
But just like we said in the last lecture, we're going to find a better solution to our optimal change

3
00:00:10,410 --> 00:00:12,420
problem by using dynamic programming.

4
00:00:12,960 --> 00:00:14,430
So let's see how we're going to do that.

5
00:00:15,450 --> 00:00:18,690
First off, let's do a little reminder of what the problem statement is.

6
00:00:18,990 --> 00:00:25,680
So what is the minimum amount of coins needed to make change given a list of denominations in addition

7
00:00:25,680 --> 00:00:26,130
to that?

8
00:00:26,430 --> 00:00:30,720
And we're going to ask what coins are used in that minimum amount kind of like what we did in the greedy

9
00:00:30,720 --> 00:00:32,640
method in the previous lecture.

10
00:00:33,120 --> 00:00:38,790
So in this actual lecture, I'm going to focus more on just the minimum amount of coins rather than

11
00:00:38,790 --> 00:00:42,630
what coins are used to make that combination of the minimum amount of coins.

12
00:00:42,840 --> 00:00:45,150
I'm going to leave that for the code later on.

13
00:00:45,750 --> 00:00:50,340
I'm also going to be going over an example that is a little bit more simplified.

14
00:00:51,060 --> 00:00:57,450
So it's not going to be exactly kind of the example that made our greedy method fail.

15
00:00:58,320 --> 00:01:04,470
So but I will include that example when I do the code so we can see how it actually works with dynamic

16
00:01:04,470 --> 00:01:07,200
programming, unlike the greedy method where it didn't work.

17
00:01:07,800 --> 00:01:13,140
But just for simplicity, I've kind of made it a somewhat trivial example to explain this, so I just

18
00:01:13,140 --> 00:01:14,880
want to put that out as a disclaimer there.

19
00:01:16,500 --> 00:01:22,320
So let's look back at dynamic programming strategies that we went over, so we have a top down method,

20
00:01:22,350 --> 00:01:28,050
which is memorization, that's kind of what we use for the Fibonacci and then we have bottom up, which

21
00:01:28,050 --> 00:01:29,400
we call a tabulation.

22
00:01:30,300 --> 00:01:36,750
So in the first example of Fibonacci, that top down solution, if you remember it had a recursive tree

23
00:01:36,750 --> 00:01:42,000
and we kind of eliminated the redundant recursive calls there where we were solving the same problem

24
00:01:42,000 --> 00:01:42,750
over and over again.

25
00:01:43,350 --> 00:01:48,960
This time we're using a bottom up solution, actually, so we're going to solve this coin optimization

26
00:01:48,960 --> 00:01:50,610
problem with a bottom up solution.

27
00:01:51,180 --> 00:01:56,160
Either way, if that you choose to solve the problem, dynamic programming involves solving all the

28
00:01:56,160 --> 00:02:01,890
sub problems of the initial problem and then using those solutions to the problems to arrive at a final

29
00:02:01,890 --> 00:02:02,340
answer.

30
00:02:03,150 --> 00:02:08,280
So what we're going to do is build a table which you can think of as a vector or an array.

31
00:02:08,610 --> 00:02:13,050
I'm just going to refer to it as the container most of the time, because I'm not sure exactly what

32
00:02:13,080 --> 00:02:15,420
type of container you want to use when you do the code.

33
00:02:16,290 --> 00:02:22,530
So we're going to store the answers to our previous problems in there, and we'll use the stored values

34
00:02:22,530 --> 00:02:27,300
that are the answers to those problems, so problems to compute the next spots in the table.

35
00:02:29,130 --> 00:02:31,800
So let's take a closer look at what we mean by sub problems.

36
00:02:31,810 --> 00:02:35,460
So at this point when I say some problems, you're probably thinking of recursion.

37
00:02:35,880 --> 00:02:42,390
But we can also represent sub problems in dynamic programming without recursion, i.e. using loops with

38
00:02:42,390 --> 00:02:45,300
tabulation, which is what we're going to do for this lecture.

39
00:02:46,110 --> 00:02:51,210
So a key point in solving dynamic programming problems from scratch, like when you get a word problem

40
00:02:51,210 --> 00:02:55,650
and you have to turn it into code and figure out how to solve it, you should actually just focus your

41
00:02:55,650 --> 00:03:00,900
thoughts on the idea of sub problems helping you with your final answer.

42
00:03:01,470 --> 00:03:07,710
Don't focus so much immediately right off the bat on whether you're going to use tabulation or memorization.

43
00:03:08,100 --> 00:03:13,370
Just try and think of Is this problem solvable with dynamic programming?

44
00:03:13,380 --> 00:03:16,530
Does it make sense for me to use dynamic programming?

45
00:03:17,250 --> 00:03:20,220
And if it makes sense, that means the problem.

46
00:03:20,220 --> 00:03:25,760
The problem can probably be broken into sub problems where you could use those answers to the set of

47
00:03:25,770 --> 00:03:28,090
problems to come up with a final solution.

48
00:03:28,110 --> 00:03:32,100
So that is what you should think about some problem answers to come up with a final solution.

49
00:03:32,550 --> 00:03:37,080
That's what you should think about when you're trying to design your strategy before you think about

50
00:03:37,080 --> 00:03:38,490
the nitty gritty details.

51
00:03:40,200 --> 00:03:43,800
So a sub problem just to kind of redefine what that is.

52
00:03:43,980 --> 00:03:45,480
It's when we ask a question.

53
00:03:45,840 --> 00:03:49,830
But to find the answer to that question, we also need to ask some other questions.

54
00:03:49,840 --> 00:03:55,470
So it's a lot like what we do with recursion, where we start off with an initial kind of input path

55
00:03:55,470 --> 00:03:55,800
to it.

56
00:03:56,040 --> 00:04:01,290
And then we keep doing recursive calls where we like half the input or minus one just to arrive at a

57
00:04:01,290 --> 00:04:06,330
base case that will help us answer all of those questions that we set aside with the recursive calls.

58
00:04:07,380 --> 00:04:12,540
So same type of thing, just not using recursion in this example for this lecture.

59
00:04:13,620 --> 00:04:16,950
So let's look at a visual way of kind of explaining this.

60
00:04:16,950 --> 00:04:23,940
This time I'm using an example of our coins are change needed coin optimization problem.

61
00:04:24,570 --> 00:04:26,310
So I have the denominations here.

62
00:04:26,340 --> 00:04:30,090
I have a one coin, a five coin and a 10 coin, respectively.

63
00:04:30,090 --> 00:04:33,180
If you're using US currency, a penny, a nickel and a dime.

64
00:04:34,290 --> 00:04:36,180
And then the change needed is 11.

65
00:04:37,130 --> 00:04:39,800
So I have like this tree structure here.

66
00:04:40,190 --> 00:04:46,820
You don't need to think of it as like a literal like code type of thing with that recursive tree.

67
00:04:47,150 --> 00:04:48,690
But it's kind of related to that.

68
00:04:48,710 --> 00:04:53,210
I'm just using it to explain our sub problem kind of thing we were talking about.

69
00:04:54,140 --> 00:04:59,240
So this root node here also it might be kind of hard to see with so many colors.

70
00:04:59,250 --> 00:05:02,390
I never have any use, but this is a different color than this color.

71
00:05:02,420 --> 00:05:05,100
This is gray and this is white, but it's kind of hard to see.

72
00:05:05,120 --> 00:05:06,290
So these are different colors.

73
00:05:06,290 --> 00:05:07,430
That's what I was aiming for.

74
00:05:08,210 --> 00:05:14,450
So we start off with our change needed that can be represented by this circle or node or whatever you

75
00:05:14,450 --> 00:05:15,410
want to call it up here.

76
00:05:15,420 --> 00:05:17,390
It's like a root node for the tree.

77
00:05:17,780 --> 00:05:20,570
This is our original problem we're trying to solve.

78
00:05:21,590 --> 00:05:29,420
From that point, we can use any one of these coins because 11 is greater than the value of each one

79
00:05:29,420 --> 00:05:30,380
of these coins.

80
00:05:30,770 --> 00:05:36,110
So we could essentially subtract one of these and say that, Hey, I'm going to make my first part of

81
00:05:36,110 --> 00:05:36,830
making change.

82
00:05:36,830 --> 00:05:39,190
I'm going to choose a coin and I can choose any one of these.

83
00:05:39,200 --> 00:05:41,930
So this is me using one coin.

84
00:05:42,530 --> 00:05:47,810
This is me using, Oh, sorry, I only get the fact this is me using a five coin.

85
00:05:47,810 --> 00:05:49,310
This is me using a 10 coin.

86
00:05:51,640 --> 00:05:58,650
So, for example, if I take an 11 and then I use one, then that means that I have 10 right here.

87
00:05:58,660 --> 00:06:00,730
So this is like another sub problem.

88
00:06:01,210 --> 00:06:09,010
If I use one, then this node right here is essentially now me asking, OK, how do I make change for

89
00:06:09,010 --> 00:06:09,910
10 now?

90
00:06:11,070 --> 00:06:18,750
Since 10 is not basically since none of these coins in here are greater than 10, it allows us to use

91
00:06:18,750 --> 00:06:20,650
all three of them from this point.

92
00:06:21,480 --> 00:06:24,510
So you can choose any one of them is what I mean.

93
00:06:25,500 --> 00:06:30,690
So you could use one and that would bring you from 10 to nine.

94
00:06:31,260 --> 00:06:38,880
And you can use five, which would bring you from 10 to five and then you can use 10, which would bring

95
00:06:38,880 --> 00:06:40,380
you from 10 to zero.

96
00:06:41,580 --> 00:06:43,440
Let's take a look at this branch over here.

97
00:06:44,040 --> 00:06:54,780
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

98
00:06:54,780 --> 00:06:56,190
use five or 10, right?

99
00:06:56,430 --> 00:07:02,560
If I'm at this node here, I'm essentially asking, how do I make change for one?

100
00:07:02,580 --> 00:07:08,190
I just used a 10 that brought me down to only needing to find change for one.

101
00:07:08,730 --> 00:07:09,870
So how do I change change?

102
00:07:09,870 --> 00:07:15,540
For one, we only have one option because you're not going to use a five coin when you're just wanting

103
00:07:15,540 --> 00:07:15,840
change.

104
00:07:15,840 --> 00:07:18,390
For one, neither are you going to use a 10 coin that's too big.

105
00:07:19,800 --> 00:07:21,000
So let's look at what these mean.

106
00:07:21,000 --> 00:07:22,200
There's some colors here.

107
00:07:23,200 --> 00:07:25,420
I said I was looking to solve.

108
00:07:25,570 --> 00:07:29,140
How do I make the minimum change for one here?

109
00:07:30,430 --> 00:07:31,360
And it's orange.

110
00:07:31,600 --> 00:07:33,070
This is also orange.

111
00:07:33,250 --> 00:07:35,770
And that's because it's the same sub problem.

112
00:07:36,310 --> 00:07:43,780
The colors that I put here correspond to the same sub problem question we're asking about how do we

113
00:07:43,780 --> 00:07:46,780
solve for a specific change needed?

114
00:07:47,380 --> 00:07:51,790
So this is how do we solve for the minimum change for one in orange?

115
00:07:51,790 --> 00:07:55,790
And so is this 10 minus five if we use a five?

116
00:07:55,810 --> 00:07:56,140
Sorry.

117
00:07:56,140 --> 00:08:01,210
11 my bed 11 minus five is six six.

118
00:08:01,210 --> 00:08:02,860
Minus five is one.

119
00:08:03,370 --> 00:08:05,230
It's why we were having this same.

120
00:08:05,710 --> 00:08:08,680
How do I make the minimum change for one here, just like here?

121
00:08:09,340 --> 00:08:12,160
Same with this blue that I already pointed out was six.

122
00:08:12,880 --> 00:08:15,100
It's just like this dark blue here.

123
00:08:15,100 --> 00:08:19,090
And then you have these light blues as well and this red.

124
00:08:19,900 --> 00:08:22,300
So you notice that we have two oranges.

125
00:08:22,690 --> 00:08:25,600
We have two of these light blues and we have two of these reds.

126
00:08:25,600 --> 00:08:32,470
So we're essentially having to solve the same problems multiple times in this tree.

127
00:08:33,130 --> 00:08:39,970
So that's kind of like what we ended up having when we were trying to do the dynamic programming solution

128
00:08:39,970 --> 00:08:41,080
of the Fibonacci thing.

129
00:08:41,350 --> 00:08:46,630
We're trying to get rid of having to redundantly calculate the same sub problems over and over.

130
00:08:46,990 --> 00:08:50,190
I haven't even drawn out this whole tree yet.

131
00:08:50,200 --> 00:08:56,110
You notice that if we were to explore all of the options to get all the way down from 11 to zero, I'd

132
00:08:56,110 --> 00:08:58,480
need to write some more branches in this tree.

133
00:08:58,930 --> 00:09:01,840
And even so, I haven't done all of the.

134
00:09:02,680 --> 00:09:08,170
Even so, with me not having filled out the whole tree, you can already see some repeated calculations.

135
00:09:09,280 --> 00:09:12,430
So that brings us down to this table here.

136
00:09:12,460 --> 00:09:15,430
You notice that it also has a lot of colors here.

137
00:09:17,120 --> 00:09:23,840
I said this Orange was us asking the question for a sub problem, how do we find the minimum change

138
00:09:23,840 --> 00:09:24,380
for one?

139
00:09:24,970 --> 00:09:30,920
Well, you notice that I also have an orange block right here inside of this table.

140
00:09:31,250 --> 00:09:35,690
And I said, how do you solve the minimum change for one?

141
00:09:35,990 --> 00:09:37,490
And we see a one right here.

142
00:09:38,870 --> 00:09:45,560
So like you may have already figured out these colors in this tree with a specific problem attached

143
00:09:45,560 --> 00:09:51,200
to them, correspond with the indices in the colors in this table, except that you notice in the table

144
00:09:51,560 --> 00:09:53,210
there's no repetitions.

145
00:09:53,780 --> 00:09:55,370
They're all different colors.

146
00:09:57,220 --> 00:10:04,570
And that's because every single spot in this table represents its own unique sub problem.

147
00:10:04,960 --> 00:10:07,220
How do I find the change for zero?

148
00:10:07,240 --> 00:10:10,960
How do I find the change for one, how do I find the change for two?

149
00:10:10,960 --> 00:10:12,930
And we're talking about minimum change each time.

150
00:10:14,170 --> 00:10:20,770
So you can already kind of see that this strategy that you're going to use with the table is going to

151
00:10:20,980 --> 00:10:24,310
eliminate a lot of these redundant calculations.

152
00:10:24,880 --> 00:10:27,040
So let's move on and explore this further.

153
00:10:29,050 --> 00:10:36,490
So one thing that we know is that the minimum number of coins for zero change needed is to zero coins.

154
00:10:36,940 --> 00:10:41,200
If somebody asks you, Hey, can you make change for nothing?

155
00:10:41,620 --> 00:10:44,280
And like, OK, well, that's nothing.

156
00:10:44,290 --> 00:10:47,110
I don't need to give you any coins because you don't need any change.

157
00:10:47,530 --> 00:10:49,090
Zero means zero.

158
00:10:49,930 --> 00:10:53,890
So that's something that we know and we can kind of use that as a base case.

159
00:10:54,340 --> 00:10:58,990
I don't mean base case like recursion because we're not really using recursion, but it gives us a point

160
00:10:58,990 --> 00:11:02,800
to build off of so we can solve the rest of our sub problems.

161
00:11:03,130 --> 00:11:04,930
So keep that in mind as we go on.

162
00:11:06,360 --> 00:11:12,240
Like I said, each index in this table represents an amount of change that is needed a sub problem.

163
00:11:15,230 --> 00:11:20,960
So, for example, the purple, the purple at Index seven means that it stores the minimum number of

164
00:11:20,960 --> 00:11:24,320
coins needed to make change for the amount.

165
00:11:24,560 --> 00:11:25,190
Seven.

166
00:11:26,240 --> 00:11:32,240
So we're not only just solving how to make change, we are solving and storing the minimum amount of

167
00:11:32,240 --> 00:11:35,600
coins for this problem at this location here.

168
00:11:37,090 --> 00:11:39,430
And that's the same for each one of these locations.

169
00:11:42,350 --> 00:11:48,620
So the final position in the container is Index 11, which happens to be the original change we needed.

170
00:11:49,670 --> 00:11:55,160
So if you might have already figured out putting two and two together, 11 is actually going to be the

171
00:11:55,160 --> 00:12:02,900
position that holds our final answer because this is same store, the minimum amount of points needed

172
00:12:02,900 --> 00:12:08,030
to make change for 11 right here, which is what we were originally asking in our problem statement.

173
00:12:11,060 --> 00:12:16,670
So unlike the greedy method, rather than immediately choosing the biggest coin and continuing on,

174
00:12:17,000 --> 00:12:21,470
we want to subtract each one of the denominations from our current change needed.

175
00:12:21,980 --> 00:12:27,290
By doing this, we will get a result amount that will be one of our indices on the table.

176
00:12:28,040 --> 00:12:33,320
We can then find the minimum number of coins stored at that index and check to see if we were to add

177
00:12:33,320 --> 00:12:35,000
one more coin to that.

178
00:12:35,360 --> 00:12:37,040
Would it be a better result?

179
00:12:37,340 --> 00:12:37,850
And why?

180
00:12:37,850 --> 00:12:43,160
When I say better result, I mean less than what's already stored at some specific spot.

181
00:12:45,700 --> 00:12:53,470
So basically, we need to cycle through each change needed position zero one to three in our container

182
00:12:53,650 --> 00:13:01,210
and try subtracting each one of our coin denominations one, five and 10 from that change needed amount,

183
00:13:01,570 --> 00:13:04,770
but only if it's less than the change needed amount, of course.

184
00:13:04,780 --> 00:13:08,630
For example, if we have this to here, how do we make change for two?

185
00:13:08,650 --> 00:13:13,870
Well, we're not going to try and give a nickel or a dime because that is greater than the change we're

186
00:13:13,870 --> 00:13:14,770
trying to give back.

187
00:13:15,310 --> 00:13:19,180
So that's what I mean by only if it's less than the change needed amount.

188
00:13:21,250 --> 00:13:22,480
So that's kind of where wordy.

189
00:13:22,510 --> 00:13:25,840
Let's break it down into smaller pieces and use an example.

190
00:13:27,370 --> 00:13:32,770
We're going to start out with zero in the zero change needed position because like we already stated,

191
00:13:33,010 --> 00:13:39,670
if you have no change needed to give, you don't really need to give any coins zero coins.

192
00:13:44,680 --> 00:13:45,120
OK.

193
00:13:46,180 --> 00:13:52,900
So each time we do one of these subtractions, the result of the subtraction will be an amount of change

194
00:13:52,900 --> 00:13:55,420
needed that's already computed in our table.

195
00:13:55,810 --> 00:13:58,690
And therein lies the efficiency of this solution.

196
00:13:59,380 --> 00:14:03,160
We already have computed the sub problems.

197
00:14:03,940 --> 00:14:10,810
You notice it's not skipping any numbers here, so we've computed every possible asking for change amount

198
00:14:11,110 --> 00:14:14,980
up to up to the current one that we will be considering.

199
00:14:16,580 --> 00:14:22,040
So that gives us the ability to look it up and find the minimum amount of coins that were needed for

200
00:14:22,040 --> 00:14:24,650
that smaller amount, the smaller sub problem.

201
00:14:26,060 --> 00:14:32,540
So for example, if I want to know the minimum amount of coins needed to make change for a one change

202
00:14:32,540 --> 00:14:40,160
needed problem, I can look at my coin denominations and see that the only coin I can really use is

203
00:14:40,160 --> 00:14:40,790
a one.

204
00:14:43,960 --> 00:14:47,410
So I'll do one minus one equals zero.

205
00:14:47,680 --> 00:14:53,050
And that makes me want to look at container zero to see what that sub problem was.

206
00:14:53,290 --> 00:14:55,900
I notice that it says zero coins there.

207
00:14:58,600 --> 00:15:05,740
Since I found zero there, and I'm using a one coin to try and make change, I'm going to do zero plus

208
00:15:05,740 --> 00:15:06,100
one.

209
00:15:06,320 --> 00:15:12,820
And remember, this plus one is not because the coin value is one, the plus one is because I'm using

210
00:15:12,970 --> 00:15:14,020
one coin.

211
00:15:14,740 --> 00:15:20,710
So as my coins needed, I'm going to see as the smallest amount of coin so far for my one change needed

212
00:15:20,710 --> 00:15:21,100
problem.

213
00:15:22,150 --> 00:15:25,510
So I want to compare it to what is currently at one.

214
00:15:25,520 --> 00:15:29,260
But wait, there is nothing at one, huh?

215
00:15:29,290 --> 00:15:34,120
So before we go about this, we're going to have to fill these with some initial values.

216
00:15:35,480 --> 00:15:40,160
We need to fill our table with some initial values that we can compare against so we can update what

217
00:15:40,160 --> 00:15:44,210
coin we're going to choose that will result in the smallest amount of coins.

218
00:15:44,570 --> 00:15:45,980
But what shall we put here?

219
00:15:47,240 --> 00:15:54,110
A safe idea is to put a value that is larger than the total possible number of coins we could have for

220
00:15:54,110 --> 00:15:56,360
our original change needed problem.

221
00:15:57,530 --> 00:16:03,620
So that means, like us using 11 pennies for a change 11.

222
00:16:05,130 --> 00:16:09,900
So because of this, we can store any number that is 12 or above.

223
00:16:10,350 --> 00:16:11,760
So I'm just going to put 12.

224
00:16:12,150 --> 00:16:16,070
You can think of it the same way as us needing to put a number here.

225
00:16:16,080 --> 00:16:22,890
That is one more than the size of the container because you notice we've put a solve change problem

226
00:16:22,890 --> 00:16:27,150
for each number all the way up to the original number we were asking about.

227
00:16:28,470 --> 00:16:33,030
Because of that, we need to put something slightly bigger than that, so it gives us the ability to

228
00:16:33,030 --> 00:16:38,400
keep updating and a minimum the first time we update it, we need it to be bigger than any possible

229
00:16:38,400 --> 00:16:39,930
thing we're going to compare against.

230
00:16:40,170 --> 00:16:41,760
So that's why we're going to use 12.

231
00:16:42,510 --> 00:16:44,460
So I'm filling all of these with 12.

232
00:16:46,950 --> 00:16:48,900
So let's check our previous problems.

233
00:16:48,900 --> 00:16:55,410
So if we do zero, which we took from here for our sub problem this year and we add, we add one coin

234
00:16:55,410 --> 00:16:57,360
to that, it equals one.

235
00:16:57,810 --> 00:17:01,950
Then we take a look back at here and we say is one less than 12.

236
00:17:02,040 --> 00:17:02,980
Yes, it is.

237
00:17:03,000 --> 00:17:06,030
So let's update container of one to one.

238
00:17:08,920 --> 00:17:09,940
So that's what we do.

239
00:17:11,700 --> 00:17:17,610
So we're going to do this for every position in the table until we update the whole table with the minimum

240
00:17:17,610 --> 00:17:21,750
number of coins needed for each one of these change needed positions.

241
00:17:21,870 --> 00:17:27,580
Each one of these chains needed some problems since the final position is changing for 11.

242
00:17:27,600 --> 00:17:31,800
Of course, the value there will be our answer, so let's go ahead and step through this process.

243
00:17:33,130 --> 00:17:34,300
Let's go to two now.

244
00:17:35,110 --> 00:17:41,710
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.

245
00:17:41,950 --> 00:17:43,890
Well, I'm going to use one.

246
00:17:43,900 --> 00:17:45,160
I'm going to use a penny.

247
00:17:45,170 --> 00:17:49,240
So if I refer to it as U.S. currency, two minus one is one.

248
00:17:49,570 --> 00:17:56,770
So now I'm basically asking the question How do I find the minimum number of coins for one change needed?

249
00:17:57,070 --> 00:18:00,430
Well, let's go to the one change needed position in the table.

250
00:18:01,510 --> 00:18:02,590
What does that say?

251
00:18:03,160 --> 00:18:07,780
Well, it says that there's one is the minimum number of coins.

252
00:18:08,080 --> 00:18:10,420
And you notice that this is an orange block here.

253
00:18:10,420 --> 00:18:14,080
So I've denoted the thing that I'm bringing up here in orange.

254
00:18:14,860 --> 00:18:19,610
So it says that the minimum number of coins to make change for one is one.

255
00:18:19,630 --> 00:18:24,710
So I use that and then I'm also adding the one coin that I'm using right now.

256
00:18:24,730 --> 00:18:29,950
Remember, it's not about the value, it's about the fact that I'm adding one coin.

257
00:18:29,950 --> 00:18:31,270
That's what this gray one is.

258
00:18:31,660 --> 00:18:32,980
One plus one is two.

259
00:18:33,250 --> 00:18:37,840
Now let's go back and see if that's less than this right here, which is stored here.

260
00:18:38,320 --> 00:18:40,280
It is two is less than 12.

261
00:18:40,300 --> 00:18:42,270
So let's change this value to two.

262
00:18:44,160 --> 00:18:49,230
So another thing I want to point out is that I kind of ran out of colors and I'm using red to denote

263
00:18:49,410 --> 00:18:53,520
the current denomination that I am on as we cycle through these.

264
00:18:54,240 --> 00:18:56,550
It has nothing to do with the red in this box here.

265
00:18:56,550 --> 00:19:01,770
So I just wanted to make sure that you're not associating this red with this box here, even though

266
00:19:01,770 --> 00:19:02,800
this is orange right here.

267
00:19:02,820 --> 00:19:09,840
Do not associate the red in this original down arrow thing where I'm looking at the index I'm currently

268
00:19:09,840 --> 00:19:14,880
on with this box, it's actually just the coin we're subtracting initially.

269
00:19:16,500 --> 00:19:17,400
Just wanted to point that out.

270
00:19:19,490 --> 00:19:26,960
So we would normally cycle through the rest of these, but since we're asking for change for two, we

271
00:19:26,960 --> 00:19:31,700
don't really want to try any other coins because like we said, why would we use if we're trying to

272
00:19:31,700 --> 00:19:35,360
find the minimum number of coins for to change needed?

273
00:19:35,630 --> 00:19:39,650
We're not going to use a coin that's bigger than the amount of change that we're trying to give.

274
00:19:41,360 --> 00:19:43,160
So for that reason, we just moved to three.

275
00:19:44,410 --> 00:19:47,560
Let's start out and then left most again, so let's look at one.

276
00:19:48,100 --> 00:19:50,990
So three minus one is two.

277
00:19:51,010 --> 00:19:53,020
Well, how do we go to that's the problem.

278
00:19:53,020 --> 00:19:56,500
How what is the minimum number of coins for change to needed?

279
00:19:57,970 --> 00:19:58,970
Let's go over here.

280
00:19:58,990 --> 00:19:59,710
We assess that.

281
00:19:59,710 --> 00:20:00,230
It's two.

282
00:20:00,250 --> 00:20:03,370
So let's add our coin, our one coin to two.

283
00:20:03,370 --> 00:20:04,900
That gives us three coins.

284
00:20:06,610 --> 00:20:07,970
Three is less than 12.

285
00:20:07,990 --> 00:20:10,030
So let's update this value to three.

286
00:20:12,270 --> 00:20:16,980
And let's keep going on, because just like three, five and 10 are greater than three, so we wouldn't

287
00:20:16,980 --> 00:20:20,550
use those coins so we can move on to the next problem.

288
00:20:22,110 --> 00:20:23,960
Four minus one is three.

289
00:20:24,940 --> 00:20:27,880
So let's look at what we have stored for three.

290
00:20:28,660 --> 00:20:31,210
Well, it says that three coins had the minimum.

291
00:20:32,020 --> 00:20:36,850
So we do three plus our current coin that we're trying out or that we already gave.

292
00:20:36,850 --> 00:20:37,850
You can think of it that way.

293
00:20:37,870 --> 00:20:39,550
Like, I handed someone.

294
00:20:40,680 --> 00:20:50,010
One, Penny, when they were asking for for change and now the only problem I need to solve is how do

295
00:20:50,010 --> 00:20:54,780
I give them change for three, I still need to give in three changed and that's why I went over here

296
00:20:54,780 --> 00:20:56,820
to the three to find out that answer.

297
00:20:57,300 --> 00:21:01,770
And then I basically added the one coin to it so I could go update this.

298
00:21:02,880 --> 00:21:05,430
And that's what we're going to do for is less than 12.

299
00:21:05,700 --> 00:21:07,230
So we're going to update this to four.

300
00:21:09,030 --> 00:21:10,200
Now we get to five.

301
00:21:10,470 --> 00:21:12,930
So five minus one is four.

302
00:21:13,140 --> 00:21:14,670
We go check out our four.

303
00:21:16,770 --> 00:21:21,420
So a forest stored here for plus our current coin is five.

304
00:21:23,610 --> 00:21:25,020
Five is less than 12.

305
00:21:25,530 --> 00:21:26,940
So it's updated to five.

306
00:21:28,020 --> 00:21:33,520
Unlike the previous problems, we're not going to be done when we were just considering one.

307
00:21:33,540 --> 00:21:39,630
Now we're going to have to look at five, because five is not greater than five, it's equal to five.

308
00:21:39,780 --> 00:21:41,760
We can still use five.

309
00:21:41,760 --> 00:21:46,140
If we need to give five change, then I can just use a nickel.

310
00:21:46,140 --> 00:21:48,210
I can just use a five coin.

311
00:21:49,770 --> 00:21:50,760
So let's do that.

312
00:21:51,210 --> 00:21:53,220
Five minus five is zero.

313
00:21:53,850 --> 00:21:58,260
And kind of pointlessly in reality, wouldn't really need to look at this.

314
00:21:58,260 --> 00:22:04,560
But now I got to ask, Well, how many coins do I need if I'm trying to make change for zero?

315
00:22:05,220 --> 00:22:08,130
So you go over here and you're like, Well, I need zero coins.

316
00:22:08,130 --> 00:22:15,930
So let's add the five coin that we just gave to this person, and that means that we gave them one coin.

317
00:22:17,340 --> 00:22:24,120
Therefore, since one is less than five, the minimum amount of change and coin side, the minimum amount

318
00:22:24,120 --> 00:22:28,680
of coins to use for a giving change for five is going to be one.

319
00:22:29,820 --> 00:22:35,310
We can't really use 10 because we're only asking for change for five, so that's going to lead us to

320
00:22:35,310 --> 00:22:35,820
move on.

321
00:22:37,020 --> 00:22:38,760
Hopefully, you can see a pattern here.

322
00:22:38,790 --> 00:22:44,430
I'm going to play out an animation for the rest of the table being filled out, but what's probably

323
00:22:44,430 --> 00:22:48,210
good, you trying to see if you can fill out the table yourself first?

324
00:22:48,510 --> 00:22:52,170
It'll be a really good practice exercise for understanding this problem.

325
00:22:52,530 --> 00:22:55,350
So go ahead and pass a video and see if you can do that.

326
00:22:55,710 --> 00:22:57,750
And then afterwards, I can walk through the rest.

327
00:22:59,550 --> 00:23:01,290
OK, so let's walk through this animation.

328
00:23:01,890 --> 00:23:07,410
You noticed this chess change to two up here in the nation's I'm going to refer to which coin I'm trying

329
00:23:07,410 --> 00:23:07,950
to use.

330
00:23:08,160 --> 00:23:11,560
I'm not going to show the rest of the arrows when I refer to the seven problems.

331
00:23:11,580 --> 00:23:14,400
I'm just going to update the value to the minimum number of coins.

332
00:23:16,060 --> 00:23:19,560
So we go to five because we can still use five, but it remains the same.

333
00:23:21,350 --> 00:23:23,780
We go to seven, that goes to three.

334
00:23:24,320 --> 00:23:26,420
We try five, it remains the same.

335
00:23:27,050 --> 00:23:28,460
We're going to move to eight next.

336
00:23:29,120 --> 00:23:30,530
Eight turns to four.

337
00:23:30,900 --> 00:23:31,810
That's the minimum.

338
00:23:31,820 --> 00:23:32,760
I go to five.

339
00:23:32,780 --> 00:23:35,090
It remains the same four using five.

340
00:23:35,270 --> 00:23:36,710
Same minimum number of coins.

341
00:23:37,370 --> 00:23:38,420
I go to nine.

342
00:23:38,720 --> 00:23:39,720
It goes down to five.

343
00:23:39,740 --> 00:23:40,700
I use five.

344
00:23:40,710 --> 00:23:41,900
It remains the same.

345
00:23:43,160 --> 00:23:44,240
I go to 10.

346
00:23:45,430 --> 00:23:47,380
That gives me six is a minimum.

347
00:23:47,620 --> 00:23:51,430
I use five that goes down to two.

348
00:23:52,240 --> 00:23:57,610
So if I was to use five, 10 minus five brings me to the five.

349
00:23:57,970 --> 00:24:02,230
I take this one here and I add one that basically gives me two.

350
00:24:02,410 --> 00:24:03,310
And that was less so.

351
00:24:03,310 --> 00:24:03,970
I updated it.

352
00:24:04,570 --> 00:24:10,420
Now, at this point, though, I can actually use my 10 coin because it's not greater than 10.

353
00:24:11,370 --> 00:24:17,160
So if I was to use 10, if I do 10 minus 10, that gives me zero.

354
00:24:17,250 --> 00:24:24,150
If I had over two zero, I noticed that I was zero coins is the minimum for that.

355
00:24:24,450 --> 00:24:30,090
So if I add the 10 coins that I just gave the dime, referring back to you as current currency, I give

356
00:24:30,090 --> 00:24:30,810
someone a dime.

357
00:24:31,050 --> 00:24:35,220
I don't need any other coins since I came over here zero.

358
00:24:35,220 --> 00:24:36,990
So zero plus one is one.

359
00:24:37,200 --> 00:24:42,990
And so now I would update this to a minimum of one coin because I can just give a dime for the change

360
00:24:42,990 --> 00:24:43,410
for 10.

361
00:24:45,880 --> 00:24:52,810
Now we move over to our final one, so it changes to two when I use Penny because Penny brings me to

362
00:24:52,810 --> 00:24:55,530
10 and 10, only has one and one plus one is two.

363
00:24:56,680 --> 00:25:00,300
If I go to five, that would actually be three, I believe.

364
00:25:00,340 --> 00:25:04,720
But since three is greater than two, it's not less than we're not going to update it.

365
00:25:04,720 --> 00:25:05,770
We're going to keep our minimum.

366
00:25:07,180 --> 00:25:13,500
And then I can use 10 and 10 is also two, because if I subtract 10 from 11, it brings me to one and

367
00:25:13,540 --> 00:25:16,480
one said the minimum was one to one plus one is two.

368
00:25:16,810 --> 00:25:19,570
It's the same as when we used the one point.

369
00:25:21,910 --> 00:25:24,590
OK, so this is actually our answer here.

370
00:25:24,610 --> 00:25:31,150
We just look at the index that is the original number that was being asked to make change of.

371
00:25:31,510 --> 00:25:33,910
And that gives us the minimum number of coins.

372
00:25:36,470 --> 00:25:39,770
Of course, we finished updating the whole table, we have our final answer.

373
00:25:40,040 --> 00:25:45,800
It takes a minimum number of two coins to make change for 11, which was a 10 in a one or a one and

374
00:25:45,800 --> 00:25:48,290
a 10, whatever way you want to think about it.

375
00:25:49,720 --> 00:25:51,940
OK, so now we have to write some code.

376
00:25:52,630 --> 00:25:58,300
So I'm going to go ahead and in the video now and then I will have a separate video for the code.

377
00:25:58,540 --> 00:26:06,580
And like I said, I will be going over not only how to do the minimum number of coins and solve for

378
00:26:06,580 --> 00:26:12,970
that, but also show you how to keep track of the coins that were used to make that minimum number of

379
00:26:12,970 --> 00:26:13,450
coins.

380
00:26:13,870 --> 00:26:20,440
In addition to that, I will show the method the sorry, also the example that the greedy method failed

381
00:26:20,440 --> 00:26:26,920
to do the optimal solution for so we can see how our dynamic programming solution can actually solve

382
00:26:26,920 --> 00:26:29,020
for that and come up with the correct solution.

383
00:26:29,500 --> 00:26:33,910
So we'll do this example that we did in this lecture, and then I will include that other examples as

384
00:26:33,910 --> 00:26:34,180
well.

385
00:26:34,510 --> 00:26:36,070
With that, I'll see you in the next election.