Oh, it's Y k here.

So in this video, I'm going to talk about what dynamic programming is on, how to use it on.

As I explained how it works, I'm going to assume that you're already from there with rickerson.

So what is dynamic programming?

Exactly?

It's actually fairly simple, even though it might sound difficult.

It's basically a way off making your algorithm more efficient by storing some of the intermediate results.

And he works really well when your algorithm has a lot of repetitive competitions so that you don't have to repeat those competitions over and over again on I'm gonna give you a concrete example of how it works with criminal to sequence.

So just in case you're enough on there with it, Fibonacci sequence is a sequence of numbers.

The starts with two ones at the beginning on each number after that is computed by adding up the two previous numbers.

So the third for much number is two because one plus one equals two and then the fourth man runs number is three because one plus two equals three and sown, and this sequence keeps on going forever.

So let's say we're trying to solve the problem of finding the end spirits number or riding a function called fib Off N, which takes a positive in desert end fines and returns the ends for Iran's number.

So if the given and is three, we want to be able to find and return the third Finn wants number, which is to on if the given and is five.

We want to be able to return the fifth spinouts number, which is five.

Let's see how we can solve this problem using dynamic programming.

So if you want to solve a problem using dynamic programming, they're typically three steps you can take.

The first step is to come out with a recursive solution to your problem and then in your recursive solution.

If you notice that there are a lot of repeated competitions, you can then store some of the intermediate results so that you don't have to repeat those competitions.

This process is also called memorization or memorize, and this is not to be confused with memorize, and I've made that mistake before, too, and then the third step, if you don't like using records in anymore, is to come up with something called a bottom up approach.

So let's first see what every curse of a solution might look like for this particular problem.

So, as I said earlier, we're going to write a function called Fable End, which takes and a positive indicator and returns to the instruments number.

And if N is equal to one or two, we know that the first and the second film Rush numbers are one we're going to return one.

But instead of returning you right away, we're going to store it in a temporary, viable, called a result.

And they returned that instead on it's gonna be clear why we need to do that later on.

If N is neither one nor two, then we're going to return the sum of the two previous criminals numbers is that fever off and minus one plus and minus two store that in result and then returning at the end.

So the solution works, but it's very, very inefficient to see why.

Let's see an example where we're trying to find the 5th 5 minutes number by calling people five.

So to find the return valley off people five, we need to first compute the return valleys for Favell.

Four on people three, so we can add them up.

And to find Favell four.

We need to first compute favorite three anti above two.

And so, and that's what this diagram shows.

I'm looking at this diagram.

You might notice that there are some competitions that we repeat over and over again.

For example, we need to compute the return by re for people to three times.

Andi.

We need to compute the return body for a few of three twice here on.

It's not a big deal when we're trying to find the fifth or sixth feminist number.

But if we're trying to find the hundreds for bonnets number, it becomes an issue, and actually the time it takes to find the ends Favorites number grows exponentially or roughly in the order off to do the part of N on dynamic programming here says.

Why not just store those return by views, for example, for feeble three store the return value wants we computed and then use that same value when we see federal three again instead of computing it again and again.

This process is called memorization, so let's see what a meme wise solution looks like in code.

Let's again consider the example where we're trying to find the fifth Beaumont's number by calling Feeble five.

The idea of this solution is going to be that we're going to use an array whose length Ace and plus one or six in this particular case because and here's five and then we're going to store the return value for the functional fib off N at the index end.

So we're going to store Feeble one, which is the first few months number right here at the next one and then five of two at the next, too and sewn on.

Initially, we're going to set all these five ese to know and we're going to write are functional fib, and this is going to take two arguments instead of just one.

The 1st 1 is the same as before, and a policy manager on the 2nd 1 is going to be this array.

And so you'll need to initialize this array memo before you call this function.

Now, at the beginning of this function, check if Memmo at index and is null or not.

If it's not equal to know that will mean that we've already seen this argument end.

We've already stored the return violet for that at the index and a memo, so just return that instead.

So return memo square brackets end.

Otherwise, the fooling part is the same as before.

If N is equal to one or two, return one store, one in result, and then return that at the end.

And if that's not the case, then find the sum of the two previous favorites numbers, and then return that instead.

And then what's new in dysfunction is that before you return this result, the return value.

You need to store it in a memo at the next end so that you can usually later.

Let's now think about the time complexity for this solution.

We're going to call it tee off end.

This is going to be the time it takes to find the instruments number.

With this particular method on, we're going to find that by multiplying the number of times we call dysfunction fib with the time it takes to execute each of those costs were going to call that tea.

Now there are only two ways we're going to call this function of fib.

The first way is when we call dysfunction for the first time with the arguments and a memo to find the instruments number.

And the second way is from this line right here and noticed that if you look at this whole block after this first, if Klaus this whole block is on, Lee executed most end times.

And this is true because there and possible arguments to dysfunction that's one through N.

And each time this function is called, with each of those arguments, the return value will be stored a memo at the next end.

So after the first time this function is called with, each argument will never get to this block.

And each time this block is executed, Faber is called a most twice if we get to this line.

So the number of times fib is called is at most two times and plus one so to end.

It comes from this block right here on one comes from the first time we call this function fib and the time it takes to execute each of those calls.

This tea right here is going to be a constant time or a big 01 This is because If you look at each operation and dysfunction, excluding these recursive call us that follow.

Each operation is a constant time operation.

And when you have a constant time operation, when you add them up, you still get a constant time operation, which is Big Oaf one.

And that's why we have to go off one here and so t ove n or the time it takes to find the instruments number with this particular method is going to be too n plus.

One times we go off one which is a big off to end plus one, which is eager to big off.

And this is a huge improvement from what we had earlier, which was a big go off to to depart.

And let's now examine how this memo array is actually filled.

So let's say we're trying to find the fifth Fibonacci number again on when we call fib with the argument five on memo.

Of course, we'll see that we don't have a story value at the next five years, so we go down and we're gonna ask ourselves what's the value of fear before and then three, and so on on when we get to favor of two will know that this value is one.

So we're gonna story at next to right here on same with people, one that's one right here.

And once we have these two values will be able to find the 33 much number, which is about three right here.

And then once we find value by adding them up, store that value right here so we can use the later and then when we go up to feed before will add one into right here and we get three and so on until we get here.

And so, as you can see, this arrays mostly filled from left to right.

So when you see this, you might say, Why not just explicitly build this array from left to right from scratch instead of building a recursive week?

That's the idea behind a bottom up approach.

So let's see what a bottom up approach might look like.

In code.

We're going to define a function called fehb bottom up, which steaks and a positive desert just like before and returns to the few minutes number.

And then if n is equal to one or two, Of course, we're going to return one on.

After that, we're going to define Honore, whose length is going to be N plus one where in plus one is six.

Of course, if we're trying to find the fifth Fever dance number right here, if N is equal to five and after that we're going to set the first and the second elements off this array bottom up to be one, these two items right here and then we're going to run a four loop for I from three, which corresponds to this I did right here, Up to N on end corresponds to the last item right here off this saree on whatever index were examining.

Currently, we're going to set that element at the next I or bottom up square brackets I to be the sum of the two previous items.

So in this particular example, will have to hear three here on after that, we're going to return the last item in bottom up or bottom up, square brackets end and we're done.

The time complexity for this algorithm will be again big off.

And because we're going to define this array on, go through this array only once.

Okay, so that's how dynamic programming works.

But now I'm gonna show you a quick demo with Python on something called Jupiter Notebook to show you how this idea might play out in practice.

So in this Jupiter notebook, I have defined a few functions in Python feeble and which is a recursive naive recursive solution on drive off memo on people, too, which represent a memorized solution on fifth bottom up.

Which is, of course, a bottom up solution.

So let's see how they compared to each other in performance.

We're gonna try running Favell and first, the naive recursive solution with people five on That gives us five, which is expected.

What about five of 20?

That gives us the answer pretty quickly, too.

On what?

About five of 35?

This actually takes 5 to 6 seconds on my computer, so it's obviously not the most efficient approach.

Let's see how favor of two and feeble memo the memoirs solution compares to that.

Let's try running fifth memo off.

Five firsts on that gives us five, which is expected.

And what about fifth memo?

35?

That's pretty quick, too.

On what about Fifth memo 100 on Dhe 1000.

This actually gives us honor, and this error is called a recursive error.

Python gives us this, er, actually, because they're too many recursive calls on a coal stack.

And to fix that, we can just use the bottom up approach.

One advantage of using a bottom up approach is that we don't have to put any recursive calls on a coal stack, so we don't have to worry about that.

So we're going to load this function and then run it with the argument 35 which is pretty quick.

1000 and then let's try 10,000 as well.

And that's pretty instantaneous, too.

Okay, so that's my introduction to dynamic programming.

Let me know.

In the comments section below where you thought of this video on if you have any requests about what kind of videos I should make in the future, let me know in the comments section below as well I'm like a from C s social on.