Hello readers, hope you are doing good. Today we will start with a very important topic which is Dynamic Programming. We will do that through a very simple problem that we have already solved before, then analyze the cons of that approach and come up with a new approach that is more optimized.
Important Links : Problem Link, Question Video
The problem is very simple. The Fibonacci numbers are the series of numbers such that the current number is the sum of the last two numbers. It follows this integer sequence. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144. The 0-th number i.e F0 = 0 and the 1-th number i.e F1 = 1.
The 2-nd number is 0+1 = 1
The 3-rd number is 1+1 = 2
The 4-th number is 1+2 = 3
And so on.
Formula goes like this:
For the recursive approach, we will just implement the recursive formula with the base cases. A very simple approach, it will also get accepted but we will understand the recursion tree for this problem to find room for improvement.
Let's say we are calculating the Fibonacci of 5. So Fib(5), which will in turn call Fib(3) and Fib(4).
Now, do you notice that it is calculating Fib(2) 3 times and Fib(3) twice? For bigger numbers, you will find there is also a lot of repetition. The same calculation is occurring more than once, which is not necessary because the value of Fibonacci remains the same.
We can simply store them somewhere and when needed just retrieve the value, this is actually called Memoization (careful, not memorization).
java;
true";
O(2n) [exponential]
Clearly, the time complexity is exponential. It can also be visualized in a simple manner, like for each Fibonacci you are making 2 sub-calls. And this will happen n times so 2*2*2*2 ... n-times i.e 2n . Thus it is in the order of O(2n).
O(n) [linear]
Since we are making at most n recursion calls, the runtime stack will take up n units of space and hence it will O(n).
We will create a separate array to store the Fibonaccis, let's name that array qb (Question Bank).
Every n that we pass to the Fib() function is a question and the answer is the n-th Fibonacci, which we store in the qb. So that next time we ask the question "What is the n-th Fibonacci?" we can directly reply. So, what changes do we have to do:
Here you can see that when we called the Fib of 2 and 3 for a second time we directly fetched it from the qb[] instead of calculating again.
java;
true";
For n = 45 this approach took 0.114 sec compared to the recursion which took 5.415 secs. You can see the huge optimization.
O(n) [exponential]
Here every Fib(n) will be called only once, because next time the value will be retrieved from the qb. Thus, it will take O(1) per call, hence n*O(1) = O(n)
O(n) [linear]
Here we are using an additional qb[] array to store the results, which will add to the runtime stack space complexity. Thus overall space complexity is O(n+n) which is the same as O(n)
If at any point you found some difficulty I would suggest you watch the video explanation. It is very important that your dp basics are strong.
There is another approach, which is based on O(1) space. Can you find that? Because at any time we are just using the value of n-1 and n-2 we don't need the previous ones. So, there is further room for improvements clearly.
There is also a constant time solution which is based on using a formula for Fibonacci numbers. You can research that too.
