The Fibonacci Problem

The Fibonacci problem is the first thing you will hear about in any Dynamic Programming lecture or chapter (maybe not!) You can solve this problem using recursive iteration but that would create a lot of stacking in the memory. A lot of these stacks (sub problems) are reputations. For example the Fib(6) = Fib(0) + Fib(1) + Fib(2) + Fib(3) + Fib(4) + Fib(5) + Fib(6). If we look at Fib(4) & Fib(5) then you will see that they both have one in common and that is Fib(3) and Fib(2). So in the following algorithm we basically skip the Fibs that already have been calculated by just memorizing them in some variables (a & b). So instead of O(2^N) time complexity we do it in O(N) time. and O(1) space.


So, what do you think ?