Now what's Fibonacci sequence?

It's a secret.

So numbers there start with ones at the beginning to one's at the beginning.

On.

After that, we just add the previous two numbers to get the next number.

So one plus one he goes to on one plus two equals three on two plus three equals five and sewn.

And the problem here is finding the end Fibonacci number.

So if and is six the 6th 5th notch number, he's just a The most naive approach we can think of for this problem is a recursive one.

So in this code I'm defining my function here, a fib on if an is equal to one or two.

We just returned one, which is based case on that course most of the 1st 2 elements on If that's not the case, we're just gonna return the sum of the previous element on the second previous sentiment.

So this approach works, but the thing is, this is very, very inefficient.

Let's see why that's the case.

Here's a quick analysis off the naive, recursive approach that we just talked about.

Let's just say I was on example.

We're trying to find the six people match number to do that in this approach.

What we do is we ask ourselves, What's a 50 much number on what's the fourth through much number on when we know what they are.

We add them together to find a six foot much number, and to find the 55 nights number we need to find the forthree months number the third for Munch number and then add them together.

That's what this diagram shows.

And as you can see, the problem with this approach is that there are a lot of duplicates in our competition.

For instance, to find 1/3 Fibonacci number, we're repeating the same process three times.

And to find the 43 minutes number, we're repeating the same competition twice, and that's why this is very slow and in fact, the time it takes to find the ends people.

That's number is about an older off to to the part of end and dynamic programming says we can do much better than that just by storing all those intermediate results.

So here's one very simple, dynamic programming solution.

In this example, we're gonna assume that any is larger than to just for simplicity's sake.

And let's just say we're trying to find the 65 Nights number as our previous example on.

The first thing we do is we initialize Honore off the same size as the given number on.

We're initializing into zeroes here, but it doesn't matter if we initialize it to ones or the ones.

And obviously the 1st 2 elements need to be one, and we're gonna eat.

Read this.

I from two.

Which course monster third, a man here two and mine's one which corresponds to Dallas salmon here and for each eye we're gonna populated with with some off the previous number on the second previous number.

So for the third element, we get one plus one equals two.

And for the fourth element, we get one plus two goes three and five and sewn.

And at the end, we just gonna return the last element India Ray, which is eight.

In this case.

This is a much better solution than the previous solution to find ends.

Frivolous number.

It only takes a leaner time, so it's much faster.

But you might say, Oh, but we're using all this extra space.

And if you don't like that, that's why you can just store the last two elements instead of everything, and you can save some space that way as well.

That's a form of video.

If you like this video, you might also like my video about the maximum suburb, a problem for which you can also use a dynamic programming solution.

And if you want a much more videos like this one, you can just click right here to subscribe to my channel and see you soon.