1
00:00:00,870 --> 00:00:07,950
OK, so to start out with the dynamic programming, I am going to go over a very classic example.

2
00:00:07,980 --> 00:00:10,530
This used a lot to explain dynamic programming.

3
00:00:11,400 --> 00:00:17,760
I put one here because I'm going to go over many examples in hopes that we can learn about dynamic programming

4
00:00:17,760 --> 00:00:23,810
and the greedy method through examples and doing and implementing along the way.

5
00:00:23,820 --> 00:00:30,030
Of course, I'll be explaining the theoretical aspects of things and including visualizations, and

6
00:00:30,030 --> 00:00:32,070
I think you just got to practice a lot with this.

7
00:00:32,400 --> 00:00:37,950
These are very important, complex and very important topics, and you can do a lot of cool things with

8
00:00:37,950 --> 00:00:38,220
them.

9
00:00:38,220 --> 00:00:38,550
So.

10
00:00:39,080 --> 00:00:42,870
I'm talking about the greedy method and dynamic programming when I say them.

11
00:00:43,850 --> 00:00:44,930
So let's go ahead and get started.

12
00:00:46,890 --> 00:00:52,560
So let's revisit a very familiar example, so this is the Fibonacci sequence, so if you recall from

13
00:00:52,560 --> 00:00:58,350
our recursion lecture, we went over this algorithm and we actually traced the recursive calls with

14
00:00:58,350 --> 00:01:00,090
a recursive tree.

15
00:01:00,360 --> 00:01:06,810
Here's the code over here if it's ringing any bells and the recursive tree actually looked like this

16
00:01:06,840 --> 00:01:07,720
right here.

17
00:01:07,920 --> 00:01:10,830
So maybe you recognize this as well.

18
00:01:11,250 --> 00:01:16,920
You also may recall from that lecture that we did mention we would optimize this algorithm later on,

19
00:01:16,920 --> 00:01:18,480
and that's what we're doing right now.

20
00:01:19,050 --> 00:01:27,660
We are going to try and use dynamic programming to come up with a more time efficient solution as far

21
00:01:27,660 --> 00:01:28,630
as time complexity.

22
00:01:28,650 --> 00:01:34,050
So when I'm talking about optimizing this problem, don't get it confused with what I talked about in

23
00:01:34,050 --> 00:01:40,470
the previous lecture, where we said that dynamic programming and greedy method are used to kind of

24
00:01:40,470 --> 00:01:48,750
solve optimization problems like, for example, the optimal number of things or maximizing profit to

25
00:01:48,750 --> 00:01:53,370
get the optimal amount or something like that or like optimal shortest path.

26
00:01:53,880 --> 00:01:59,070
That's not what I'm talking about dynamic programming and getting method or both, you know, meant

27
00:01:59,070 --> 00:02:00,330
to solve those problems.

28
00:02:00,330 --> 00:02:01,950
But right now, I'm talking about Optum.

29
00:02:02,010 --> 00:02:06,840
When I say optimization, I'm talking about finding a more optimal time complexity, a better solution

30
00:02:06,840 --> 00:02:09,180
and more efficient solution to the Fibonacci problem.

31
00:02:10,050 --> 00:02:12,300
So that's what I mean in this example.

32
00:02:14,030 --> 00:02:23,480
So what we're going to do is that you notice you might have noticed actually that this algorithm repeats

33
00:02:23,480 --> 00:02:27,710
a lot of stuff, so it's repeating a lot of calculations and recalculating them.

34
00:02:28,790 --> 00:02:36,080
So if you see, like, for example, down here, we have like three is getting calculated right here.

35
00:02:37,490 --> 00:02:41,780
And, you know, since we're doing five of them minus one, we actually head over this direction first.

36
00:02:41,780 --> 00:02:46,610
So we've already done this, but then we do it again over here and then we do it again over here.

37
00:02:47,640 --> 00:02:53,190
And, you know, an even worse example is something like calculating for to, you know, we have to

38
00:02:53,190 --> 00:03:01,460
calculate for two right here and right here and right here and right here, right here.

39
00:03:01,470 --> 00:03:04,920
So we're doing things kind of redundantly over and over.

40
00:03:04,920 --> 00:03:12,430
And if we use dynamic programming, we can actually avoid doing this so we don't have to resolve for

41
00:03:12,510 --> 00:03:14,430
the Fibonacci numbers we've already solved.

42
00:03:14,430 --> 00:03:14,790
Four.

43
00:03:16,350 --> 00:03:17,360
So how do we do that?

44
00:03:17,370 --> 00:03:21,860
Well, what if we could keep track of the Fibonacci numbers we have already solved for?

45
00:03:21,870 --> 00:03:26,490
So during the recursive process, we don't end up just redundantly recalculating them like that.

46
00:03:27,180 --> 00:03:33,810
So let's go ahead and walk through this recursive call tree here again and see what that would look

47
00:03:33,810 --> 00:03:34,080
like.

48
00:03:34,110 --> 00:03:39,000
So just to kind of recap when I'm walking through it, just think of the code right here.

49
00:03:39,360 --> 00:03:41,790
First, we're doing this five in minus one call.

50
00:03:41,790 --> 00:03:43,380
So those are our left turns.

51
00:03:43,380 --> 00:03:48,240
And so since it's just going to keep bouncing off of this and going back up to the top until we stop

52
00:03:48,240 --> 00:03:50,820
by reaching a base case, it's just going to keep going left.

53
00:03:51,210 --> 00:03:56,010
So if you might already know that, but and remember that from the recursive lecture, but I just wanted

54
00:03:56,010 --> 00:04:01,140
to kind of refresh everyone on that in case we're still feeling a little shaky about what it is to traverse

55
00:04:01,140 --> 00:04:01,590
this tree.

56
00:04:02,280 --> 00:04:04,620
So that's why we're going to be heading all the way down to the left first.

57
00:04:04,860 --> 00:04:09,060
And then when we hit the base case, you know, we can come back up in the recursive process one level

58
00:04:09,060 --> 00:04:14,610
and then we can we'll come back to where we left off, which is right here and we'll go to the second

59
00:04:14,610 --> 00:04:16,470
right hand turn, which is the minus two.

60
00:04:16,920 --> 00:04:19,020
So let's go ahead and do that.

61
00:04:20,040 --> 00:04:23,510
So I am going to start at six, which is my input.

62
00:04:23,550 --> 00:04:24,960
This problem is five six.

63
00:04:25,140 --> 00:04:28,830
So I start there and we're going to go down to the left.

64
00:04:28,840 --> 00:04:34,590
So five and minus one for one, three and minus one to come down to one.

65
00:04:35,130 --> 00:04:41,970
And one is a base case because we said, you know, if it's less than or equal to one, then just return

66
00:04:41,970 --> 00:04:45,930
in and this is five than this one in this one here.

67
00:04:46,470 --> 00:04:48,480
So we know that answers one for this.

68
00:04:48,960 --> 00:04:54,090
And so what am I to do is say, Hey, I know I now know what five one is, so I'm going to put five

69
00:04:54,090 --> 00:04:55,200
of one right here.

70
00:04:55,210 --> 00:04:58,540
So this represents one as in favor of one.

71
00:05:00,060 --> 00:05:05,990
Then that sends me back up here and I can do my right call and zero the base case as well.

72
00:05:06,000 --> 00:05:07,440
And so in is zero for that.

73
00:05:07,440 --> 00:05:08,790
So I know the answer is zero.

74
00:05:09,120 --> 00:05:12,390
So I can say, Hey, I know what five zero is two.

75
00:05:14,000 --> 00:05:19,490
And now these to get, you know, added together to give you the first of two, which is one right here,

76
00:05:19,490 --> 00:05:22,940
one plus here's one so I can say, Hey, I know what Fable two is.

77
00:05:23,850 --> 00:05:32,760
And now I had backup from what called the two, and I do my right hand in my house to call, and I have

78
00:05:32,760 --> 00:05:39,150
a one here and I already know what that is because I've seen it so I can pretty much ignore that it

79
00:05:39,150 --> 00:05:40,430
also is a base case.

80
00:05:40,440 --> 00:05:43,620
So it kind of doesn't matter anyways, but I've already seen that.

81
00:05:45,120 --> 00:05:48,570
So then I can go back up to three.

82
00:05:48,750 --> 00:05:53,520
And then when we add these two and I can say handle three is now, so I can mark that down over here,

83
00:05:54,090 --> 00:05:56,340
head up to where that came from, which is four.

84
00:05:56,940 --> 00:05:58,500
And I do my RN minus to call.

85
00:05:59,730 --> 00:06:03,090
And I say, have I seen two before, do I know what that is?

86
00:06:03,300 --> 00:06:04,800
I know the answer to Yeah, yeah.

87
00:06:05,100 --> 00:06:09,840
I have seen for two weeks I haven't worked out here, so I actually don't need to go any further.

88
00:06:09,840 --> 00:06:12,360
So I don't need to do these guys down here.

89
00:06:12,840 --> 00:06:16,220
So I'm just going to get my answer for food too and come back up.

90
00:06:17,220 --> 00:06:23,160
And now I know if it were for so I can mark that down, go back up here, go down to the right.

91
00:06:23,280 --> 00:06:27,420
I already have process with three because remember, we did it over here.

92
00:06:28,090 --> 00:06:29,250
That's when we got our answer.

93
00:06:29,250 --> 00:06:33,720
So I don't need to do any of this stuff below for the three.

94
00:06:34,170 --> 00:06:39,150
So I can ignore all this work here because I can just grab the answer right here at this stack frame

95
00:06:39,420 --> 00:06:40,800
and then head back up.

96
00:06:40,800 --> 00:06:42,420
And now these two go together.

97
00:06:42,420 --> 00:06:44,520
So I have an answer for five.

98
00:06:45,570 --> 00:06:50,820
Then I go back to the starting original call and I can do my own minus two.

99
00:06:52,640 --> 00:06:56,540
And I say, OK, I've I've seen this before.

100
00:06:56,570 --> 00:07:01,760
Yes, I have, I have it marked here, so I don't need to do any of this work here, so I can eliminate

101
00:07:01,760 --> 00:07:03,110
a lot of stuff right here.

102
00:07:03,680 --> 00:07:09,530
And now these two together, I go to the sixth and I say, Hey, I've seen five of six and I am done,

103
00:07:09,530 --> 00:07:12,530
so I transition there to a new slide.

104
00:07:13,370 --> 00:07:16,630
So that got rid of a lot of stuff here.

105
00:07:16,640 --> 00:07:17,960
So pretty cool.

106
00:07:18,110 --> 00:07:20,660
Let's do this in a little bit more detail.

107
00:07:20,780 --> 00:07:26,870
So I'm going to break it down a little more and see what is it really doing when I say that we are going

108
00:07:26,870 --> 00:07:30,390
to keep track of these numbers that we've solved for already?

109
00:07:31,190 --> 00:07:38,660
What we're actually going to do in this example is we're going to keep track of things in an array.

110
00:07:39,290 --> 00:07:41,930
So right here I have the array indices.

111
00:07:42,050 --> 00:07:45,920
So you can imagine like what Story Zero will be here on top or stored at.

112
00:07:45,920 --> 00:07:48,410
One will be here was sorted to be here.

113
00:07:48,680 --> 00:07:51,920
So this is like five zero five one five two, so on.

114
00:07:53,300 --> 00:07:58,700
So let's go ahead and walk through this example again, and we will be updating with the values and

115
00:07:58,700 --> 00:08:02,630
the answers for what five is in this race.

116
00:08:02,630 --> 00:08:05,660
So that's what we're doing is we're going to keep track of it in an array.

117
00:08:06,980 --> 00:08:14,030
So if I go all the way down here and we got to our base case down here and we said, OK, well, fib

118
00:08:14,030 --> 00:08:15,650
of one is one.

119
00:08:16,190 --> 00:08:18,650
So I put that there at index one.

120
00:08:19,620 --> 00:08:24,660
And then I went back up to where it got called from, I came down to this in minus two and I said,

121
00:08:24,660 --> 00:08:29,100
Hey, fib of zero is zero, that's a base case, so I can update that in my area.

122
00:08:30,510 --> 00:08:37,080
Since I have both of these now, I was able to do one plus zero equals one and now I can go back to

123
00:08:37,080 --> 00:08:41,170
two and store that result in two, so I can put that in my array.

124
00:08:41,190 --> 00:08:43,560
I now know that the two is one.

125
00:08:45,310 --> 00:08:50,320
I go back to where that got called from, so I need this other in minus two to be added to this, so

126
00:08:50,650 --> 00:08:52,120
I already know what this is.

127
00:08:52,150 --> 00:08:54,580
I can just go straight into my array and grab it.

128
00:08:55,060 --> 00:08:57,160
So that's, you know, five of one is one.

129
00:08:57,940 --> 00:08:59,680
So I can say one.

130
00:08:59,680 --> 00:09:05,740
Plus what I already got for two is going to be two.

131
00:09:06,190 --> 00:09:08,350
And I can store that and three.

132
00:09:08,830 --> 00:09:10,720
So I know that five three is to.

133
00:09:12,170 --> 00:09:14,270
Then I can go back to where that got called from.

134
00:09:14,630 --> 00:09:16,790
And I can do that in is to call over here.

135
00:09:17,420 --> 00:09:22,070
And I say, OK, I'm going to check my array, OK?

136
00:09:22,610 --> 00:09:24,830
I do have something in here for two.

137
00:09:25,160 --> 00:09:30,350
It's one so I can just do two plus one is three and I can store that at four.

138
00:09:30,890 --> 00:09:37,280
So I don't need to do these down here and now I have that stored here at four, so five before it's

139
00:09:37,280 --> 00:09:37,640
three.

140
00:09:39,110 --> 00:09:40,550
So then we come back up to five.

141
00:09:40,580 --> 00:09:41,000
Same thing.

142
00:09:41,000 --> 00:09:42,970
Go down here three is two.

143
00:09:42,980 --> 00:09:46,160
So I can add that three and two don't need to do this down here.

144
00:09:46,400 --> 00:09:47,180
Ignore that.

145
00:09:47,660 --> 00:09:53,240
And then I can add my thing for five or five because I knew the way out of these and I got five.

146
00:09:53,240 --> 00:09:57,850
So I store five at five in the array.

147
00:09:57,860 --> 00:10:03,350
And so now I can come back up to six go down in here for I know what four is, it's three.

148
00:10:03,350 --> 00:10:06,140
So no need to do any further recursion here.

149
00:10:06,140 --> 00:10:11,900
I can just grab that three out of there and added to this other one over here, which is five.

150
00:10:12,860 --> 00:10:15,050
So that gives me an answer of eight am.

151
00:10:15,050 --> 00:10:16,460
I ignore all this down here.

152
00:10:16,460 --> 00:10:22,460
So I make that off and I can store eight at six and then I can return that as my answer.

153
00:10:23,240 --> 00:10:28,790
So hopefully going through that once again and showing you kind of how it works as an array was how

154
00:10:28,850 --> 00:10:31,220
it can help you understand what it is we're really doing here.

155
00:10:31,230 --> 00:10:39,200
So this this implementation of dynamic programming algorithm is us just keeping track of things in an

156
00:10:39,200 --> 00:10:42,470
array so we don't have to redundantly recalculate stuff.

157
00:10:44,380 --> 00:10:46,060
So what is this code look like?

158
00:10:46,090 --> 00:10:49,670
Well, the code actually looks like this over here.

159
00:10:49,810 --> 00:10:55,770
So what I am doing here in this example, you see, I had to make it say seven, because we're starting

160
00:10:55,780 --> 00:10:57,880
at zero, we still care about five zero.

161
00:10:57,880 --> 00:11:05,410
So this would be like zero one two three four five six and just doing the same thing five of six.

162
00:11:05,410 --> 00:11:09,880
So I kind of hard coded an example here just to be as basic as possible.

163
00:11:11,080 --> 00:11:12,760
So you see that I make this array.

164
00:11:12,760 --> 00:11:17,710
I pass five six to my tip function for dynamic programming.

165
00:11:19,370 --> 00:11:21,410
We put this check originally up here.

166
00:11:21,590 --> 00:11:26,240
You notice that I filled this whole thing with negative ones, so that's basically to say, you know,

167
00:11:26,240 --> 00:11:27,560
if it's negative one.

168
00:11:28,280 --> 00:11:31,820
That means that we haven't yet solved for that fake fib number.

169
00:11:32,060 --> 00:11:35,390
If we have, then we're going to replace it with one of the answers we can put.

170
00:11:35,390 --> 00:11:41,900
Negative one is kind of a safe initial value there because we know that our Fibonacci series is not

171
00:11:41,900 --> 00:11:43,820
going to have any negative value there for us.

172
00:11:43,820 --> 00:11:45,950
So that's why we put negative ones.

173
00:11:45,950 --> 00:11:52,040
So we're basically like, OK, if whatever is if the current Fibonacci number, we're at that index

174
00:11:52,040 --> 00:11:57,170
and our air is not minus one, it means that we already have calculated it so we can just straight up

175
00:11:57,170 --> 00:11:59,360
stop right here and return that value.

176
00:12:00,550 --> 00:12:05,230
Otherwise, we check our normal base case to see if we reach the base case, whether it's zero or one

177
00:12:05,230 --> 00:12:07,000
in which we can just return that as well.

178
00:12:07,720 --> 00:12:15,880
If not, then what we're going to do is actually try and set the position in the array equal to this

179
00:12:15,880 --> 00:12:17,930
recursive call here.

180
00:12:17,950 --> 00:12:20,170
So this recursive call plus this recursive call.

181
00:12:22,330 --> 00:12:27,370
And then so you can imagine that that's going to come back here and return one of these and it's going

182
00:12:27,370 --> 00:12:28,900
to end up getting stored in here.

183
00:12:28,960 --> 00:12:31,900
So if you can think back to the tree kind of and connected to the code.

184
00:12:33,050 --> 00:12:38,030
And then, you know, we'll return this afterwards, so instead of just returning straight up on this

185
00:12:38,030 --> 00:12:44,060
line like we were before, we're saving it and then returning that value, it's stored at that index.

186
00:12:45,920 --> 00:12:53,960
So pretty cool implementation in kind of pretty cool how something so simple can be so efficient.

187
00:12:54,600 --> 00:13:04,070
So if you notice before we actually ended up only doing one two three four five six seven eight nine

188
00:13:04,070 --> 00:13:10,940
10 11 recursive calls for this, we eliminated one two three four five six seven eight nine 10 11 12

189
00:13:10,940 --> 00:13:18,120
13 14 recursive calls, so eliminated 14 recursive calls and ended up with just 11 recursive calls.

190
00:13:18,140 --> 00:13:19,070
That's pretty cool.

191
00:13:19,730 --> 00:13:20,900
How much work we got rid of.

192
00:13:22,980 --> 00:13:32,200
So this style of dynamic programming is something referred to as memorization, memorization.

193
00:13:32,760 --> 00:13:35,700
So it kind of sounds like memorization, and it's very similar.

194
00:13:35,710 --> 00:13:39,810
We're just kind of keeping track of the stuff that we've done somewhere in this container.

195
00:13:40,290 --> 00:13:47,940
But we're doing it top down, kind of like recursively, you know, we came to top down like this and.

196
00:13:49,010 --> 00:13:54,230
We kind of, you know, we're storing stuff in, and as we came back on the recursive phase, we didn't

197
00:13:54,230 --> 00:13:54,920
continue.

198
00:13:54,920 --> 00:13:58,850
If it was already in there, we just kind of got what we needed out of the container.

199
00:13:59,720 --> 00:14:04,820
And so something that we're going to be talking about more is the difference between memorization and

200
00:14:04,820 --> 00:14:12,140
kind of a top down thing compared to something that is called, I think tabulation is what it's called,

201
00:14:12,140 --> 00:14:18,290
which is actually kind of building the table straight out and we can actually look at something like

202
00:14:18,290 --> 00:14:18,590
that.

203
00:14:18,590 --> 00:14:21,830
You don't have to do this recursively like we did.

204
00:14:21,830 --> 00:14:27,320
You can actually solve this iteratively using dynamic programming, and that's kind of building out

205
00:14:27,320 --> 00:14:29,120
a table with a for loop.

206
00:14:29,780 --> 00:14:32,150
So like this, the iterative code.

207
00:14:33,270 --> 00:14:36,000
Instead, what we're going to do, we have the same array being passed.

208
00:14:36,880 --> 00:14:43,900
But if we're looking for, you know, five of one or for those zero, we're just going to immediately

209
00:14:43,900 --> 00:14:45,620
return it because we know what that is.

210
00:14:46,570 --> 00:14:51,100
Then what we're going to do is just try and start our table off with these two values because we need

211
00:14:51,100 --> 00:14:56,620
to know what one of the zero is, so we can then calculate the next figure to because it's the sum of

212
00:14:56,620 --> 00:14:57,520
the previous values.

213
00:14:58,060 --> 00:15:04,030
So we just hard code that right away we say, you know, our array is zero zero zero zero five one is

214
00:15:04,030 --> 00:15:06,610
one set those in our at the correct positions.

215
00:15:07,390 --> 00:15:13,570
Then we loop through starting at two, at the next position, the next fib number and go all the way

216
00:15:13,570 --> 00:15:17,260
up through our array and we just populate our array.

217
00:15:18,540 --> 00:15:24,900
As we go with whatever the previous two values are, so whatever I wear out, we look at the previous

218
00:15:24,900 --> 00:15:28,800
two before it and we sum that and story today.

219
00:15:29,760 --> 00:15:34,620
And so pretty simple, we just literally loop through that and you can see that we're pretty much doing

220
00:15:34,620 --> 00:15:41,850
this in like linear time because we just have to go through that size of in list even less, you know,

221
00:15:41,850 --> 00:15:42,510
we're starting to.

222
00:15:43,170 --> 00:15:48,360
And then at the end, we just return the very last thing in the list, which is that are in numbers

223
00:15:48,360 --> 00:15:52,680
so we can get that instead of announcing numbers since we've already calculated everything as a prerequisite

224
00:15:53,160 --> 00:15:54,300
to the left before it.

225
00:15:55,080 --> 00:15:59,160
So it's like the two previous numbers right here at the very end we have those, we get our last number

226
00:15:59,160 --> 00:15:59,970
and we return that.

227
00:16:01,380 --> 00:16:02,660
So pretty cool.

228
00:16:02,670 --> 00:16:08,790
A lot of dynamic programming algorithms kind of use this style or we're just building up this table.

229
00:16:09,800 --> 00:16:16,190
And we might actually like and some things will just build out a table first and then try and compute

230
00:16:16,190 --> 00:16:17,720
an optimal solution.

231
00:16:17,870 --> 00:16:22,310
You know, remember I talked about this is kind of optimized our time complexity, which is an added

232
00:16:22,310 --> 00:16:24,590
benefit quite often of dynamic programming.

233
00:16:25,070 --> 00:16:29,420
But we also use dynamic programming to come up with like an optimal solution to see like, how can we

234
00:16:29,420 --> 00:16:33,530
get the best, you know, the most things, the most value out of some type of problem.

235
00:16:34,810 --> 00:16:40,540
So just wanted to show you these two versions, I will get into talking more about memorization, and

236
00:16:41,080 --> 00:16:47,290
I think tabulation of where I am remembering that correctly is what's called a billion table, and we'll

237
00:16:47,290 --> 00:16:50,500
get more in depth and cover some more complicated examples.

238
00:16:50,500 --> 00:16:55,720
But hopefully this was a simple enough introduction for you, and it kind of cool for you to see how

239
00:16:57,100 --> 00:17:00,940
much more efficient we can make our calculating the Fibonacci number.

240
00:17:01,540 --> 00:17:01,810
All right.

241
00:17:01,810 --> 00:17:04,000
So with that, I will see you in the next lecture.