Calculating Fibonacci Series using Dynamic Programming
An alternative to calculating it via DAC recursion
Defining a function to calculate the Fibonacci series is one of the many programs every to-be-developer has written at some point. Consider it a “Hello World” program to recursion if you will; they all have more or less written similar lines of code like this:
By the way, you can think of recursion as defining a problem in terms of a simpler version of itself. For instance, the first Fibonacci numbers are 0 and 1; the rest are defined as the sum of the previous 2 numbers in the series:
However, these lines of code are not the best or fastest way to get the Fibonacci numbers. To see why, lets visualize how the function calls are being made in the above code:
Viewing the tree above, you notice that lot of function calls to the same Fibonacci numbers are being called multiple times — this wastes time and space. Couldn’t we just store these results somewhere for future reference? Better yet, instead of branching out exponentially, why not simply go from Fib(0) to Fib(1) to Fib(2) and so on to Fib(n) in a linear, straight fashion?
These questions from the crux of Dynamic Programming.
Dynamic Programming is just a strategy to design code; one that involves:
· Memorization : Storing previous solutions in memory
· Bottom-Up Approach : Solving the simplest problems first
From these 2 axioms one can devise a function that is further optimized to calculate the Fibonacci series: Start from the beginning of the series, and use those calculated Fibonacci numbers to calculate the next one ad nauseam.
We know that the first 2 Fibonacci numbers are pre-defined, 0 and 1.
The next numbers in the series can be calculated by summing up the previous 2 numbers:
Fib(n) = Fib(n-1) + Fib(n-2) if n >= 2
To calculate the numbers after them, we can initialize 2 variables:
Var0 = 0
Var1 = 1
These variables contain the values of the last 2 numbers in the series respectively; which right now is 0 and 1.
To calculate the next Fibonacci number F3:
Set Var0 to Var1 and Var1 to Var0 + Var1
Var0 = 1
Var1 = 1
F3 = Var1 = 1
Voila! Var1 contains our desired result — F3 — and Var0 has F2. Now we can use them to calculate F4:
Var0 = Var1 = 1
Var1 = Var1 + Var0 = 1 + 1 = 2
F4 = 2
You can see the pattern forming here as we can get Fn by looping the above process, indicating we are formulating the series in a linear fashion.
The above process can be implemented quite readily:
For F6, you can observe how Var0 and Var1 change (they start at 0 and 1 respectively):
Intuitively, observe that the loop runs n-2 times for Fn.
As stated above, the time complexity will be O(n) — linear.
Hopefully, more programmers-in-training will start learning about this more efficient way of calculating the Fibonacci series :)
