# 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