Fibonacci Number

Bottom up approach for printing the nth Fibonacci number using Dynamic Programming.

Recursive Tree

                        fib(5)   
                   /             \     
             fib(4)                fib(3)   
            /      \                /     \
        fib(3)      fib(2)         fib(2)    fib(1)
       /     \        /    \       /    \  
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /    \
fib(1) fib(0)

Overlapping Sub-problems

Here fib(0),fib(1) and fib(3) are the overlapping sub-problems.fib(0) is getting repeated 3 times, fib(1) is getting repeated 5 times and fib(3) is getting repeated 2 times.

Implementation

public int fib(int n){
        int f[] = new int[n+1];
        f[0]=0;f[1]=1;
        for(int i=2;i<=n;i++){
            f[i]=f[i-1]+f[i-2];
        }
        return f[n];
    }

Time Complexity

O(n)

Found a mistake? Have a question or improvement idea? Let me know.

Table Of Contents