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)