OK, so to start out with the dynamic programming, I am going to go over a very classic example.
This used a lot to explain dynamic programming.
I put one here because I'm going to go over many examples in hopes that we can learn about dynamic programming
and the greedy method through examples and doing and implementing along the way.
Of course, I'll be explaining the theoretical aspects of things and including visualizations, and
I think you just got to practice a lot with this.
These are very important, complex and very important topics, and you can do a lot of cool things with
them.
So.
I'm talking about the greedy method and dynamic programming when I say them.
So let's go ahead and get started.
So let's revisit a very familiar example, so this is the Fibonacci sequence, so if you recall from
our recursion lecture, we went over this algorithm and we actually traced the recursive calls with
a recursive tree.
Here's the code over here if it's ringing any bells and the recursive tree actually looked like this
right here.
So maybe you recognize this as well.
You also may recall from that lecture that we did mention we would optimize this algorithm later on,
and that's what we're doing right now.
We are going to try and use dynamic programming to come up with a more time efficient solution as far
as time complexity.
So when I'm talking about optimizing this problem, don't get it confused with what I talked about in
the previous lecture, where we said that dynamic programming and greedy method are used to kind of
solve optimization problems like, for example, the optimal number of things or maximizing profit to
get the optimal amount or something like that or like optimal shortest path.
That's not what I'm talking about dynamic programming and getting method or both, you know, meant
to solve those problems.
But right now, I'm talking about Optum.
When I say optimization, I'm talking about finding a more optimal time complexity, a better solution
and more efficient solution to the Fibonacci problem.
So that's what I mean in this example.
So what we're going to do is that you notice you might have noticed actually that this algorithm repeats
a lot of stuff, so it's repeating a lot of calculations and recalculating them.
So if you see, like, for example, down here, we have like three is getting calculated right here.
And, you know, since we're doing five of them minus one, we actually head over this direction first.
So we've already done this, but then we do it again over here and then we do it again over here.
And, you know, an even worse example is something like calculating for to, you know, we have to
calculate for two right here and right here and right here and right here, right here.
So we're doing things kind of redundantly over and over.
And if we use dynamic programming, we can actually avoid doing this so we don't have to resolve for
the Fibonacci numbers we've already solved.
Four.
So how do we do that?
Well, what if we could keep track of the Fibonacci numbers we have already solved for?
So during the recursive process, we don't end up just redundantly recalculating them like that.
So let's go ahead and walk through this recursive call tree here again and see what that would look
like.
So just to kind of recap when I'm walking through it, just think of the code right here.
First, we're doing this five in minus one call.
So those are our left turns.
And so since it's just going to keep bouncing off of this and going back up to the top until we stop
by reaching a base case, it's just going to keep going left.
So if you might already know that, but and remember that from the recursive lecture, but I just wanted
to kind of refresh everyone on that in case we're still feeling a little shaky about what it is to traverse
this tree.
So that's why we're going to be heading all the way down to the left first.
And then when we hit the base case, you know, we can come back up in the recursive process one level
and then we can we'll come back to where we left off, which is right here and we'll go to the second
right hand turn, which is the minus two.
So let's go ahead and do that.
So I am going to start at six, which is my input.
This problem is five six.
So I start there and we're going to go down to the left.
So five and minus one for one, three and minus one to come down to one.
And one is a base case because we said, you know, if it's less than or equal to one, then just return
in and this is five than this one in this one here.
So we know that answers one for this.
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
of one right here.
So this represents one as in favor of one.
Then that sends me back up here and I can do my right call and zero the base case as well.
And so in is zero for that.
So I know the answer is zero.
So I can say, Hey, I know what five zero is two.
And now these to get, you know, added together to give you the first of two, which is one right here,
one plus here's one so I can say, Hey, I know what Fable two is.
And now I had backup from what called the two, and I do my right hand in my house to call, and I have
a one here and I already know what that is because I've seen it so I can pretty much ignore that it
also is a base case.
So it kind of doesn't matter anyways, but I've already seen that.
So then I can go back up to three.
And then when we add these two and I can say handle three is now, so I can mark that down over here,
head up to where that came from, which is four.
And I do my RN minus to call.
And I say, have I seen two before, do I know what that is?
I know the answer to Yeah, yeah.
I have seen for two weeks I haven't worked out here, so I actually don't need to go any further.
So I don't need to do these guys down here.
So I'm just going to get my answer for food too and come back up.
And now I know if it were for so I can mark that down, go back up here, go down to the right.
I already have process with three because remember, we did it over here.
That's when we got our answer.
So I don't need to do any of this stuff below for the three.
So I can ignore all this work here because I can just grab the answer right here at this stack frame
and then head back up.
And now these two go together.
So I have an answer for five.
Then I go back to the starting original call and I can do my own minus two.
And I say, OK, I've I've seen this before.
Yes, I have, I have it marked here, so I don't need to do any of this work here, so I can eliminate
a lot of stuff right here.
And now these two together, I go to the sixth and I say, Hey, I've seen five of six and I am done,
so I transition there to a new slide.
So that got rid of a lot of stuff here.
So pretty cool.
Let's do this in a little bit more detail.
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
to keep track of these numbers that we've solved for already?
What we're actually going to do in this example is we're going to keep track of things in an array.
So right here I have the array indices.
So you can imagine like what Story Zero will be here on top or stored at.
One will be here was sorted to be here.
So this is like five zero five one five two, so on.
So let's go ahead and walk through this example again, and we will be updating with the values and
the answers for what five is in this race.
So that's what we're doing is we're going to keep track of it in an array.
So if I go all the way down here and we got to our base case down here and we said, OK, well, fib
of one is one.
So I put that there at index one.
And then I went back up to where it got called from, I came down to this in minus two and I said,
Hey, fib of zero is zero, that's a base case, so I can update that in my area.
Since I have both of these now, I was able to do one plus zero equals one and now I can go back to
two and store that result in two, so I can put that in my array.
I now know that the two is one.
I go back to where that got called from, so I need this other in minus two to be added to this, so
I already know what this is.
I can just go straight into my array and grab it.
So that's, you know, five of one is one.
So I can say one.
Plus what I already got for two is going to be two.
And I can store that and three.
So I know that five three is to.
Then I can go back to where that got called from.
And I can do that in is to call over here.
And I say, OK, I'm going to check my array, OK?
I do have something in here for two.
It's one so I can just do two plus one is three and I can store that at four.
So I don't need to do these down here and now I have that stored here at four, so five before it's
three.
So then we come back up to five.
Same thing.
Go down here three is two.
So I can add that three and two don't need to do this down here.
Ignore that.
And then I can add my thing for five or five because I knew the way out of these and I got five.
So I store five at five in the array.
And so now I can come back up to six go down in here for I know what four is, it's three.
So no need to do any further recursion here.
I can just grab that three out of there and added to this other one over here, which is five.
So that gives me an answer of eight am.
I ignore all this down here.
So I make that off and I can store eight at six and then I can return that as my answer.
So hopefully going through that once again and showing you kind of how it works as an array was how
it can help you understand what it is we're really doing here.
So this this implementation of dynamic programming algorithm is us just keeping track of things in an
array so we don't have to redundantly recalculate stuff.
So what is this code look like?
Well, the code actually looks like this over here.
So what I am doing here in this example, you see, I had to make it say seven, because we're starting
at zero, we still care about five zero.
So this would be like zero one two three four five six and just doing the same thing five of six.
So I kind of hard coded an example here just to be as basic as possible.
So you see that I make this array.
I pass five six to my tip function for dynamic programming.
We put this check originally up here.
You notice that I filled this whole thing with negative ones, so that's basically to say, you know,
if it's negative one.
That means that we haven't yet solved for that fake fib number.
If we have, then we're going to replace it with one of the answers we can put.
Negative one is kind of a safe initial value there because we know that our Fibonacci series is not
going to have any negative value there for us.
So that's why we put negative ones.
So we're basically like, OK, if whatever is if the current Fibonacci number, we're at that index
and our air is not minus one, it means that we already have calculated it so we can just straight up
stop right here and return that value.
Otherwise, we check our normal base case to see if we reach the base case, whether it's zero or one
in which we can just return that as well.
If not, then what we're going to do is actually try and set the position in the array equal to this
recursive call here.
So this recursive call plus this recursive call.
And then so you can imagine that that's going to come back here and return one of these and it's going
to end up getting stored in here.
So if you can think back to the tree kind of and connected to the code.
And then, you know, we'll return this afterwards, so instead of just returning straight up on this
line like we were before, we're saving it and then returning that value, it's stored at that index.
So pretty cool implementation in kind of pretty cool how something so simple can be so efficient.
So if you notice before we actually ended up only doing one two three four five six seven eight nine
10 11 recursive calls for this, we eliminated one two three four five six seven eight nine 10 11 12
13 14 recursive calls, so eliminated 14 recursive calls and ended up with just 11 recursive calls.
That's pretty cool.
How much work we got rid of.
So this style of dynamic programming is something referred to as memorization, memorization.
So it kind of sounds like memorization, and it's very similar.
We're just kind of keeping track of the stuff that we've done somewhere in this container.
But we're doing it top down, kind of like recursively, you know, we came to top down like this and.
We kind of, you know, we're storing stuff in, and as we came back on the recursive phase, we didn't
continue.
If it was already in there, we just kind of got what we needed out of the container.
And so something that we're going to be talking about more is the difference between memorization and
kind of a top down thing compared to something that is called, I think tabulation is what it's called,
which is actually kind of building the table straight out and we can actually look at something like
that.
You don't have to do this recursively like we did.
You can actually solve this iteratively using dynamic programming, and that's kind of building out
a table with a for loop.
So like this, the iterative code.
Instead, what we're going to do, we have the same array being passed.
But if we're looking for, you know, five of one or for those zero, we're just going to immediately
return it because we know what that is.
Then what we're going to do is just try and start our table off with these two values because we need
to know what one of the zero is, so we can then calculate the next figure to because it's the sum of
the previous values.
So we just hard code that right away we say, you know, our array is zero zero zero zero five one is
one set those in our at the correct positions.
Then we loop through starting at two, at the next position, the next fib number and go all the way
up through our array and we just populate our array.
As we go with whatever the previous two values are, so whatever I wear out, we look at the previous
two before it and we sum that and story today.
And so pretty simple, we just literally loop through that and you can see that we're pretty much doing
this in like linear time because we just have to go through that size of in list even less, you know,
we're starting to.
And then at the end, we just return the very last thing in the list, which is that are in numbers
so we can get that instead of announcing numbers since we've already calculated everything as a prerequisite
to the left before it.
So it's like the two previous numbers right here at the very end we have those, we get our last number
and we return that.
So pretty cool.
A lot of dynamic programming algorithms kind of use this style or we're just building up this table.
And we might actually like and some things will just build out a table first and then try and compute
an optimal solution.
You know, remember I talked about this is kind of optimized our time complexity, which is an added
benefit quite often of dynamic programming.
But we also use dynamic programming to come up with like an optimal solution to see like, how can we
get the best, you know, the most things, the most value out of some type of problem.
So just wanted to show you these two versions, I will get into talking more about memorization, and
I think tabulation of where I am remembering that correctly is what's called a billion table, and we'll
get more in depth and cover some more complicated examples.
But hopefully this was a simple enough introduction for you, and it kind of cool for you to see how
much more efficient we can make our calculating the Fibonacci number.
All right.
So with that, I will see you in the next lecture.