OK, guys, here is the bullet proof formula, and it consists only of five simple steps.
Let's take a look at step number one.
We should define our problems and store their results using arrays for our problem.
The Fibonacci series.
What would be our problems?
Well, the bigger problem is finding what is the Fibonacci number?
In order to solve this problem, I should know that and minus one Fibonacci number and minus two large
number and so on and so on, until I get to know the fourth, the second, the first people, not your
number.
So our of problems is something like that.
What is that?
If Fibonacci number, I should start their results into memory using arrays.
So if I need to know the first, the second, the fourth until the Fibonacci number, that looks to
me to be an array so I can just define the array theme of I want to be that if Fibonacci number and
in memory, it will look like something like this.
And feeB, let's say of one hundred, all the problems are these ones and store their results in memory
using arrays.
Step one is not finished.
Let's take a look.
Step number two.
We should compute the recurrence relation and you will ask me what is the recurrence relation?
It is a formula that computes the solution of some problem, knowing the fact that we already know the
solutions for smaller problems and combining those solutions together to give me the solution for the
initial problem.
In our case, some problem is going to be feasible of the if we want number.
So if I want to find a solution for this problem, I should use some already computed solutions for
smaller problems.
And what are going to be those?
Well, we know that Fibi is definitely equal to feeB of five minus one plus feebs of Pi minus two.
These two are two smaller problems, obviously, and their results would be already computed and we'll
see how we do that.
Step two is now completed.
Step number three, we should define in which order we are going to solve our problems.
And why is that necessary?
Because, as we mentioned, a step two, when we want to compute the solution for a bigger problem,
we assume that we already know the solutions for smaller problems.
So let's take a look at our recurrence relation.
As we can see, feebs of it is going to be equal.
We have Feebles minus one, plus five, minus two.
So in order to correctly compute this value, I should know these values.
So this recurrence relation is valid only if before computing the IFF element.
I know this too.
So in what order should I compute the elements of the array?
And that is obviously increasingly whiffy.
So if I let's say from zero to end, increasingly step three is now completed or at least four step
number four, we should initialize the non computable state and let's find out what that means.
Again, I take a look at step two and I see the recurrence relation.
I know that Fibi is equal to minus one plus or minus two.
But what if this is going to be zero?
How do I know of minus one, plus minus two?
Those values shouldn't exist if I is equal to one, maybe 50 above zero plus above minus one here,
this minus one shouldn't exist.
So only if I is greater or equal then to this recurrence relation is fully valid.
So what do I do with zero and one, if I can compute them using this relation?
Of course I initialize them.
So the only thing we should do here is initialize feebs zero is going to be equal with feebs one and
these two are going to be equal to one.
First things first.
We initialize those two five zero equals if you want equal one.
And then with this I add step three, we are going to go from value to to value.
Now step forward is completed.
And the fifth and final step is we should find the answer of the problem.
In our case, the answer is simple because we want the Fibonacci number.
So our solution would be feebs of N, but in some problems, this answer can actually be harder to compute.
This is the formula for formula that is only this five step.
And if we were to write the code for this problem, you know, first things first, we define this array,
we initialize these values, then we start this loop in the order we define that we will solve our problems.
So for I equals to less or equal to a plus plus and then apply the recurrence relation.
That's all this that's obviously the complexity for this using the dynamic programming approach would
now be big.
And so, guys, I really hope I understood and I can't wait to see on the next lesson.