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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
public static int getNthFib(int n) { if(n==2) return 1; // 0 + 1 if(n==1) return 0; // 0 int a = 0; int b = 1; int counter=3, fib=0; while(counter<=n){ // n > 2 fib=a+b; a = b; // memo or caching b = fib; counter++; } return fib; } |

## So, what do you think ?