1
00:00:02,110 --> 00:00:10,330
OK, so now it's time to move on to the code portion of this dynamic programming tone coin problem.

2
00:00:11,140 --> 00:00:13,450
So let's go ahead and get started.

3
00:00:13,460 --> 00:00:20,830
I basically already made a little new project here called Coin ODP, and I just have an empty main file

4
00:00:20,830 --> 00:00:23,480
with a main function kind of skeleton here.

5
00:00:24,010 --> 00:00:30,730
And I included a vector as well as, I assume, because I'm going to use a vector is my container for

6
00:00:30,730 --> 00:00:31,360
my table.

7
00:00:32,740 --> 00:00:34,410
So I'll get right to it.

8
00:00:34,420 --> 00:00:38,200
I'm on foot using namespace for this.

9
00:00:38,440 --> 00:00:39,100
And then.

10
00:00:40,370 --> 00:00:46,970
In addition to the function that's going to be like men coins function that does the entire algorithm.

11
00:00:47,450 --> 00:00:53,450
I'm also going to make a helper because I do know from our last lecture that we had a part of the algorithm

12
00:00:53,870 --> 00:00:57,680
where we kind of needed to update the minimum value.

13
00:00:57,680 --> 00:01:01,010
So we had to make a comparison to see which one was bigger, right?

14
00:01:01,580 --> 00:01:08,030
We basically, if we came up with the smaller minimum number of coins, then we would replace what was

15
00:01:08,030 --> 00:01:12,410
in a current position stored at whatever was stored in the current position.

16
00:01:13,130 --> 00:01:14,390
With that new minimum value.

17
00:01:14,990 --> 00:01:17,110
So that means I'm going to want like a min function.

18
00:01:17,120 --> 00:01:21,320
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

19
00:01:21,340 --> 00:01:22,340
return an integer.

20
00:01:22,400 --> 00:01:23,740
I'm just going to call it man do.

21
00:01:23,810 --> 00:01:26,060
And A and and B.

22
00:01:27,860 --> 00:01:31,100
So of course, we're going to have our main coins function.

23
00:01:31,610 --> 00:01:38,120
You could make it return just an integer or something, but I'm actually just going to make it void

24
00:01:38,540 --> 00:01:43,460
and going to print my minimum number of coins inside of the function.

25
00:01:44,240 --> 00:01:53,330
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

26
00:01:53,330 --> 00:01:56,360
to make an end, which is the original change needed.

27
00:01:58,750 --> 00:01:59,470
Cool.

28
00:01:59,550 --> 00:02:02,230
So let's go ahead and implement these functions.

29
00:02:02,240 --> 00:02:03,420
The men will be easy.

30
00:02:03,440 --> 00:02:12,890
I'm actually just going to do it with a ternary, so I'm going to the return and basically a less than

31
00:02:12,890 --> 00:02:17,660
B than a otherwise b.

32
00:02:20,070 --> 00:02:22,350
So that's pretty simple there.

33
00:02:23,130 --> 00:02:25,800
All it does is find the minimum of the two in return, the minimum.

34
00:02:27,690 --> 00:02:40,320
So let's see now I'm going to do mine in coins and I will do this vector and coins and change needed.

35
00:02:42,660 --> 00:02:48,570
And hopefully this is big enough for us to see an increase that size a little bit.

36
00:02:50,700 --> 00:02:53,210
So what's the kind of the first thing that we need?

37
00:02:53,220 --> 00:02:55,050
We should probably make our table right?

38
00:02:55,320 --> 00:02:58,350
Think back to the lecture and think of how our table started out.

39
00:02:58,350 --> 00:03:03,300
It basically had a zero in the 0th position for like that serious problem.

40
00:03:04,650 --> 00:03:07,320
And then the rest were 12th in our example.

41
00:03:07,740 --> 00:03:14,130
And the rest were 12 because it was one more than what the change needed value was.

42
00:03:14,550 --> 00:03:17,580
So with that in mind, let's make our initial table here.

43
00:03:17,640 --> 00:03:19,190
So I'm going to call it table.

44
00:03:19,670 --> 00:03:25,110
I'm going to say change needed is going to be the size plus one, actually.

45
00:03:25,110 --> 00:03:27,120
So change needed plus one will be the size.

46
00:03:27,570 --> 00:03:32,340
And then I'm also going to put change needed plus one as the values that fill it.

47
00:03:33,660 --> 00:03:41,740
And since we don't want that first initial value, the zeroth position to be like, for example, well,

48
00:03:41,790 --> 00:03:45,050
if our changing was 11, we're going to go ahead and update that right away.

49
00:03:45,060 --> 00:03:48,150
So I'm just going to say table of zero is zero.

50
00:03:49,080 --> 00:03:50,520
So hopefully this makes sense.

51
00:03:50,580 --> 00:03:59,670
This is just saying that the size of the table is going to be one more than change needed.

52
00:03:59,820 --> 00:04:02,460
So think of this, for example, if you have change needed.

53
00:04:02,460 --> 00:04:09,390
11, we had an 11th position in the table and if you're starting at zero, that means, you know, the

54
00:04:09,390 --> 00:04:10,770
size is going to be 12.

55
00:04:10,800 --> 00:04:16,650
That's why we're doing change needed +1 for the size and then the values that we're filling this with

56
00:04:16,650 --> 00:04:21,330
is just going to be like if you're thinking of the example, it would be 12 as well, one more than

57
00:04:21,330 --> 00:04:21,810
11.

58
00:04:22,020 --> 00:04:25,650
But of course, we're just adding into this variable amount change needed.

59
00:04:27,200 --> 00:04:30,890
And then our zero position is zero, of course.

60
00:04:31,460 --> 00:04:32,900
So let's think about how to start.

61
00:04:32,900 --> 00:04:35,870
The algorithm was the first thing we kind of did like.

62
00:04:36,470 --> 00:04:43,540
The main overarching process is just looping over all of these sub problems.

63
00:04:43,550 --> 00:04:50,510
And so the sub problems are basically the positions of the table going from zero all the way up to whatever

64
00:04:50,510 --> 00:04:51,610
change needed is.

65
00:04:51,620 --> 00:04:55,610
So I'm going to make this kind of range based loop here.

66
00:04:55,790 --> 00:05:02,420
So four and I go zero, I is less than or equal to change needed because we're going to have a position

67
00:05:02,420 --> 00:05:03,260
for change needed.

68
00:05:03,920 --> 00:05:07,880
Remember, if the change needed is 11, we have an 11th position.

69
00:05:08,360 --> 00:05:10,310
So that's why it's a less than or equal to.

70
00:05:10,790 --> 00:05:13,640
So I want to make this outer loop here.

71
00:05:14,000 --> 00:05:18,620
Then what were we looping over in kind of in between this?

72
00:05:18,620 --> 00:05:27,380
So if each position that we were looking at, we had to also try out each coin as long as it wasn't

73
00:05:27,380 --> 00:05:28,370
too big, right?

74
00:05:28,760 --> 00:05:30,530
So let's loop over our coins.

75
00:05:30,530 --> 00:05:33,600
So I'm actually going to see and do a looping over the items for this.

76
00:05:33,600 --> 00:05:37,850
So I'm going to do for any coin in coins.

77
00:05:38,630 --> 00:05:42,350
You can also do like auto, but I'm just putting the right here.

78
00:05:44,280 --> 00:05:52,260
And basically, we were saying, I think I just said to that we are only going to consider a coin if

79
00:05:52,860 --> 00:05:58,540
it's not greater than the amount that we are currently looking at getting change for.

80
00:05:58,580 --> 00:06:00,060
So that is our eye, right?

81
00:06:00,930 --> 00:06:07,320
Eyes are some problems and are some problems are also like, how do we make change for blink?

82
00:06:07,650 --> 00:06:10,470
So, you know, if I three, it's how do we make change for three?

83
00:06:11,340 --> 00:06:19,620
So as long as the coin is less than or equal to so you can flip this around as long as I is greater

84
00:06:19,620 --> 00:06:26,700
than or equal to coin, then we can basically just update our tables.

85
00:06:26,700 --> 00:06:35,940
So I'm just going to say Table I equals men and think about this right here.

86
00:06:36,270 --> 00:06:41,000
So we're updating that value to the minimum right.

87
00:06:41,020 --> 00:06:42,480
But how did we do that?

88
00:06:43,260 --> 00:06:50,370
Well, what we did first was we subtracted the coin from the current sub problem that we were at right

89
00:06:50,550 --> 00:06:51,480
from the current.

90
00:06:51,570 --> 00:06:53,570
How do we make change for this?

91
00:06:53,580 --> 00:06:55,770
So how do we make change for three?

92
00:06:55,800 --> 00:06:58,920
Well, what we did was we started out with the coin one.

93
00:06:59,340 --> 00:07:01,530
We subtracted one from three.

94
00:07:03,690 --> 00:07:12,060
So and then once we got that answer, which is to then we looked at the two position in the table for

95
00:07:12,060 --> 00:07:14,400
what was stored there and added one to it, right?

96
00:07:14,790 --> 00:07:15,840
That's kind of a mouthful.

97
00:07:15,990 --> 00:07:16,650
Break it down.

98
00:07:16,650 --> 00:07:21,330
So right off the bat, we know we're trying to update where we currently are.

99
00:07:21,360 --> 00:07:25,380
So table is the value stored where we're currently at.

100
00:07:25,380 --> 00:07:28,650
We're at high and we're seeing what is stored here.

101
00:07:29,220 --> 00:07:32,240
Can we take a coin and find a better minimum?

102
00:07:32,250 --> 00:07:34,610
So one of the things we're comparing is Table II.

103
00:07:35,460 --> 00:07:44,580
The next thing is basically we take that position where we subtract that coin from I, right?

104
00:07:44,970 --> 00:07:48,540
We get what's at that position and then we add the coin.

105
00:07:48,540 --> 00:07:49,470
We're considering to it.

106
00:07:49,470 --> 00:07:50,720
We're considering a coin.

107
00:07:50,730 --> 00:07:59,040
So if I, you know, give someone a coin, then I subtract that coin from the total amount and then

108
00:07:59,040 --> 00:08:03,870
I ask myself, OK, how do I make change for this new smaller amount?

109
00:08:04,560 --> 00:08:08,520
I go, Look there in my table for that new, smaller amount.

110
00:08:08,910 --> 00:08:10,440
I get the amount from it.

111
00:08:10,830 --> 00:08:17,820
And then I say, Well, I already gave a coin to this person for the change, so I need to consider

112
00:08:17,820 --> 00:08:19,020
that coin that I gave.

113
00:08:19,020 --> 00:08:20,370
So I do the plus one.

114
00:08:20,970 --> 00:08:23,430
So just trying to connect this back to the previous lecture.

115
00:08:25,890 --> 00:08:32,130
OK, so that is getting annoying with this scroll and probably make this a little bit smaller.

116
00:08:32,160 --> 00:08:32,610
There we go.

117
00:08:36,040 --> 00:08:36,430
So.

118
00:08:38,630 --> 00:08:39,180
OK.

119
00:08:40,670 --> 00:08:42,110
OK, I got Jones down there.

120
00:08:43,800 --> 00:08:50,670
OK, so I need to put a semicolon here, and then so, yeah, that updates into our table.

121
00:08:51,180 --> 00:08:58,170
So that's kind of if you think about the previous lecture, that's kind of all we were really doing.

122
00:08:59,550 --> 00:08:59,900
Right.

123
00:09:00,080 --> 00:09:04,880
So we didn't have to do anything really else besides that, so we're kind of handling everything we

124
00:09:04,880 --> 00:09:05,510
need to hear.

125
00:09:06,490 --> 00:09:13,720
So if we fill out our table just like that, where was our final answer when we're finished filling

126
00:09:13,720 --> 00:09:14,380
out a table?

127
00:09:15,070 --> 00:09:20,080
So if I'm going to go ahead and print this out, so I say.

128
00:09:22,220 --> 00:09:25,510
Fill out and then men.

129
00:09:26,090 --> 00:09:27,510
No coins.

130
00:09:30,110 --> 00:09:33,920
What am I going to print here, so it's going to be stored in our table?

131
00:09:34,640 --> 00:09:39,680
If you remember correctly, like when we had our 11 past as the change needed.

132
00:09:40,670 --> 00:09:45,260
We actually had to look at that 11th position to get our answer right.

133
00:09:45,650 --> 00:09:46,880
So that's what we're going to do.

134
00:09:46,930 --> 00:09:53,030
We're going to print out a table of change needed because that final thing in the vector is storing

135
00:09:53,030 --> 00:09:53,600
our answer.

136
00:09:54,560 --> 00:09:57,020
And I'm just going to put an end line here.

137
00:09:58,970 --> 00:10:02,270
OK, so this is pretty much our whole function here.

138
00:10:02,270 --> 00:10:05,450
So let's go ahead and make a little example.

139
00:10:05,720 --> 00:10:08,180
I'm going to go over the two examples.

140
00:10:08,420 --> 00:10:11,420
One of them is going to be what was in the last lecture.

141
00:10:11,420 --> 00:10:16,970
So we have something like the nominations we're going to call this number one.

142
00:10:18,350 --> 00:10:22,190
It was basically one, five and 10, right?

143
00:10:23,180 --> 00:10:26,360
And we were looking for change 11.

144
00:10:26,360 --> 00:10:33,920
So I'll remember that the other one was like our greedy method, one that failed with the greedy method,

145
00:10:33,920 --> 00:10:34,240
right?

146
00:10:34,250 --> 00:10:39,200
And that's why we wanted to move over to the dynamic programming methods so we could get the real optimal

147
00:10:39,200 --> 00:10:39,710
solution.

148
00:10:39,720 --> 00:10:53,960
So that was something like we had a three, no a one and then an eight and then a nine and then like

149
00:10:53,960 --> 00:10:54,890
a 14.

150
00:10:55,010 --> 00:11:04,430
I think because we were looking for 17 and we said the greening method basically said, Oh, 17, the

151
00:11:04,430 --> 00:11:09,650
best way to do that is 14 and then one and one and one three one.

152
00:11:09,660 --> 00:11:10,520
So that was.

153
00:11:14,620 --> 00:11:19,750
You know, for coins, which was suboptimal, because if we want 17, we could have just taken these

154
00:11:19,750 --> 00:11:20,320
two here.

155
00:11:20,740 --> 00:11:28,870
So we're going to include that so we can see how our dynamic programming method now is fixing that problem

156
00:11:28,870 --> 00:11:30,160
that we had with the great method.

157
00:11:31,360 --> 00:11:37,660
So let's call our function and I'm going to start off with just passing it to number one.

158
00:11:38,290 --> 00:11:41,680
And 11, because that is what we used in the lecture.

159
00:11:42,270 --> 00:11:43,390
Let's go ahead and print this out.

160
00:11:43,510 --> 00:11:47,560
If if everything is correct, remember for change.

161
00:11:47,630 --> 00:11:48,660
11.

162
00:11:48,670 --> 00:11:50,890
We should be only having two coins.

163
00:11:50,890 --> 00:11:52,690
It would be a 10 in a one.

164
00:11:52,930 --> 00:11:53,260
Right.

165
00:11:54,190 --> 00:12:00,580
So right now, we're only solving for the actual minimum number of coins.

166
00:12:01,120 --> 00:12:11,410
Once we check our kind of test these two here, then we will go in and try and add some code that handles

167
00:12:11,620 --> 00:12:13,420
getting the actual coins that we use.

168
00:12:14,380 --> 00:12:15,220
So let's run this.

169
00:12:15,220 --> 00:12:16,780
We should be getting the two here.

170
00:12:22,150 --> 00:12:23,710
OK, so that looks good.

171
00:12:23,740 --> 00:12:25,300
M. Collins is, too.

172
00:12:26,260 --> 00:12:29,140
Let's go ahead and try the names too.

173
00:12:30,040 --> 00:12:35,040
And so this was when we were asking for 17 in the greedy method.

174
00:12:35,800 --> 00:12:38,800
It was doing 14 with three once, which is four coins.

175
00:12:38,800 --> 00:12:42,290
But really what we wanted was the eight and nine, which should be two.

176
00:12:42,310 --> 00:12:44,710
So our answer should also be two for this.

177
00:12:48,540 --> 00:12:51,000
OK, so we also get men coins, too.

178
00:12:52,470 --> 00:12:52,770
Cool.

179
00:12:52,830 --> 00:12:56,340
So let's go in and add some code here.

180
00:12:57,560 --> 00:13:02,420
For us to be able to also record the coins that were being used.

181
00:13:04,310 --> 00:13:13,850
So at first, you might have tried this on your own, and if you succeeded, you know, props to you

182
00:13:13,850 --> 00:13:15,860
for being able to figure that out.

183
00:13:16,930 --> 00:13:21,880
I said it was somewhat trivial, but it's not really that trivial to think about, it's kind of confusing.

184
00:13:22,210 --> 00:13:33,640
But what we need to think of is that recording the minimum number of coins is kind of the same as us

185
00:13:33,640 --> 00:13:36,760
recording the coins that are being used.

186
00:13:37,120 --> 00:13:44,620
We're looking at these sub problems and trying to see well for this sub problem, what was its minimum

187
00:13:44,620 --> 00:13:45,670
number of coins?

188
00:13:46,480 --> 00:13:52,300
And we kept doing that for the whole loop and the whole table that we were building.

189
00:13:53,780 --> 00:13:59,120
So we can pretty much do the same type of thing for the actual coins that were used.

190
00:13:59,900 --> 00:14:08,950
We can say, OK, well, let's see if I go to if I jump somewhere in the table to this previous problem

191
00:14:08,960 --> 00:14:09,920
has been solved.

192
00:14:10,370 --> 00:14:13,040
What were its number of coin or sorry?

193
00:14:13,040 --> 00:14:16,370
What were its specific coins that it used?

194
00:14:17,240 --> 00:14:30,050
And if I have like less coins basically then or I'm actually updating, you know, the value of coins

195
00:14:30,050 --> 00:14:31,950
like I found something that was less.

196
00:14:33,260 --> 00:14:38,960
Then I'm going to want to update, you know, so we're basically going to do the same thing.

197
00:14:38,960 --> 00:14:44,450
We're doing the same exact idea idea of how we're updating the minimum number of coins.

198
00:14:45,510 --> 00:14:52,500
To keep track in another table of the actual coins that we're using.

199
00:14:53,870 --> 00:14:56,060
So that should help us simplify the problem a little bit.

200
00:14:57,230 --> 00:15:03,500
So if we're going to need to keep track of another table, let's go ahead and make that table, so I'm

201
00:15:03,500 --> 00:15:04,910
going to make another vector here.

202
00:15:06,110 --> 00:15:13,160
But instead of making a vector, it's if you think about it, we're keeping track of all the coins that

203
00:15:13,160 --> 00:15:14,090
were used.

204
00:15:14,940 --> 00:15:23,460
To create change for a specific change needed, so that's going to be another vector, so we're going

205
00:15:23,460 --> 00:15:26,520
to basically have to make a vector of vectors so like a 2D vector.

206
00:15:28,010 --> 00:15:35,000
So I'm going to make this vector vectors and then call it cleans used, I think.

207
00:15:37,190 --> 00:15:39,770
And so it's basically going to be doing the same thing.

208
00:15:39,780 --> 00:15:45,320
You can imagine it just like our table, which is a vector of ants, but instead of ants, we're storing

209
00:15:45,380 --> 00:15:47,390
like what coins we're used.

210
00:15:48,500 --> 00:15:50,780
At some given some problem.

211
00:15:52,260 --> 00:15:53,520
Which will be an index, you know?

212
00:15:54,900 --> 00:15:56,790
So how am I going to modify this now?

213
00:15:57,420 --> 00:15:58,110
Well.

214
00:15:59,180 --> 00:16:08,660
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

215
00:16:08,660 --> 00:16:16,940
here to keep track of the coins used and then add it like later in the hour, Lou.

216
00:16:16,940 --> 00:16:18,710
So I don't need to add in the out of loop.

217
00:16:18,710 --> 00:16:21,920
So it makes sense with the scope, so it'll recognize it.

218
00:16:22,790 --> 00:16:31,850
So first off here, I'm going to just put this inner vector, which is the actual vector of coins that

219
00:16:31,850 --> 00:16:35,450
we're going to put in a specific index for our coins used.

220
00:16:36,860 --> 00:16:40,190
We're going to be updating this little like inner vector.

221
00:16:40,310 --> 00:16:47,080
So this guy, we're going to be updating that inside of this loop because this is looping over the coins.

222
00:16:47,090 --> 00:16:51,770
So in here we will add the coins that we're keeping track of to it.

223
00:16:52,940 --> 00:17:00,770
And then after this loop is done, so over here, when we're back in the scope of the outer loop, then

224
00:17:00,770 --> 00:17:04,910
we're going to have to add this highlighted vector to our coins used.

225
00:17:05,120 --> 00:17:10,760
And since we're adding it there, we're going to need to declare it here first, because since we're

226
00:17:10,760 --> 00:17:16,970
already referencing it, we basically need to have it like exist already.

227
00:17:16,970 --> 00:17:18,530
It's really because of in here too.

228
00:17:18,530 --> 00:17:21,800
We're going to be able, we're going to be needing to do stuff in here as well.

229
00:17:23,150 --> 00:17:25,460
So I'm going to just declare it right here.

230
00:17:26,120 --> 00:17:28,730
So it's already declared and we call it new vector.

231
00:17:30,420 --> 00:17:38,610
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

232
00:17:38,610 --> 00:17:42,000
because I wanted to call this again and I may need to check another condition.

233
00:17:43,900 --> 00:17:54,190
So basically, what I am going to do is set this to a variable, I want to say end smallest.

234
00:17:56,960 --> 00:17:58,070
Is equal to this.

235
00:17:58,430 --> 00:18:00,110
So I save it in a variable there.

236
00:18:02,900 --> 00:18:13,400
Then what I'm going to do is I'm basically going to say, OK, well, if smallest is not the same.

237
00:18:15,160 --> 00:18:23,020
As what I already had in the table, that just means that it is getting updated right.

238
00:18:25,460 --> 00:18:30,320
In that case, I'm going to basically.

239
00:18:32,230 --> 00:18:36,970
I'm basically going to try and look back at the coins that were used.

240
00:18:38,200 --> 00:18:42,470
At the same problem that I need to look at, so let's let's talk about that a little bit more.

241
00:18:42,490 --> 00:18:48,820
I'm going to go ahead and remove this for now because I just changed it to be recorded in this variable

242
00:18:48,820 --> 00:18:49,090
here.

243
00:18:50,350 --> 00:19:00,220
So this is a condition just saying if we're going to update it, so if the smallest is not Table II,

244
00:19:00,220 --> 00:19:06,070
you notice there's table, I hear that if it was Table II, that means that we didn't find something

245
00:19:06,700 --> 00:19:09,160
that was smaller.

246
00:19:09,190 --> 00:19:14,320
So we're not going to update our current position that we're at.

247
00:19:16,480 --> 00:19:23,470
So what I'm going to do is I'm going to set this inner vector of coins that were used.

248
00:19:25,770 --> 00:19:30,120
To basically this right here is what I'm looking for.

249
00:19:30,300 --> 00:19:36,390
I index, I remember I said it's going to mirror the table that we're using so far, but rather than

250
00:19:36,390 --> 00:19:41,190
storing the min number of coins, we're trying to store all the coins used.

251
00:19:41,700 --> 00:19:43,800
So we're using the same concept.

252
00:19:44,280 --> 00:19:49,680
But what I'm going to do is I'm actually going to try and grab what was there.

253
00:19:49,690 --> 00:19:57,420
So I'm going to say coins used that's like synonymous with our table here, basically for this other

254
00:19:57,420 --> 00:19:58,200
part of the problem.

255
00:19:59,100 --> 00:20:02,910
And then I'm going to use AI minus coin because that is the index that I'm using.

256
00:20:02,910 --> 00:20:05,160
I'm looking at the same sub problem.

257
00:20:06,340 --> 00:20:07,450
A-minus coin.

258
00:20:09,720 --> 00:20:18,000
So I'm basically getting the coins that were used at that previous said problem that we're looking at.

259
00:20:19,110 --> 00:20:21,600
So that was like that three, you know, when we had.

260
00:20:23,700 --> 00:20:32,040
We're currently on three and then we're using the coin one, and we did three minus one is two, and

261
00:20:32,040 --> 00:20:34,200
then we went to the table and looked at.

262
00:20:35,450 --> 00:20:36,980
How to make change for two.

263
00:20:37,610 --> 00:20:39,050
And we grabbed what was there.

264
00:20:39,470 --> 00:20:40,550
That's what I'm doing.

265
00:20:40,670 --> 00:20:41,660
Same thing.

266
00:20:42,050 --> 00:20:50,600
I'm looking at basically, you know, three minus one, if we're using the same example is two and I

267
00:20:50,600 --> 00:20:52,970
go to like how to make change for two.

268
00:20:54,220 --> 00:21:00,820
But we're not in the table anymore, our original table or in this other type of table that stored the

269
00:21:00,820 --> 00:21:03,790
actual coins that were used in a vector.

270
00:21:05,490 --> 00:21:12,240
So I'm setting this new vector equal to the vector that's stored there, that holds the coins that we're

271
00:21:12,240 --> 00:21:13,680
used for, that some problems.

272
00:21:15,540 --> 00:21:22,980
And then what I can do is basically do new vac

273
00:21:26,430 --> 00:21:33,330
dot push back the current coin because we have to consider it right.

274
00:21:34,850 --> 00:21:40,730
So you notice here we're adding one for the number, because this is the coin, we're saying, Hey,

275
00:21:41,360 --> 00:21:44,570
I already gave this coin, so I have to count it.

276
00:21:44,900 --> 00:21:45,860
Same thing here.

277
00:21:45,860 --> 00:21:49,130
I already gave this coin, so I have to record it.

278
00:21:50,420 --> 00:21:56,840
I'm not thinking about the fact that it's just one coin, I care about the actual coin now, so I need

279
00:21:56,840 --> 00:21:58,220
to add it to this.

280
00:21:59,130 --> 00:22:04,470
I got what was at the cell problem, but the fact is is that I already gave out a coin, so we need

281
00:22:04,470 --> 00:22:12,360
to keep track of, Hey, this is part of the solution for this problem or this final problem that we're

282
00:22:12,360 --> 00:22:12,750
at.

283
00:22:13,170 --> 00:22:18,900
I have to use the coin that I just gave in addition to what the answer was for the sub problem.

284
00:22:21,100 --> 00:22:23,050
Hopefully that makes sense, try and break it down.

285
00:22:23,950 --> 00:22:32,710
So either way, regardless of this part, right here we are and you said, you know, if the coin is

286
00:22:32,710 --> 00:22:38,320
less than or equal to I and we already have the smallest here.

287
00:22:40,350 --> 00:22:45,640
We know that it's either going to be the same or it's going to be something smaller.

288
00:22:45,660 --> 00:22:48,960
So it's safe to outside of this check here.

289
00:22:49,590 --> 00:22:52,860
Just go ahead and do Table I.

290
00:22:53,070 --> 00:22:56,190
Is now the smallest, whether it updated or not.

291
00:22:56,940 --> 00:23:03,570
We're just re updating it to me the same thing or updating it to be the actual smaller one if it ended

292
00:23:03,570 --> 00:23:04,590
up being this.

293
00:23:07,170 --> 00:23:18,180
OK, so then like I said, what we have to do is once this inner loop is done, we have to add this

294
00:23:18,240 --> 00:23:21,690
new set of coins, which are the solution.

295
00:23:22,890 --> 00:23:31,470
To our Victor, our original coins use the 2D like the outer dimension dimension of this vector, where

296
00:23:31,470 --> 00:23:36,120
we're keeping track of all the sets of coins that were used for a specific solution.

297
00:23:38,250 --> 00:23:39,930
So that's going to be right here.

298
00:23:39,990 --> 00:23:49,680
I'm going to say coins used, Dot pushed back and then new back because that was the updated coin list

299
00:23:49,680 --> 00:23:54,000
of coins solution for this problem, or it could have been for our final answer.

300
00:23:56,940 --> 00:24:03,060
OK, so now that we updated this, we're keeping track of it, and remember, it's totally mirroring

301
00:24:03,060 --> 00:24:04,710
this table that we've already done.

302
00:24:04,980 --> 00:24:07,440
It might seem a little crazy like what we're doing.

303
00:24:07,440 --> 00:24:11,760
We have this 2D thing, but it's only 2D because rather than keeping track of numbers.

304
00:24:12,870 --> 00:24:18,210
We're keeping track of list of the coins used of the denominations.

305
00:24:20,390 --> 00:24:25,430
So now that we're building that solution as well, we can add another little sea out here.

306
00:24:25,430 --> 00:24:31,640
So I'm going to say see out coins used for this minimum number of coins.

307
00:24:32,810 --> 00:24:34,700
I'm going to have it print on the same line.

308
00:24:34,940 --> 00:24:42,890
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

309
00:24:42,890 --> 00:24:49,690
it different this time just to mix it up and it's going to be coins used.

310
00:24:50,630 --> 00:24:51,650
What's it going to be?

311
00:24:52,190 --> 00:24:56,240
We're totally mirroring our other table, so it's going to be just like this.

312
00:24:56,480 --> 00:25:02,510
The answer is going to be stored at the exact same position as the position it was in our table for

313
00:25:02,510 --> 00:25:04,340
the answer that had just the count.

314
00:25:05,280 --> 00:25:09,390
So we're going to use that same thing, we're going to say change needed.

315
00:25:09,810 --> 00:25:16,320
That's the that's the position that has our answer also in this new this new league table that we're

316
00:25:16,320 --> 00:25:16,710
creating.

317
00:25:19,410 --> 00:25:24,120
So we're going for each one of the coins stored at this last position.

318
00:25:25,770 --> 00:25:30,840
And so I'm just going to say, see out I because we're looking over the actual items and then I'm going

319
00:25:30,840 --> 00:25:39,750
to put a little space here just to separate them so that all print nicely in my actual.

320
00:25:41,640 --> 00:25:42,780
Main coins function.

321
00:25:43,860 --> 00:25:48,210
So let's run this again, let's kind of look back at what our answers were, right?

322
00:25:48,960 --> 00:25:50,220
They were both too.

323
00:25:51,540 --> 00:25:53,340
Let's go ahead and.

324
00:25:54,390 --> 00:25:57,540
Check, we already have this one in here, so we'll check this one out, right?

325
00:25:58,410 --> 00:26:05,520
So the greedy method, let's just I'm just reiterating this, so it really like gets to the point of

326
00:26:05,520 --> 00:26:06,750
like what we're talking about.

327
00:26:07,020 --> 00:26:12,440
So 14 and one and one and one was what really method used, and that was not optimal.

328
00:26:12,450 --> 00:26:13,680
That was for coins.

329
00:26:13,690 --> 00:26:16,320
The optimal solution was these two.

330
00:26:16,590 --> 00:26:22,740
When we ran it last time, we got a successful answer that said that the main point was to that is correct.

331
00:26:23,190 --> 00:26:27,120
But now with verify that the actual coins you used were eight and nine.

332
00:26:28,970 --> 00:26:31,190
So then we can really feel like we did this correctly.

333
00:26:31,640 --> 00:26:32,930
So let's go ahead and run it.

334
00:26:37,690 --> 00:26:38,680
So there we go.

335
00:26:38,710 --> 00:26:43,060
We see that nine in eight with the two coins that we used.

336
00:26:43,210 --> 00:26:44,860
And it says two coins.

337
00:26:45,400 --> 00:26:52,330
So we have seen now that this effectively solved with the greedy method can solve it looked at every

338
00:26:52,330 --> 00:26:58,780
possible solution and that made it realize that there was this better solution of just two coins to

339
00:26:58,780 --> 00:26:59,020
make.

340
00:26:59,020 --> 00:26:59,740
17.

341
00:27:00,610 --> 00:27:02,440
Let's go ahead and test out our other ones.

342
00:27:02,920 --> 00:27:08,140
So we've been an arms one, and our example in the previous lecture was 11.

343
00:27:08,410 --> 00:27:13,420
We already kind of talked about that the minimum number coins is two, but this time what we should

344
00:27:13,420 --> 00:27:20,980
be seeing is a 10 in a one because that is what we would use to make change for 11.

345
00:27:21,670 --> 00:27:24,190
So now that that switch to, let's go ahead and run it.

346
00:27:27,080 --> 00:27:33,470
And there we see our answer, so M. coins as to what are the coins that were used for that solution?

347
00:27:33,830 --> 00:27:35,480
The coins were ten in one.

348
00:27:36,870 --> 00:27:42,480
OK, so hopefully that was pretty interesting for you, dynamic programming is really cool, and this

349
00:27:42,480 --> 00:27:47,160
is just one of many, many problems that can be solved with dynamic programming.

350
00:27:47,760 --> 00:27:49,750
We're going to get into some more after this.

351
00:27:50,370 --> 00:27:57,870
But if you were able to figure this out on your own, then I definitely give you a lot of respect.

352
00:27:57,870 --> 00:27:59,880
If not, it's totally fine.

353
00:28:00,240 --> 00:28:00,720
You know what?

354
00:28:00,720 --> 00:28:07,530
It's a difficult problem, and I hope that now after seeing this solution video, you were able to understand

355
00:28:07,530 --> 00:28:09,030
how we put all this together.

356
00:28:10,890 --> 00:28:15,120
OK, so with that, I'll go ahead and see you in the next lecture.